Anzahl nicht-abnehmender k-Tupel natürlicher Zahlen von 1 bis n entspricht dem Binomialkoeffizienten (n+k-1 über k)

Question

Aufgabe:

Folgendes ist gegeben: Seien n,k∈N . Man beweise: Die Anzahl aller k-Tupel (a_1,...,a_k) ∈ N^k mit

Text erkannt:

\( 1 \leq a_{1} \leq a_{2} \leq \cdots \leq a_{4} \leq n \)

ist gleich

Text erkannt:

\( \binom{n+k-1}{k} \)

Problem/Ansatz:

Ich habe folgenden Ansatz: da die Reihe strikt aufsteigend ist kann man diese Reihe auch als Auswahl von k Elementen aus der Gesamtmenge auffassen. Jede Auswahl entspricht einer schwach wachsenden Tupelfolge (a_1, ..., a_n)

dies entspricht dem Binomialkoeffizienten

Text erkannt:

Es ist ersichtlich, dass in den tupeln auch zahlen dopplungen vorkommen können. Meiner Meinung nach kann man auch das Problem umschreiben zu x_1 + x_2 + ... +x_n = k, für i = Anzahl der Auftretens der Zahl i in einem Tupel, wobei i von 1 bis n läuft.

Man schaut also, wie häufig man Einheiten k einheiten auf n positionen verteilt.

Mathematisch kann ich das aber leider nicht beweisen. Ich bräuchte Hilfe, bei der Beweisführung, da ich bisher nur Vermutungen aufgestellt habe.

Answer 1

Hallo,

es gibt verschiedene Ansätze:

Z.B.: Bilde die angegebenen Tupel bijektiv auf folgende Tupel \((b_1, \ldots, b_k)\) mit

$$b_1:=a_i, \qquad b_i:=a_i+i-1, \quad i=2, \ldots k$$

Jetzt gilt \(b_{i+1}>b_i\) und \(b_k \leq n+k-1\). D.h. die neuen Tupel repräsentieren jeweils eine k-elementige Teilmenge von 1 bis n+k-1

Z.B:. Du kannst aus den \(a_i\) eine Summenzerlegung von n basteln:

$$n=a_1+(a_2-a_1)+(a_3-a_2)+ \cdots (a_k-a_{k-1})+(n-a_k)$$

Das wurde auf der ML kürzlich besprochen.

(Ich finde den ersten Vorschlag schöner)

Answer 2

Aloha :)

Willkommen in der Mathelounge... \o/

Aus den natürlichen Zahlen von \(1\) bis \(n\) sollen wir \(k\) Werte \(x_1;\ldots;x_k\) auswählen mit$$1\le x_1\le x_2\le\ldots\le x_k\le n$$und diese in einem \(k\)-Tupel anordnen. Dazu führen wir Zählvariablen \(a_i\) ein, wobei \(a_i\) angibt, wie oft die Zahl \(i\) ausgewählt wurde.

Ist also z.B. \(n=5\) und \(k=3\), wäre das \(3\)-Tupel \((3,3,5)\) wie folgt codiert:$$a_1=0\quad;\quad a_2=0\quad;\quad a_3=2\quad;\quad a_4=0\quad;\quad a_5=1$$

Wir abstrahieren, indem wir für jede Auswahl ein Sternchen schreiben:$$a_1=\quad;\quad a_2=\quad;\quad a_3=\ast\ast\quad;\quad a_4=\quad;\quad a_5=\ast$$Die \(a_i\) brauchen auch nicht mehr, da sie ja durch Semikolons voneinander getrennt sind:$$;;\ast\ast;;\ast$$

Die Anzahl der Sterne ist für jedes Tupel gleich \(k\) und die Anzahl der Semikolons ist für jedes Tupel gleich \((n-1)\).

Wir haben in unserer Codierung also insgesamt \((n+k-1)\) Positionen, von denen wir genau \(k\) auswählen müssen, um sie mit einem Sternchen zu besetzen. Die übrigen \((n-1)\) Positionen sind dann automatisch jeweils durch ein Semikolon zu besetzen.

Es gibt genau \(\binom{n+k-1}{k}\) Möglichkeiten zur Auswahl der Sternchen-Positionen.

Answer 3

Da Mathhilf die Differenzerlegung nur kurz erwähnt, diese mir aber gefällt, ergänze ich noch schnell diesen Zugang:

Jedes Tupel wird eineindeutig durch eine Folge von nichtnegativen Differenzen \(d_i\) wie folgt beschrieben:

\(1 \stackrel{d_1}{\rightarrow} a_1 \stackrel{d_2}{\rightarrow}a_2\rightarrow \cdots \stackrel{d_k}{\rightarrow} a_k \stackrel{d_{k+1}}{\rightarrow}n\)

Dabei gilt:

\(0\leq d_i \leq n-1\) und \(\displaystyle d_1+ \cdots + d_{k+1}=n-1\)

Damit haben wir ein klassisches Stars-and-Bars-Szenario (siehe hier oder hier).

Es ist schnell einzusehen, dass es genau \(\binom{n-1+k}{k}\) solcher Differenzfolgen gibt.