0 Daumen
414 Aufrufe

Aufgabe:

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

blob.png

Text erkannt:

1a1a2a4n 1 \leq a_{1} \leq a_{2} \leq \cdots \leq a_{4} \leq n

ist gleich blob.png

Text erkannt:

(n+k1k) \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 blob.png

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.

Avatar von

3 Antworten

0 Daumen

Hallo,

es gibt verschiedene Ansätze:

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

b1 : =ai,bi : =ai+i1,i=2,kb_1:=a_i, \qquad b_i:=a_i+i-1, \quad i=2, \ldots k

Jetzt gilt bi+1>bib_{i+1}>b_i und bkn+k1b_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 aia_i eine Summenzerlegung von n basteln:

n=a1+(a2a1)+(a3a2)+(akak1)+(nak)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)

Avatar von 14 k
0 Daumen

Aloha :)

Willkommen in der Mathelounge... \o/

Aus den natürlichen Zahlen von 11 bis nn sollen wir kk Werte x1;;xkx_1;\ldots;x_k auswählen mit1x1x2xkn1\le x_1\le x_2\le\ldots\le x_k\le nund diese in einem kk-Tupel anordnen. Dazu führen wir Zählvariablen aia_i ein, wobei aia_i angibt, wie oft die Zahl ii ausgewählt wurde.

Ist also z.B. n=5n=5 und k=3k=3, wäre das 33-Tupel (3,3,5)(3,3,5) wie folgt codiert:a1=0;a2=0;a3=2;a4=0;a5=1a_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:a1=;a2=;a3=;a4=;a5=a_1=\quad;\quad a_2=\quad;\quad a_3=\ast\ast\quad;\quad a_4=\quad;\quad a_5=\astDie aia_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 kk und die Anzahl der Semikolons ist für jedes Tupel gleich (n1)(n-1).

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

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

Avatar von 153 k 🚀
0 Daumen

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 did_i wie folgt beschrieben:

1d1a1d2a2dkakdk+1n1 \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:

0din10\leq d_i \leq n-1 und d1++dk+1=n1\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 (n1+kk)\binom{n-1+k}{k} solcher Differenzfolgen gibt.

Avatar von 12 k

Ein anderes Problem?

Stell deine Frage