Kombinatorik-Frage

[Tobias P. (hubertus)]

Hallo,
Ich habe da mal eine Kombinatorik-Frage. Im Papula und Bronstein bin ich 
nicht so recht fündig geworden, drum frage ich mal hier.
Folgendes Problem:
Gegeben seien die Buchstaben a und b. Wie viele Kombinationen zu 4 
Buchstaben lassen sich bilden, wenn jeweils 3 Buchstaben gleich sein 
sollen?
Es gibt die Kombinationen

aaab
aaba
abaa
baaa

Sowie

bbba
bbab
babb
abbb

Also 8, aber wie berechne ich das? Es ist nicht die Fakultät und nicht 
der Binominalkoeffizient.

Wenn 2 gleiche Buchstaben verwendet werden sollen, gibt es offenbar 6 
Möglichkeiten:

aabb
abab
baab
abba
baba
bbaa

Das geht mit

4!/(2!*2!)

Warum klappt es also beim Problem oben nicht?

[Willi W. (williwacker)]

Es gibt 4 Positionen für den alleinstehenden Buchstaben und dann kann 
man die Buchstaben noch austauschen. Hast Du doch eigentlich auch schon 
erkannt. Also kleine Formel:

M = p*a, wobei p=..... 4
und a= .... 2

-> M = 8
============

so ungefähr?

[Ben _. (burning_silicon)]

Kann sein, daß das eine Problemstellung ist, die nicht mit einer 
Gleichung lösbar ist.

Bei nur einem "gleichen" Buchstaben passt Deine Gleichung ja auch nicht, 
bei 4 gleichen gibts nur noch zwei Lösungen. Ich halte Deine "Lösung" 
bei dreien daher für eine Zufallspassung...

[D. I. (Gast)]

Die Frage ist gleichbedeutend mit:

Wieviel Kombinationen gibt es k_a von n Plätzen mit a zu belegen +
Wieviel Kombinationen gibt es k_b von n Plätzen mit b zu belegen

dementsprechend 2mal der Bi.-Koeff, wobei man den Fall betrachten muss 
k_a = k_b da fällt das *2 weg

[Peter Z. (peter2)]

Hallo,
das was du meinst ist ja nix anderes wie Permutation mit Wiederholung. 
(Im Bronstein ist das bei mit Kapitel 16.1.1.3.

Du hast n Element von denen k gleich sind. Du musst dann 4!/3! = 4 
rechnen. Du musst allerdings beachten das hier nicht berücksitigt wird 
das die Elemente vertauscht werden also 3*A und 1*B sowie 3*B und 1*A . 
Wie man das noch berücksichtigt müsste man mal in ner ruhigen Minute 
ausknoppeln. In dem einfachen fall kann man ja einfach das ergebnis mal 
2 nhemn.
Gruß
Peter

[P. M. (o-o)]

Der zweite Buchstaben spielt keine Rolle. Die Frage lautet deshalb: Auf 
wie viele Arten kann ich p Objekte auf n Plätzen verteilen.

Tja, einfach: Das erste Objekt kann ich auf n Plätze, das zweite auf (n 
- 1) (einer ist ja schon besetzt), das dritte auf (n - 2) usw. Gibt also 
n * (n - 1) * (n - 2) * ... .

Da die Objekte aber alle gleich sind, muss man noch die internen 
Vertauschungen entfernen, das ist bekanntlich Fakultät p.

Soweit die kombinatorische Erklärung, das Ausrechnen lasse ich dir als 
Übungsaufgabe ;-)

[Tobias P. (hubertus)]

Also, dass da ein *2 sein muss, ist klar wieso.
Ich wundere mich nur, wie man im allgemeinen Fall darauf käme. Wenn ich 
1000 Elemente anordnen müsste, dann könnte ich ja nicht durch probieren 
alle möglichen Kombinationen finden und dann daran ablesen, dass da noch 
ein Faktor 2 hin muss ;-)

[C. P. T. (jimpanse)]

Diese Kategorie von Problemen läuft unter dem Namen:
"Permutationen von klassenweise äquivalenten Objekten"
Bei Wikipedia steht ein Beispiel, dass dir bekannt vorkommen sollte.
Es ist dort recht gut erklärt.