Kombinatorik: Anzahl k Kugeln in k Körbe?

22/08/2010 - 01:02 von Jürgen Will | Report spam
Hallo,

bin kein Mathematiker; bekomme nur einfachere kombinatorische Probleme hin.
Kann mir jemand bei dem unten beschriebenen für mich etwas komplizierteren
Problem helfen?

Ich suche eine Methode für die Abzàhlung der möglichen Aufteilungen einer
Menge von k Kugeln auf eine Menge von k Körben, wobei in jedem Korb genau
ein Ball plaziert ist, und sowohl für die Menge der Kugeln als auch für die
Menge der Körbe eine Konfiguration für die Ununterscheidbarkeit gegeben ist.
Beispiel: 4 Kugeln, wovon genau 3 dieselbe Farbe haben, und 4 Körbe, von
denen genau 2 dieselbe Farbe haben.

Ich hab's mit dem Pólya-Theorem versucht, aber ich komme nicht auf den
Zyklenzeiger der Permutationsgruppe der Menge der Körbe. Vielleicht ist ja
Pólya auch zu hoch gegriffen?

Danke!
 

Lesen sie die antworten

#1 Bastian Erdnuess
22/08/2010 - 07:49 | Warnen spam
Jürgen Will wrote:

Hallo,

bin kein Mathematiker; bekomme nur einfachere kombinatorische Probleme hin.
Kann mir jemand bei dem unten beschriebenen für mich etwas komplizierteren
Problem helfen?

Ich suche eine Methode für die Abzàhlung der möglichen Aufteilungen einer
Menge von k Kugeln auf eine Menge von k Körben, wobei in jedem Korb genau
ein Ball plaziert ist, und sowohl für die Menge der Kugeln als auch für die
Menge der Körbe eine Konfiguration für die Ununterscheidbarkeit gegeben ist.
Beispiel: 4 Kugeln, wovon genau 3 dieselbe Farbe haben, und 4 Körbe, von
denen genau 2 dieselbe Farbe haben.



Verstehe ich dich richtig, du hast also z. B. eine schwarze und drei
weiße Kugeln, die du auf zwei rote, einen blauen und einen gelben Korb
aufteilen willst, so dass in jedem Korb eine Farbe liegt?

Da kommt es doch nur drauf an, welche Farbe der Korb hat, in dem die
schwarze Kugel liegt, und dafür gibt es drei Möglichkeiten, nàmlich rot,
blau oder gelb. In dem Fall gibt es also drei Kombinationen.

Ich hab's mit dem Pólya-Theorem versucht, aber ich komme nicht auf den
Zyklenzeiger der Permutationsgruppe der Menge der Körbe. Vielleicht ist ja
Pólya auch zu hoch gegriffen?



Für dieses spezielle Problem auf jeden Fall. Wenn es dir aber auch um
komplexere Probleme dieser Art geht, hilft Polya schon weiter.

Was ist in dem Fall die Symmetriegruppe der Körbe? Nun, du kannst nur
gerade die beiden roten Körbe vertauschen ohne was an dem Aussehen der
Korbreihe zu veràndern, die anderen beiden Körbe müssen stehenbleiben.
D. h. die Symmetriegruppe ist S_2 x S_1 x S_1. Sie hat den
Zyklenindex (x_1^4 + x_2*x_1^2)/2.

Gruß,
Bastian

Ähnliche fragen