Anzahl der Möglichkeiten ein Wort der Länge x zu zerschneiden und auf k Variablen zu verteilen?

Question

Aufgabe:

Wieviele Möglichkeiten gibt es die Wörter „abc“, „abcd“ zu zerschneiden und auf 3 Variablen zu verteilen?

Zum Beispiel soll sich „abc“ aufteilen lassen:

x= abc oder x= a, y= ab oder x=a, y=b, z=c ...

Die Reihenfolge der Zeichen darf nicht verändert werden.

1) x,y,z können auch leer sein

2) y muss mindestens ein Zeichen enthalten

Problem/ Ansatz

Gibt es dafür eine Formel?

Für 1) und Wortlänge

1=> 3 Möglichkeiten

2=> 6 Möglichkeiten

3=> 10 Möglichkeiten

4=> 14 Möglichkeiten?

Answer 1

Für 1) und Wortlänge

f(n) = (n + 2)! / (n! * 2!) = 0.5·n^2 + 1.5·n + 1

n	1	2	3	4	5	6	7	8	9	10
f(n)	3	6	10	15	21	28	36	45	55	66

Comments

An die Formel kommt man nur über eine Reihe von Werten und dann mit Newton interpolierten? Auf 4 Fächer(Variablen) wäre ja eine andere Formel.

!

---

Das ist die normale Formel für Permutationen mit Wiederholungen.

Nimm an du hast ein Wort aus drei Buchstaben *** und sollst es in 3 Stücke zerschneiden wobei die Stücke auch leer sein können. Dann fügt man 2 Trenner ein und bekommt so folgende Möglichkeiten

||***
|*|**
|**|*
|***|
*||**
*|*|*
*|**|
**||*
**|*|
***||

Das ist also auch die typische Kombinatorikformel der Kombination mit Wiederholungen

((n über k)) = (n - 1 + k über k) = (n - 1 + k)!/((n - 1)! * k!)

wobei k hier die Anzahl der Buchstaben ist und n die Anzahl der Variablen.

Es ist also die Formel ein Wort mit k Buchstaben auf n Variablen zu verteilen.

Siehe auch: https://de.wikipedia.org/wiki/Abz%C3%A4hlende_Kombinatorik

---

An den n über k hatte ich auch gedacht, aber nicht an mit zurücklegen. Grüße