Úloha o hostech
Chystáme se řešit klasickou úlohu o hostech. K tomu účelu nejprve vyřešíme dvě pomocné úlohy.
Nechť a?, k jsou kladná celá čísla splňující k ^ n. Na přímce je vyznačeno n různých bodů. Zjistěte, kolika způsoby je možno mezi těmito body vybrat k bodů tak, aby žádné dva vybrané body nebyly sousední.
Po odstranění vybraných k bodů zůstane na přímce n — k bodů. Naši úlohu lze nyní přeformulovat jako problém, kolika způsoby lze do úseků přímky vyťatých zadanými n — k body rozmístit po jednom k nových, jinak označených bodů. Zadaných n — k bodů dělí přímku na n — k + 1 částí, lze tedy rozmístění nových bodů provést způsoby.
Nechť dále a?, k jsou kladná celá čísla splňující k < n. Na kružnici je vyznačeno n různých vzájemně odlišitelných bodů. Opět zjistěte, kolika způsoby je možno mezi těmito body vybrat k bodů tak, aby žádné dva vybrané body nebyly sousední.
Z podmínek úlohy plyne, že n ^ 2. Zvolme na kružnici mezi n vyznačenými body pevně dva sousední body /4, B. Rozlišíme možnosti:
• Není-li mezi vybranými k body bod a je nutno tyto body vybrat ze zbývajících n — 1 bodů, což podle předchozí úlohy lze učinit (n~kk) způsoby.
• Není-li mezi vybranými k body bod B, analogicky je možno takový výběr učinit (n~kk) způsoby.
• Oba předchozí případy v sobě ovšem zahrnují možnost, že mezi vybranými k body není ani bod A ani bod B. Tehdy musí být tyto body vybrány ze zbylých n — 2 bodů, což opět podle předchozí úlohy lze učinit (n~k~1) způsoby.
Celkem je tedy požadovaný výběr k nesousedních bodů mezi danými n navzájem odlišitelnými body vyznačenými na kružnici možno učinit
fn - k\     fn - k\ _ fn - k - l\     [n - k]k     [n - k\k _ [n - k - l]k \  k ) + \  k )    \     k     ) ~     k\ kl k\
= [n-k]k í _ n-2k\ = [n-k]k n k\     V      n-k ) k\    'n-k
_ n ín - k\ ~7^k'\  k )
způsoby.
Věnujme se nyní avizované úloze o hostech. Tato úloha je formulována následovně. Nechť a? je kladné celé číslo splňující n ^ 2. Na večírku se sejde n manželských párů. Zjistěte, kolika způsoby je možno rozesadit tyto hosty kolem kulatého stolu tak, aby se muži a ženy pravidelně střídali a aby žádní dva manželé neseděli vedle sebe.
Poznamenejme, že budeme předpokládat, že židle kolem stolu jsou od sebe navzájem odlišitelné. Budeme tedy rozlišovat mezi rozesazeními, z nichž jedno vznikne z druhého pootočením hostů kolem stolu. Pokud bychom takto nerozlišovali, vydělili bychom na závěr získaný výsledek číslem 2n.
Za uvedeného předpokladu existuje n\-2 možností, jak mohou být za stolem rozesazeni muži. Zvolme pevně jedno takové rozesazení. Řešíme nyní problém, kolika způsoby lze mezi tyto muže rozmístit ženy tak, aby dva manželé nikde neseděli vedle sebe. (Zřejmě tento počet rozmístění žen nezávisí na tom, jaké rozesazení mužů bylo předtím zvoleno.)
Buď Q množina všech myslitelných umístění žen na volné židle mezi muži. Kolem stolu je rozestavěno 2n židlí a mezi nimi je 2n mezer. Označme / množinu všech těchto mezer. Pro každou mezeru / G / označme A; množinu všech těch umístění žen na volná místa mezi muži, kdy na sousedních židlích kolem mezery / sedí manželé. Takže ta rozmístění žen, kdy žádní dva manželé nesedí vedle sebe, vytvoří množinu
A(0) = f](Q - A;)
iei
Podle principu inkluze a exkluze je tedy počet těchto rozmístění roven
\A(0)\ = £(-1)
K\
KCI
n a-
ieK
Obsahuje-li podmnožina KCI některé dvě sousední mezery, pak ovšem OieK^i = 0. neboť žádný z hostů nemůže mít u stolu manžela po obou stranách kolem sebe. Jestliže podmnožina KCI neobsahuje žádné dvě sousední mezery, pak nutně \K\ ^ n, v umístěních z f]ieKAj jsou místa \K\ žen určena pevně, totiž vedle jejich manželů v sousedství příslušné mezery, a zbývajících n — \ K\ žen lze umístit na zbylá volná místa libovolně, což lze učinit (n — \K\)\ způsoby, takže v tom případě
n a
ieK
(n- \K\)\
Toto číslo nezávisí na podmnožině K samotné, ale pouze na počtu mezer v podmnožině K. Přitom víme, že pro každé k = 0,1, 2,..., n počet všech těch /c-prvkových podmnožin KCI, které neobsahují žádné dvě sousední mezery, je podle předchozí pomocné úlohy roven číslu
2n (2n-k\ 2n-k'\   k J'
Využitím těchto poznatků v předchozím výše uvedeném vztahu pro |/4(0)| vychází
w»)i = Ď-^-
k=0
Tolik je tedy všech přípustných rozesazení žen, je-li předem zvoleno nějaké rozesazení mužů. Viděli jsme, že je možno předem zadat celkem n\-2 rozesazení mužů, takže dohromady dostáváme, že existuje
k=Q V 7
přípustných rozesazení hostů kolem kulatého stolu.