Burnside-Lemma [hilfe 9,5 Möglichkeiten der Anordnung]

30.09.2007, 17:52

AnnaBOS07b

Burnside-Lemma [hilfe 9,5 Möglichkeiten der Anordnung]

Mein Mathelehrer und ich haben folgendes Problem:

Ausgangspunkt war eine Aufgabe im Mathebuch. Verlangt war die Anzahl aller Möglichkeiten, 9 Personen um einen runden Tisch zu verteilen. Von den Personen waren 4 weiblich und 5 männlich. Es wird in der Anordnung nur nach Mann oder Frau unterschieden. Das Mathebuch bigt folgende Lösung an: 8!/4!x5!. (Erklärung: 9!/9 Möglichkeiten, da am runden Tisch der Anfang fehlt, 4!,da 4 Frauen,5!,da 5 Männer). Ausgerechnet ergibt das 14 Möglichkeiten.

So, nun habe ich versucht, diese Formel auf unsere Klasse anzuwenden, wenn alle im Kreis sitzen. Wir sind 20 Personen, davon 2 Männer und 18 Frauen.
Folgendes Problem: Die Rechnung 19!/2!x18! ergibt 9,5 Möglichkeiten!

Und noch schlimmer. Die Formel funktioniert immer dann nicht,wenn 2! im Nenner steht und n eine gerade Zahl ist. Ebenfalls nicht bei 8 Personen und je 4 Männern und Frauen: 7!/4!x4!=8,75 Möglichkeiten.

Ich hoffe, jemand kann uns sagen, wo der Fehler liegt.
Vielen Dank im Voraus!

30.09.2007, 19:23

Auf diesen Beitrag antworten »

wieder mal Burnside-Lemma ...
Lies dir mal in Ruhe diesen Thread durch:

Nochmal Kombinatorik

evtl., auch die weiterführenden Links. Wink

Zitat:

Original von AnnaBOS07b
Und noch schlimmer. Die Formel funktioniert immer dann nicht,wenn 2! im Nenner steht und n eine gerade Zahl ist.

Nein, noch viel schlimmer: Sie funktioniert immer dann nicht, wenn die Anzahlen von Männern und Frauen nicht teilerfremd sind, also z.B. auch nicht bei 3 Männern und 6 Frauen.

----------------------------------------------------------

Aber hier schon mal die Lösung: Mit den Bezeichnungen

$\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ ... Eulersche $\begin{eqnarray*} \varphi \end{eqnarray*}$ -Funktion

$\begin{eqnarray*} T(n) \end{eqnarray*}$ ... Menge der positiven Teiler einer natürlichen Zahl $\begin{eqnarray*} n \end{eqnarray*}$

kann man die Anzahl der Sitzordnungen des runden Tisches mit $\begin{eqnarray*} f \end{eqnarray*}$ Frauen und $\begin{eqnarray*} m \end{eqnarray*}$ Männern folgendermaßen angeben:

$\begin{eqnarray*} \frac{1}{f+m} \, \sum\limits_{t\in T(\operatorname{ggT}(f,m))} \varphi(t)\cdot \binom{\frac{f+m}{t}}{\frac{m}{t}} \end{eqnarray*}$

Im Beispielfall $\begin{eqnarray*} f=18,m=2 \end{eqnarray*}$ ergibt das $\begin{eqnarray*} \operatorname{ggT}(f,m) = \operatorname{ggT}(18,2)=2 \end{eqnarray*}$ und somit die Anzahl

$\begin{eqnarray*} \frac{1}{20} \left( \varphi(1)\cdot \binom{20}{2} + \varphi(2)\cdot \binom{10}{1} \right) = \frac{1\cdot 190 + 1\cdot 10}{20} = 10 \end{eqnarray*}$ .

Noch ein Beispiel: Im Fall $\begin{eqnarray*} f=m=4 \end{eqnarray*}$ sieht das ganze dann so aus

$\begin{eqnarray*} \frac{1}{8} \left( \varphi(1)\cdot \binom{8}{4} + \varphi(2)\cdot \binom{4}{2} + \varphi(4)\cdot \binom{2}{1} \right) = \frac{1\cdot 70 + 1\cdot 6 + 2\cdot 2}{8} = 10 \end{eqnarray*}$ .

01.10.2007, 18:51

AnnaBOS07b

Auf diesen Beitrag antworten »

Vielen Dank,
verstehe zwar nur Bahnhof, weil mir noch nicht einmal Eulersche Funktion was sagt, aber das muss ich dann wohl mal nachlesen...

01.10.2007, 18:59

Auf diesen Beitrag antworten »

Für Schulmathematik ist das tatsächlich etwas hoch. Immerhin ist die Anzahl im Spezialfall, dass $\begin{eqnarray*} f \end{eqnarray*}$ und $\begin{eqnarray*} m \end{eqnarray*}$ teilerfremd sind, einfach gleich

$\begin{eqnarray*} \frac{1}{f+m} \binom{f+m}{m} = \frac{1}{f+m} \cdot \frac{(f+m)!}{m!n!} = \frac{(f+m-1)!}{m!n!} \end{eqnarray*}$ ,

wie von dir oben geschrieben. D.h., von der Summe bleibt nur der Summand $\begin{eqnarray*} t=1 \end{eqnarray*}$ übrig.

Neue Frage »

Antworten »

Burnside-Lemma [hilfe 9,5 Möglichkeiten der Anordnung]

Verwandte Themen