Počet kružnic v úplném grafu
Úloha číslo: 3650
Určete, kolik různých kružnic (všech možných délek) obsahuje úplný graf \(K_n\). Výsledek vyjádřete pomocí sumy.
Řešení
Nechť \(k\in\{3,\dots,n\}\) je délka cyklu. Vybereme vrcholy cyklu - to lze provést \(\binom{n}{k}\) způsoby. Jeden vrchol zvolíme libovolně, jeho následníci tvoří permutaci na \(k-1\) vrcholech. Stejný cyklus lze projít dvěma směry, proto je započten dvakrát.
Odpověď
Kružnic je \( \sum\limits_{k=3}^n \binom{n}{k} \frac{(k-1)!}2 \).
