Jedno riešenie, ktoré sme spravili, bolo že sme našli rekurzívnu formulu a naznačili sme, že by sa to dalo dokončiť indukciou.Ukážte, že počet možností ako vybrať $k$-prvkovú podmnožinu z~$\{1,2,\dots,n\}$ tak, že nebude obsahovať susedné čísla, je práve $\binom{n-k+1}k$. (Hint 1: Chceme vlastne čísla $a_1,\ldots,a_k$ také, že $a_1<a_2-1$, $a_2<a_3-1$, atď. Hint 2: Dá sa úloha previesť nejako vhodne na počítanie riešení $x_1+x_2+\dots+x_k+x_{k+1}=n$ s nejakými vhodnými obmedzeniami. Hint 3: Ak máte nápad na nejaké celkom iné riešenie, nedajte sa pomýliť možnosťami naznačenými v predošlých dvoch hintoch.)
Okrem toho sa podarilo nájsť aj nejaké riešenie cez stars and bars a rozmysleli sme si dve riešenia naznačené v uvedených hintoch.
Pridám sem tri linky z Math Stack Exchange - najmä preto, že jedno z riešení na prvej linke (ktoré má aj pekný obrázok) sa asi vcelku podobá na riešenie s oddeľovačmi, ktoré ste navrhli na cviku - a možno niekomu obrázok pomôže, aby toto riešenie bolo jasnejšie.
- What is the number of ways to select ten distinct letters from the alphabet $\{a, b, c, \ldots, z\}$, if no two consecutive letters can be selected?
- Choosing numbers without consecutive numbers.
- Choosing books on a bookshelf where no two are consecutive