Liczba podzbiorów

[Macies]

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

[mol_ksiazkowy]

wsk \(\displaystyle{ {n-k+1 \choose k} = f(n,k)}\)
udowodnić że
\(\displaystyle{ f(n,k)= f(n-1, k) + f(n-2, k-1)}\)

[arek1357]

Nie bardzo to rozumiem

weź np: \(\displaystyle{ n=5,k=3}\)

i co ci wyjdzie:

\(\displaystyle{ {5-3+1 \choose 3} =1}\)

I co to jest ? chyba że ja źle to interpretuję!



Ale ja mam inną propozycję, niech to zadanie spełnia ciąg :

\(\displaystyle{ a(n,k)}\)

zauważ:

\(\displaystyle{ a(n,1)=0}\)

\(\displaystyle{ a(n,n)=1}\)

\(\displaystyle{ a(n,2)=1}\)

ogólnie:

\(\displaystyle{ a(n+1,k+1)=a(n,k+1) \cdot k+a(n,k)}\)

przykłady:

\(\displaystyle{ \left\{ 1,2,3,4\right\}}\)

mamy: \(\displaystyle{ n=4,k=3}\)


\(\displaystyle{ \left\{ 2,4\right\} \left\{ 1\right\} \left\{ 3\right\}}\)

\(\displaystyle{ \left\{ 1,3\right\} \left\{ 2\right\} \left\{ 4\right\}}\)

\(\displaystyle{ \left\{ 1,4\right\} \left\{ 2\right\} \left\{ 3\right\}}\)

trzy możliwości , ze wzoru:

\(\displaystyle{ a(4,3)=a(3,3) \cdot 2+a(3,2)=1 \cdot 2+1=3}\)

podobnie:

\(\displaystyle{ a(5,3)=a(4,3) \cdot 2+a(4,2)=3 \cdot 2+1=7}\)

co też zgadza się z doświadczeniem

\(\displaystyle{ a(6,3)=15}\)

co też się zgadza