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 \).

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