Kombinatorik Aufgabe

22.05.2008, 14:23

Gast2008

Kombinatorik Aufgabe

Hallo Leute,
habe folgende aufgabe zugeteilt bekommen und habe keine idee wie ich die sache herangehen soll!

Auf wie viel verschieden Arten kann man die Seiten eines regelmäßigen p Ecks
mit n Farben f¨arben, wenn p eine Primzahl ist und wenn genau zwei Färbungen,
die durch Rotation ineinander üuberführt werden k¨onnen, als identisch angesehen werden?

keine ahnung was erstens mit der rotation gemeint ist und wie ich an diese aufgabe herangehen soll! Bitte um eure hilfe!
Vielen Dank

22.05.2008, 15:39

Auf diesen Beitrag antworten »

Gemeint ist, dass z.B. ein regelnmäßiges Fünfeck mit den Seitenfarben

rot - blau - blau - gelb - grün

(in der Reihenfolge im Uhrzeigersinn) und eines mit

blau - gelb - grün - rot - blau

als gleichgefärbt angesehen werden, weil das zweite aus dem ersten durch Drehung um $\begin{eqnarray*} 2 \cdot 72^{\circ} = 144^{\circ} \end{eqnarray*}$ um den Mittelpunkt hervorgeht.

Ich nehme hier in dem Beispiel einfach mal an, dass einzelne Farben (hier: blau) auch zur Färbung mehrerer Seiten herangezogen werden dürfen, ansonsten wird die Aufgabe gar zu einfach. Augenzwinkern

22.05.2008, 19:32

Gatsr2008

Auf diesen Beitrag antworten »

Ersteinmal Danke, jetzt weiß ich was gemeint ist,
aber wie geht man jetzt allgemein an so eine aufgabe ran?hab garkein ansatz/idee, wie ich zeigen soll, wieviel möglichkeiten es gibt! das wäre echt nett, wenn du/ihr mir da auf die sprünge helfen könntet!
Vielen dank

22.05.2008, 20:35

Auf diesen Beitrag antworten »

Überleg dir doch erstmal, wieviel Färbungen es ohne diese Bedingung der Drehungsinvarianz gibt.

In einem zweiten Schritt kannst du dir überlegen, welche der Färbungen davon überhaupt nur bei irgendwelchen Drehungen in sich selbst (!) übergehen können. Ich lasse mal das Stichwort "Burnside-Lemma" fallen - sagt dir das was? Wenn nicht auch nicht schlimm, man kommt in der Erklärung auch ohne das Lemma aus.

22.05.2008, 21:13

Gast2008

Auf diesen Beitrag antworten »

ne sagt mir nichts,
also ohne einschränkung würd ich sagen:

für die erste seite habe ich n möglichkeiten (n farben), für die zweite seite hab ich auch n möglichkeiten, da wiederholung nicht aus geschlossen ist usw., also insgesamt n^p möglicheiten oder? und jetzt muss man die bedingung einbauen!?!wie!?!

22.05.2008, 21:30

Auf diesen Beitrag antworten »

Die Anzahl $\begin{eqnarray*} n^p \end{eqnarray*}$ für Schritt 1 ist schon erstmal richtig. Freude

Zitat:

Original von Arthur Dent
In einem zweiten Schritt kannst du dir überlegen, welche der Färbungen davon überhaupt nur bei irgendwelchen Drehungen in sich selbst (!) übergehen können.

Wenn du's schon nicht sofort allgemein sagen kannst, dann überlege es dir mal für konkrete $\begin{eqnarray*} p \end{eqnarray*}$ , z.B. 3, 5, 7 ...

Ich will's mal am Beispiel einer Färbung für eine Nichtprimzahl $\begin{eqnarray*} p \end{eqnarray*}$ veranschaulichen:

Für $\begin{eqnarray*} p=6 \end{eqnarray*}$ kann man die Färbung

rot , blau , rot , blau , rot , blau

um $\begin{eqnarray*} 120^{\circ} \end{eqnarray*}$ drehen und erhält dieselbe Färbung!

Ist sowas für eine Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ auch möglich? Und wenn ja, für welche Färbung?

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

Was bringt das ganze? Man kann die obigen $\begin{eqnarray*} n^p \end{eqnarray*}$ Färbungen in Äquivalenzklassen bzgl. Drehungsinvarianz aufteilen, gesucht ist in dieser Aufgabe nun gerade die Anzahl $\begin{eqnarray*} k \end{eqnarray*}$ der Äquivalenzklassen. Wenn nun $\begin{eqnarray*} a_j \end{eqnarray*}$ die Anzahl der Färbungen in Äquivalenzklasse $\begin{eqnarray*} j \end{eqnarray*}$ ist, dann muss offenbar

$\begin{eqnarray*} \sum_{j=1}^k a_j = n^p \end{eqnarray*}$

gelten. Also lohnt es sich, die $\begin{eqnarray*} a_j \end{eqnarray*}$ rauszukriegen, dann kommt man auch an das $\begin{eqnarray*} k \end{eqnarray*}$ ran. Das ist in aller Kürze das Burnside-Lemma soweit eingedampft, wie es für diese Aufgabe ausreicht.

Neue Frage »

Antworten »

Kombinatorik Aufgabe

Verwandte Themen