Anzahl möglicher Kombinationen eine Zahl zu zerlegen

07.03.2019, 13:36

Meunier

Anzahl möglicher Kombinationen eine Zahl zu zerlegen

Hallo zusammen,
Wie berechne ich die Anzahl aller möglichen Kombinationen eine Zahl x (Beispiel 21) aus den Zahlen 2, 3 und 4 zusammenzusetzen unter Berücksichtigung der Reihenfolge?
4+3+3+3+3+2+3 != 3+4+3+3+3+2+3 ist zwar von den einzelnen Summanden identisch aber die Reihenfolge an Position 1 und 2 sind vertauscht und wären somit 2 Lösungsmöglichkeiten.

Vielen Dank im voraus
Matthias

07.03.2019, 13:59

HAL 9000

Auf diesen Beitrag antworten »

Nun, es geht rekursiv: Sei $\begin{eqnarray*} f(n) \end{eqnarray*}$ die Anzahl solcher Zerlegungen der Zahl $\begin{eqnarray*} n \end{eqnarray*}$ , dann ist $\begin{eqnarray*} f(1)=0,f(2)=1,f(3)=1,f(4)=2 \end{eqnarray*}$ sowie $\begin{eqnarray*} f(n) = f(n-2)+f(n-3)+f(n-4) \end{eqnarray*}$ für $\begin{eqnarray*} n\geq 5 \end{eqnarray*}$ .

Damit ergibt sich dann z.B. $\begin{eqnarray*} f(21)=1113 \end{eqnarray*}$ .

Aus einer derartigen Differenzengleichung lässt sich auch eine explizite Darstellung $\begin{eqnarray*} f(n) = \sum_{k=1}^4 C_k\lambda_k^n \end{eqnarray*}$ gewinnen, wobei $\begin{eqnarray*} \lambda_1,\ldots,\lambda_4 \end{eqnarray*}$ die vier Lösungen der Polynomgleichung $\begin{eqnarray*} \lambda^4-\lambda^2-\lambda-1=(\lambda+1)(\lambda^3-\lambda^2-1)=0 \end{eqnarray*}$ darstellen, sowie $\begin{eqnarray*} C_1,\ldots,C_4 \end{eqnarray*}$ anschließend aus den vier Anfangswerten gewonnen werden kann.

07.03.2019, 15:25

Meunier

Auf diesen Beitrag antworten »

Hi HAL 9000
vielen Dank für die schnelle Antwort.
Ich bin aber noch ein bisschen skeptisch was das Ergebnis angeht.
Wenn ich die Formel für n = 7 durchrechne komme ich auf 84.
Zerlege ich die 7 in Variationen aus 2,3 und 4 erhalte ich zB Patterns wie

[2,2,3] [2,2,3] gesetzt dem Fall, dass die beiden 2-en nicht identisch sind
[2,3,2] [2,3,2]
[3,2,2] [3,2,2]
[3,4] [4,3]

Mehr Möglichkeiten sehe ich nicht - jedenfalls bei weitem keine 84.
Optimal wäre auch, die "doppelten" Patterns auf jeweils 1 zu reduzieren.

VG
Matthias

07.03.2019, 15:34

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Meunier
Wenn ich die Formel für n = 7 durchrechne komme ich auf 84.

Was auch immer du da rechnest - nach der Rekursionformel oben ist

$\begin{eqnarray*} f(5) = f(3)+f(2)+f(1) = 1+1+0 = 2 \end{eqnarray*}$
$\begin{eqnarray*} f(7) = f(5)+f(4)+f(3) = 2+2+1 = 5 \end{eqnarray*}$ ,

und das sind die 5 Varianten:

2+2+3
2+3+2
3+2+2
3+4
4+3

EDIT (11.3.): Eigentlich wäre es angebracht, dass man sich nach solchen (auf Basis eines eigenen Rechenfehlers) unberechtigt angemeldeten Zweifeln nochmal zwecks Klarstellung zu Wort meldet... Ich erwarte ja nicht unbedingt eine "schnelle" Antwort, aber wenn man schon am selben Tag 17:20 reinschaut und drei Tage später immer noch nicht reagiert hat, dann sieht das nicht gerade danach aus, als hätte man noch Interesse an dem Thema. unglücklich

Neue Frage »

Antworten »

Anzahl möglicher Kombinationen eine Zahl zu zerlegen

Verwandte Themen