Kružnice v úplném bipartitním grafu
Úloha číslo: 3649
Ukažte, že počet kružnic v úplném bipartitním grafu \(K_{n,n}\) je \(\displaystyle\sum_{k=2}^n \binom{n}{k}^2 \frac{k!(k-1)!}{2}\).
Řešení
Člen \(\binom{n}{k}\) odpovídá výběru vrcholů z jedné části. Je v druhé mocnině protože nezávisle vybíráme z obou částí.
Zvolíme-li jeden vrchol libovolně, tvoří jeho následníci ze stejné části permutaci na \(k-1\) vrcholech, zatímco z druhé na \(k\) vrcholech. Stejný cyklus lze projít dvěma směry, proto je započten dvakrát.