Liczba podzbiorów k elementowych.

[nemoqwe08]

Mam problem z zadaniem,

Znaleźć liczbę podzbiorów k-elementowych zbioru \(\displaystyle{ {1,2,...,n}}\) nie zawierających żadnej pary kolejnych liczb

Nie do końca wiem jak za to zadanie się zabrać, bo liczba par kolejnych liczb to \(\displaystyle{ n-1}\), a odpowiedź \(\displaystyle{ {n \choose k} - (n-1)}\) raczej jest błędna

[Medea 2]

Wyobraź sobie przypadek \(\displaystyle{ n = 7}\), \(\displaystyle{ k = 3}\). Chcesz zliczać ciągi zer i jedynek długości \(\displaystyle{ n}\), w których jest \(\displaystyle{ k}\) niesąsiadujących jedynek. W takich ciągach jest \(\displaystyle{ n-k}\) zer, czyli \(\displaystyle{ n - k +1}\) przerw, w które można dopisać jedynkę (po jednej przed każdym zerem, jedna dodatkowa za ostatnim).

[nemoqwe08]

czyli będzie \(\displaystyle{ {n-k+1 \choose k}}\) ?

[Medea 2]

Tak, dokładnie tyle.