Kombinatorika feladat?

Nézzük meg egy konkrét számra, például n=10-re.

-Nem tudom, hogy a feladat szempontjából a 0 ember kiválasztása lehetőségnek számít-e, de ha számít, akkor az 1 lehetőség.

-Ha 1 embert választunk ki, akkor triviális okokból 10 jön ki, de úgy is kijön, hogy (10 alatt az 1), ennek később lesz jelentősége.

-Ha 2 embert választunk ki, akkor a következőképpen gondolkozhatunk; minden kiválasztáshoz kölcsönösen egyértelműen hozzárendelhető egy 2 darab X-ből és 8 darab O-ból álló kódsor, ahol az X a kiválasztott, az O a nem kiválasztott embereket jelöli. Például az OOXOOOOOXO kód azt mutatja meg, hogy a 3. és a 9. embert választottuk ki. Ezeket a kódokat kellene összeszednünk, pontosabban azokat, amelyekben a két X nincs egymás mellett.

Először írjuk le a két X-et, de valaki biztosan szétválasztja őket, ezért tegyünk egy O-t közéjük, ekkor ennyi van leírva: XOX. A maradék 7 embert, akiket O-kkal jelölünk, a társaságba kell tennünk. Lehet őket az első X elé, a második X után, vagy közéjük tenni. A további emberek berakása összegben mindig 7 kell, hogy legyen, emiatt ezeket az eseteket aszerint tudjuk összeszedni, hogy a 7-et hányféleképpen lehet nemnegatív egész számok összegeként felírni úgy, hogy a számok sorrendje számít. Tehát van 7 darab O, amik közé két elválasztást kell tennünk, ezt (9 alatt a 2)-féleképpen tudjuk megtenni. Tehát (9 alatt a 2) olyan eset van, amikor két embert megfelelően választunk ki.

-Ha 3 embert választunk, akkor XOXOX-szel kezdhetünk, marad 5 ember, akiket 4 helyre kell szétosztanunk 3 elválasztással, itt a lehetőségek száma (8 alatt a 3) lesz.

-Ha 4 embert kell kiválasztanunk, akkor XOXOXOX, a megmarad 3 embert kell 5-felé osztanunk 4 elválasztással, így (7 alatt a 4)-féleképpen tudunk eljárni.

-Ha 5 embert kerül kiválasztásra, akkor XOXOXOXOX sorral kezdünk, az utolsó ember ránézésre 6-féleképpen tudjuk elhelyezni, egyébként (6 alatt az 5)-féleképpen.

-Ha 5-nél több embert választunk, akkor (a skatulya-elv értelmében) biztosan lesz két szomszédos.

Ennyiből már lehet látni a számítási sémát; ha n emberünk van, és k embert választunk ki, akkor azt

(n+1-k alatt a k)

-féleképpen tudjuk megtenni, amennyiben 0<=k<=n+1-k, ha pedig k>n+1-k, vagyis k>(n+1)/2, akkor a lehetőségek száma 0.

A körasztalost egyelőre passzolom.