Verteilung von n Objekten auf n + 1 viele Positionen

20.11.2020, 21:32	anAlphabet	Auf diesen Beitrag antworten »
Verteilung von n Objekten auf n + 1 viele Positionen Meine Frage: Gegeben sind n + 1 viele Positionen. Es soll bestimmt werden, wie viele Möglichkeiten es gilt n ununterscheidbare Objekte auf diese Positionen zu verteilen (jede einzelne Position kann dabei beliebig viele der Objekte beinhalten). Alternativ könnte man wohl auch formulieren (aber ich bin mir bzgl. Äquivalenz nicht sicher): Wie viele Kombinationen aus n+1 natürlichen Zahlen inkl. 0 gibt es, sodass deren Summe n beträgt (dann wäre der erste Summand die Zahl der Objekte in Position 1). Meine Ideen: Mein erster Ansatz war zu sagen, dass ich für jedes Objekt aufs neue mich für eine neue Position entscheide, also (n+1)^n. Das Problem ist dabei natürlich, dass in verschiedener Reihenfolge auf die gleiche Verteilung kommen kann, also zB. erstes Objekt in Position 1 dann zweites in Position 2 vs. erstes Objekt nach 1 und zweites nach 2. Also hatte ich mir überlegt durch n! zu teilen, da ich für jede Verteilung so viele Permutationen hätte um zu ihr zu kommen, das passt aber auch nicht. Gehen alle Objekte in Position 1, so brauche ich hierfür nicht mehr durch n! teilen... Sehr glücklich über Tips!
20.11.2020, 22:02	HAL 9000	Auf diesen Beitrag antworten »
Kombinationen von $\begin{eqnarray} n \end{eqnarray}$ aus $\begin{eqnarray} (n+1) \end{eqnarray}$ mit Wiederholung: Anzahl $\begin{eqnarray} \binom{n+1+n-1}{n} = \binom{2n}{n} \end{eqnarray}$
20.11.2020, 23:55	Finn_	Auf diesen Beitrag antworten »
Seitdem ich mich mit Gitterwegen beschäftigt habe, muss ich da bei Binomialkoeffizienten zwanghaft dran denken. Die Problemstellung ist auch hier so interpretierbar. Legt man ein Objekt auf eine Position, geht es auf dem Gitter einmal nach oben. Geht man zur nächsten Position, geht es auf dem Gitter einmal nach rechts. Weil es $\begin{eqnarray} n+1 \end{eqnarray}$ Positionen gibt (0, 1, ..., n), geht es $\begin{eqnarray} n \end{eqnarray}$ mal nach rechts. Weil es $\begin{eqnarray} n \end{eqnarray}$ Objekte gibt, geht es $\begin{eqnarray} n \end{eqnarray}$ mal nach oben. Gesucht ist daher, wie viele Gitterwege von (0,0) zu (n,n) führen. Allgemein ist $\begin{eqnarray} \binom{x+y}{x} = \binom{x+y}{y} = \frac{(x+y)!}{x!y!} \end{eqnarray}$ die Zahl der Gitterwege von (0,0) zu (x,y). Die analoge Überlegung in mehr als zwei Dimensionen führt zu Multinomialkoeffizienten.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »