Teilmengen ohne 2 aufeinander folgende Zahlen

25.11.2014, 08:45	dac	Auf diesen Beitrag antworten »
Teilmengen ohne 2 aufeinander folgende Zahlen Meine Frage: Guten Morgen! Gegeben ist die Menge {1, 2, ..., n}. Gesucht ist die Anzahl der k elementigen Teilmengen in denen keine zwei aufeinander folgenden Zahlen enthalten sind. Meine Ideen: Dir Anzahl aller k elementigen Untermengen ist $\begin{eqnarray} \begin{pmatrix} n\\ k \end{pmatrix} \end{eqnarray}$ . Ich suche Mengen K die die folgende Form haben: K={n1, ..., nk} Für die n habe ich mir folgendes überlegt: $\begin{eqnarray} 1\leq n_{1} <br /> n_{1}+1 < n_{2}<br /> n_{2}+1 < n_{3} <br /> .<br /> .<br /> .<br /> n_{k-1}+1 < n_{k} < n \end{eqnarray}$ Stimmt die Überlegung? Wie fasse ich das am schlausten in einen Binomialkoeffizienten? Korrektur aus zweitem Beitrag übernommen, zweiten Beitrag gelöscht, damit Antwortzähler auf Null steht. Steffen
25.11.2014, 09:21	HAL 9000	Auf diesen Beitrag antworten »
Es werden $\begin{align} (k-1) \end{align}$ "Lücken" zwischen den $\begin{align} k \end{align}$ ausgewählten Zahlen benötigt, um die die Grundmenge der wählbaren Zahlen letztendlich geschmälert wird. Das ergibt dann Auswahlanzahl $\begin{align} \binom{n-(k-1)}{k} = \binom{n-k+1}{k} \end{align}$ .
25.11.2014, 09:24	dac	Auf diesen Beitrag antworten »
Oh, vielen vielen Dank!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »