Santa Claus — modified 2021-11-29 14:40 (402 days ago) — edit — reply
Žádné liché kružnice v grafu nenalezneme, protože jinak by graf nebyl bipartitní.
Na nule nebo dvou vrcholech kružnice neexistují.
Spočítejme kružnice na počtech vrcholů, které jsou sudými čísly $\geq 4$
Označme si vrcholy grafu $\color{blue}{1}, \color{blue}{2}, ... \color{blue}{n}$ v jedné partitě a $\color{red}{1}, \color{red}{2}, ... \color{red}{n}$ v druhé.
Každou kružici můžeme pak zapsat v takovémto formátu:
$\color{blue}{v_1}, \color{red}{v_2}, \color{blue}{v_3}, ..., \color{red}{v_m}$,
kde $2d$ je délka kružnice. To lze interpretovat jako dvě permutace: $d$ vrcholů z první partity a $d$ vrcholů z druhé partity.
Uvědomme si ale, že tímto způsobem máme přo každou kružnici několik zápisů:
+ zápis můžeme otočit (místo $\color{blue}{v_1}, \color{red}{v_2}, \color{blue}{v_3}, ..., \color{red}{v_m}$ napsat $\color{blue}{v_1}, \color{red}{v_m}, ..., \color{blue}{v_3}, \color{red}{v_2}$). Pro každou kružnici tak máme zatím dva zápisy.
+ zápis můžeme přerotovat (jako binární operace rotování), a bude tvořit stejnou kružnici. každý zápis je tak ekvivalentní $d - 1$ dalším zápisům.
Dohromady každou kružnici popíšeme $2d$-krát.
Počet zápisů pak spočeteme jako součin počtů permutací:
$\# \text{ zápisů délky 2d } = \binom{n}{d} \cdot \binom{n}{d} \cdot d! \cdot d! = \left(\frac{n!}{(n-d)!}\right)^2$
$\# \text{ kružnic délky 2d } = \frac{\# \text{ zápisů }}{\# \text{ zápisů jedné kružnice }} = \frac{\left(\frac{n!}{(n-d)!}\right)^2}{2d}$
Polovina délky kružnice $d$ může nabývat hodnot $2$ až $n$.
Celkový počet kružnic:
$\# \text{ počet kružnic } = \displaystyle\sum_{d=2}^n \frac{\left(\frac{n!}{(n-d)!}\right)^2}{2d} =\frac{n!^2}{2}\sum_{d=2}^n \frac{1}{d(n-d)!^2}$