Počet daných podgrafů
Úloha číslo: 4526
Varianta
Kolik obsahuje cest?Řešení
Počáteční vrchol cesty o \(k\) vrcholech můžeme zvolit \(n\) způsoby, jeho souseda \(n-1\) způsoby atd., což dává celkem \(n(n-1)\ldots(n-k+1) = n^\underline{k}\) způsobů. Tak každou cestu započítáme dvakrát (jednou za každý koncový vrchol), jen cestu o jednom vrcholu jednou.
Sečtením přes všechny možné délky cest dostaneme: \[n + \frac12\cdot\sum_{k=2}^{n} n^\underline{k}\]
Stejného výsledku můžeme také dosáhnout tak, že uvážíme \(n\choose k\) možných výběrů vrcholů cesty a \(k!\) způsobů, jak vrcholy na cestě uspořádat. Opět pro \(k>1\) započítáme každou cestu dvakrát. Dostaneme proto výraz: \[n + \frac12\cdot\sum_{k=2}^{n} {n\choose k}\cdot k!\]
Varianta
Kolik obsahuje kružnic?Řešení
Počítejme kružnice konkrétní délky \(k\ge 3\). Existuje \(n\choose k\) možností, jak vybrat vrcholy kružnice. Kdybychom zvolili jeden z vrcholů jako počáteční a zvolili směr procházení kružnice, můžeme \(k\) vrcholů projít \(k!\) způsoby. To vydělíme \(k\) možnostmi, jak zvolit počátek, a \(2\) možnými směry procházení. Nakonec sečteme přes všechna možná \(k\) a dostaneme: \[ \sum_{k=3}^n \frac{{n\choose k} \cdot k!}{2k} = \frac12 \cdot \sum_{k=3}^n \frac{n^\underline{k}}{k} \]
