Kombinationsmöglichkeiten < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
Kombinationsmöglichkeiten gleicher Elemente ohne Berücksichtigung der Reihenfolge
Hallo,
ich suche eine Formel, mit der man berechnen kann, auf wieviele Arten man n gleiche Elemente einer Menge aufteilen kann.
Beispielsweise gibt es ja für 2 Elemente genau 2 Möglichkeiten, getrennt oder zusammen, also als {1, 1} und {2}. Bei 3 Elementen gibt es 3 Möglichkeiten {1, 1, 1}, {1, 2} und {3}, bei 4 Elementen dann 5, nämlich {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2} und {4}. Bei 5 Elementen sind es dann schon 7, und zwar {1, 1, 1, 1, 1}, {1, 1, 1, 2}, {1, 1, 3}, {1, 3}, {1, 2, 2}, {2, 3}, {5}. Und wenn ich richtig gezählt habe sind es bei 6 Elementen 11 mögliche Anordungen, bei 7 15 und bei 8 21. Das Prinzip ist also klar, bloß wie kann man das berechnen?
In meinen alten Kombinatorik-Büchern aus dem Mathe-Grundkurs habe ich keine auch nur annähernd ähnliche Aufgabe gefunden, irgendein Muster konnte ich nicht erkennen und eine Idee für einen Lösungsansatz fällt mir auch nicht ein. Einige konzeptlose Trial-And-Error-Versuche, bei denen ich andere Kombinatorik-Formeln verändert oder kombiniert habe, ergaben bis jetzt leider nur "Error".
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:13 Mi 07.09.2005 | | Autor: | Bastiane |
Hallo!
Ich glaube, ich habe eine Idee für deine Aufgabe, aber ich bin mir nicht so ganz sicher, ob ich deine Aufgabe richtig verstehe:
> ich suche eine Formel, mit der man berechnen kann, auf
> wieviele Arten man n gleiche Elemente einer Menge aufteilen
> kann.
Was genau meinst du mit aufteilen? Also meinst du, dass du z. B. 20 Erbsen hast und sie einerseits in 20 Einerpäckchen verteilen kannst. Oder in 4 Fünferpäckchen. Oder in 2 Zehnerpäckchen. Oder wie auch immer. Und nun willst du wissen, wie viele Möglichkeiten es gibt, die Erbsen so hinzulegen. Meinst du das?
> Beispielsweise gibt es ja für 2 Elemente genau 2
> Möglichkeiten, getrennt oder zusammen, also als {1, 1} und
> {2}. Bei 3 Elementen gibt es 3 Möglichkeiten {1, 1, 1}, {1,
> 2} und {3}, bei 4 Elementen dann 5, nämlich {1, 1, 1, 1},
> {1, 1, 2}, {1, 3}, {2, 2} und {4}. Bei 5 Elementen sind es
> dann schon 7, und zwar {1, 1, 1, 1, 1}, {1, 1, 1, 2}, {1,
> 1, 3}, {1, 3}, {1, 2, 2}, {2, 3}, {5}. Und wenn ich richtig
> gezählt habe sind es bei 6 Elementen 11 mögliche
> Anordungen, bei 7 15 und bei 8 21. Das Prinzip ist also
> klar, bloß wie kann man das berechnen?
So wie das in deinem Beispiel hier ist, sieht es so aus, als hätte es etwas mit den Zahlen und deren Zerlegen in Summanden zu tun. Aber da du ja geschrieben hast, man hätte n gleiche Elemente, verstehe ich das dann nicht ganz...
Viele Grüße
Bastiane
![[banane]](/images/smileys/banane.gif "[banane]")
|
|
|
| |
|
> Was genau meinst du mit aufteilen? Also meinst du, dass du
> z. B. 20 Erbsen hast und sie einerseits in 20 Einerpäckchen
> verteilen kannst. Oder in 4 Fünferpäckchen. Oder in 2
> Zehnerpäckchen. Oder wie auch immer. Und nun willst du
> wissen, wie viele Möglichkeiten es gibt, die Erbsen so
> hinzulegen. Meinst du das?
Genau, oder etwa ein Einzelpäckchen und eine Neunzehnerpackung usw.
> So wie das in deinem Beispiel hier ist, sieht es so aus,
> als hätte es etwas mit den Zahlen und deren Zerlegen in
> Summanden zu tun. Aber da du ja geschrieben hast, man hätte
> n gleiche Elemente, verstehe ich das dann nicht ganz...
Ja, im Prinzip wäre das eine Summandenzerlegung. Mit den "gleichen Elementen" meine ich, daß sie nicht unterscheidbar sind bzw. nicht unterschieden werden, es also keinen Unterschied spielen soll, ob bei den Erbsen in einer Zweierpackung die größere links oder rechts liegt oder wie die Päckchen untereinander angeordnet sind.
|
|
|
| |
|
Was du suchst, sind die sogenannten ![[]](/images/popup.gif) Partitionszahlen [mm]p(n)[/mm]. Soweit mir bekannt ist, gibt es dafür keine geschlossene Formel. Man kann sie allerdings rekursiv berechnen durch
[mm]p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + + - - \ldots[/mm]
(auf jeweils zwei Plusglieder folgen jeweils zwei Minusglieder)
Die Subtrahenden in den Argumenten sind die sogenannten Pentagonalzahlen
[mm]\omega_k = \frac{1}{2} \left( 3k^2 - k \right)[/mm]
und zwar in der Reihenfolge [mm]\omega_1, \omega_{-1}, \omega_2, \omega_{-2}[/mm] usw. Und die Rekursion endet in
[mm]p(0) = 1 \, , \ p(n) = 0[/mm] für [mm]n<0[/mm]
Ein kleines Programm für den Rechner liegt da ja nahe ...
|
|
|
|
