Partitionen, Permutationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 12:36 So 30.07.2006 | | Autor: | dump_0 |
| Aufgabe | a) In einer Straße stehen x viele Häuser nebeneinander. Ein Malerbetrieb, in dessen Lager y viele Farben vorrätig sind, soll alle Häuser anmalen, wobei höchstens $z [mm] \le [/mm] y$ viele Farben benutzt werden sollen. Wie viele unterscheidbare Möglichkeiten gibt es, die Häuser zu streichen (natürlich soll jedes Haus in genau einer Farbe gestrichen werden - es soll also keine mehrfarbigen Häuser geben)?
b) Gegeben sei die Permutation
[mm] $\pi [/mm] = [mm] \pmat{ 1 & 2 & 3 & 4\\ 2 & 1 & 4 & 3 }$
[/mm]
Schreiben Sie [mm] $\pi$ [/mm] als Produkt nicht disjunkter Zyklen. |
Hallo.
Bei den 2 oben stehenden Aufgaben komme ich nicht so recht weiter.
bei a) habe ich es mit den Bell-Zahlen versucht, also
[mm] $B_z [/mm] = [mm] \summe_{k=1}^{z} [/mm] S(x, z)$, also das alle Möglichkeiten betrachtet werden die Häuser von 1 bis z Farben anzustreichen. Anscheinend reicht das aber leider noch nicht aus, ich weiß aber nicht was noch fehlt :-?
Bei b) habe ich leider keine Ahnung wie man nicht disjunkte Zyklen bildet, disjunkte ist klar.
Schöne Grüße
[mm] dump_0
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:20 Mo 31.07.2006 | | Autor: | DirkG |
Zu a)
Die Stirling-Zahl $S(x,m)$ beschreibt ja erstmal nur die Anzahl der Möglichkeiten, eine $x$-elementige Menge in genau $m$ nichtleere Partitionen zu zerlegen. Jetzt musst du aber für jede dieser Partitionen noch die Anzahl der Färbungen berücksichtigen, und die ist jeweils [mm] $\frac{y!}{(y-m)!}$. [/mm] Also lautet die Antwort
[mm] $$\sum\limits_{m=1}^z [/mm] ~ [mm] \frac{y!}{(y-m)!}S(x,m)$$ [/mm] .
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:09 Mo 31.07.2006 | | Autor: | dump_0 |
Vielen Dank für deine Antwort. Ich hätte eher noch "ungeordnetes Ziehen ohne zurücklegen" getippt, aber wenn man die Partitionen bedenkt, muss es ja geordnet sein :)
Grüße
|
|
|
|
