# Domácí úkol 6.4 - kruzKnn
Vrcholy v jedné partitě zakreslím v jednom řádku, partity označím $A/B$, vrcholy zleva $1...n$

Začnu od levého dolního vrcholu. K němu můžu přiřadit libovolný vrchol z horní partity, tzn. $n$ možností.
Další hrana pak vede z horní partity do dolní. Původní vrchol cílem být nemůže (nejednalo by se o kružnici). Mohu si vybrat z $n-1$ vrcholů.
Pro další horní vrchol mám opět $n-1$ možností, ale pro spodní vrchol nastávají dvě možnosti: mohu kružnici uzavřít (a vrátit se do výchozího vrcholu), nebo pokračovat dále (mám $n-2$ možností).
Dostáváme otázku, jakou délku mohou kružnice mít? Z popisu vyplývá, že nejkratší bude mít délku $4$ ($4$ vrcholy), nejdelší pak $2n$ (všechny vrcholy). Abych se mohl vrátit do počátečního vrcholu, musím se nejprve vrátit do horní partity, takže kružnice budou mít vždy *sudou* délku (nevyberu-li počáteční vrchol, pak musím vybrat jiný vrchol z dolní partity a další vrchol z horní partity).
Z kružnic stejné délky budou totožné jen ty, které jsem vytvořil v opačném pořadí (např. $1A - 1B - 2A - 2B - 1A = 1A - 2B - 2A - 1B - 1A$), takže výsledek musím vydělit dvěma.

Kružnice délky $4$: $n*n*(n-1)*(n-1)*1*\frac{1}{2}$
Kružnice délky $6$: $n*n*(n-1)*(n-1)*(n-2)*(n-2)*1*\frac{1}{2}$
...
Činitelé na lichých místech odpovídají spodní partitě (A), na sudých místech odpovídají horní partitě (B), "$*1$" vyjadřuje navrácení se do původního vrcholu.
Označíme-li délku jako $m$, pak platí: #$C_m$ = $(V_{n,\frac{m}{2}})^2*\frac{1}{2}$
Označíme:
$k = \frac{m}{2}$
$V_{n,k} = \frac{n!}{(n-k)!}$
Počet všech kružnic = $$\sum^{n}_{k=2}\frac{(n!)^2}{2*((n-k)!)^2}$$