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.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze