Anz. k-elem. Teilmengen, Lücke < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:30 Di 07.11.2017 | | Autor: | Teufel |
Hi!
Zur Zeit beschäftigt mich folgende Frage: Angenommen man hat die Menge [mm] $\{1,\ldots, n\}$. [/mm] Auf wie viele Arten kann man $k$ Elemente daraus ziehen, sodass jedes der $k$ Elemente mindestens Abstand 1 zu den anderen hat? Also wie viele [mm] $\{x_1,\ldots, x_k\}\subseteq\{1,\ldots,n\}$ [/mm] mit [mm] $|x_i-x_j|>1 \forall i\not= [/mm] j$ gibt es?
Gibt es da eine geschlossene Formel für? Ich komme nur auf die Rekursionsgleichung mit [mm] $a_{2k,k}=1$ [/mm] und [mm] $a_{n,1}=n$.
[/mm]
[mm] $$a_{n,k}=\sum\limits_{i=2}^{n}a_{n-i,k-1}$$
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:51 Di 14.11.2017 | | Autor: | tobit09 |
Hi Teufel!
Ich komme (im Falle [mm] $n\ge2k-1$) [/mm] auf die gesuchte Anzahl gegeben durch den Binomialkoeffizienten [mm] $\binom{n-(k-1)}{k}$, [/mm] also der Anzahl der k-elementigen Teilmengen von [mm] $\{1,\ldots,n-(k-1)\}$.
[/mm]
Anschaulicher Erklärungsversuch dazu:
Die Teilmengen von [mm] $\{1,\ldots,n\}$, [/mm] die zwischen je zwei Elementen "mindestens ein Element Lücke" haben, erhält man, indem man von einer beliebigen k-elementigen Teilmenge $Z$ von [mm] $\{1,\ldots,n-(k-1)\}$ [/mm] ausgeht und hinter jedem der k-1 ersten Elemente von $Z$ eine "um 1 vergrößerte Lücke" einfügt, indem man Elemente von $Z$ durch größere Werte ersetzt.
Ich weiß nicht, ob diese Idee so verständlich wird.
Wenn nötig, muss ich sie formalisieren.
Viele Grüße
Tobias
|
|
|
|
