Geordnete Zahlpartitionen

03.09.2009, 13:31

cheetah_83

Geordnete Zahlpartitionen

Hallo
Ich weiss bereits, dass die Anzahl geordneter Zahlapartitionen, also die Möglichkeiten eine Zahl p durch K Summanden auszudrücken $\begin{eqnarray*} \begin{pmatrix} p+K-1 \\ p \end{pmatrix} \end{eqnarray*}$ ist. Wobei die einzelnen Summanden auch 0 sein dürfen. Soweit hoffentlich richtig.
Interessieren würde mich jetzt die Anzahl, wenn ich bestimmte Summanden ausschliesse. In meinem Fall soll keiner der Summanden 1 sein.
Gibt es da ein einfache Möglichkeit das auszurechnen?
Meine erste Idee war die Anzahl der Partitionen mit einer 1 auszurechnen, dabei komme ich dann auf $\begin{eqnarray*} K \begin{pmatrix} p-1 + K-1 -1\\ p-1 \end{pmatrix} \end{eqnarray*}$ . Kann das jemand bestätigen?
Wenn ich die jetzt voneiner abziehe, komme ich aber leider auf nichts vernünftiges.
Hat zufällig jemand ne andere Idee, womit ich auf einen schönen ausdruck komme?

03.09.2009, 14:06

Auf diesen Beitrag antworten »

Zitat:

Original von cheetah_83
Meine erste Idee war die Anzahl der Partitionen mit einer 1 auszurechnen, dabei komme ich dann auf $\begin{eqnarray*} K \begin{pmatrix} p-1 + K-1 -1\\ p-1 \end{pmatrix} \end{eqnarray*}$ . Kann das jemand bestätigen?

Gute Idee, aber schlecht durchdacht. Du betrachtest

$\begin{eqnarray*} A_j \end{eqnarray*}$ ... Menge aller Partitionen mit einer 1 an Stelle $\begin{eqnarray*} j \end{eqnarray*}$

um an

$\begin{eqnarray*} A=\bigcup\limits_{j=1}^K A_j \end{eqnarray*}$ ... Menge aller Partitionen mit mindestens einer 1

heranzukommen, und rechnest richtig $\begin{eqnarray*} |A_j| = \binom{p-1 + K-1 -1}{p-1} = \binom{p+K-3}{p-1} \end{eqnarray*}$ aus, zumindest im Fall $\begin{eqnarray*} p\geq 1,K\geq 2 \end{eqnarray*}$ .

Dummerweise gilt hier aber wegen Überschneidungen nicht einfach

$\begin{eqnarray*} |A| \stackrel{???}{=} \sum\limits_{j=1}^K |A_j| \end{eqnarray*}$ ,

sondern du musst wegen dieser Überschneidungen dann schon mit sowas wie der Siebformel ran.

Allgemein zum Problem des "Summandenausschlusses": Summand 0 auszuschließen, ist leicht - weil man dann bijektiv auf das Ausgangsproblem "Zahl p-k mit k Summanden darstellen" abbilden kann, mit Anzahl $\begin{eqnarray*} \binom{p-k+k-1}{p-k} = \binom{p-1}{p-k} = \binom{p-1}{k-1} \end{eqnarray*}$ .

Bei allen anderen Summanden wird es schwieriger, da wird wohl der obige Weg über die Siebformel in der Regel nicht durch was wesentlich einfacheres ersetzbar sein.

Neue Frage »

Antworten »

Geordnete Zahlpartitionen

Verwandte Themen