Počet SRR (n-1)-prvkových množin
Úloha číslo: 3767
Uvažujme systém všech \((n-1)\)-prvkových podmnožin množiny \(\{1,\ldots,n\}\). Kolik má systémů různých reprezentantů?
Řešení
Označme \(A_i=\{1,\ldots,n\}\setminus i\). Zřejmě každý systém různých reprezentantů, kde množinu \(A_i\) reprezentujeme prvkem \(r(A_1)\in A_i\) odpovídá permutaci \((r(A_1),r(A_2),…,r(A_n))\) bez pevných bodů a vice versa.
Odpověď
Tento množinový systém má \(\check{s}(n)\) různých SRR, kde \(\check{s}(n)\) je řešení problému šatnářky.