Number of given subgraphs
Task number: 4534
Variant
How many paths does it contain?Solution
We can choose the initial vertex of a path with \(k\) vertices in \(n\) ways, its neighbors in \(n-1\) ways, and so on, giving a total of \(n(n-1)\ldots(n-k+1) = n^\underline{k}\) ways. So we count each path twice (once for each terminal vertex), only the path on a single vertex we count once.
Summing over all possible path lengths, we get: \[n + \frac12\cdot\sum_{k=2}^{n} n^\underline{k}\]
We can also achieve the same result by considering \(n\choose k\) possible choices of path vertices and \(k!\) ways to arrange the vertices on the path. Again, for \(k>1\) we count each path twice. Therefore, we get the expression: \[n + \frac12\cdot\sum_{k=2}^{n} {n\choose k}\cdot k!\]
Variant
How many cycles does it contain?Solution
We count cycles of a specific length \(k\ge 3\). There are \(n\choose k\) ways to select the vertices of the cycle. If we were to choose one of the vertices as the origin and choose the direction of traversal of the cycle, we can traverse \(k\) vertices in \(k!\) ways. We divide this by \(k\) possible ways to choose the origin, and by \(2\) possible traversal directions. Finally, we sum over all possible \(k\) to get: \[ \sum_{k=3}^n \frac{{n\choose k} \cdot k!}{2k} = \frac12 \cdot \sum_{k=3}^n \frac{n^\underline{k}}{k} \]
