Task list filter?
Choose required ranks and required tasks. The table of contents will list only tasks having one of the required ranks in corresponding rankings and at least one of the required tags (overall). If you wish to filter only according to some rankings or tags, leave the other groups empty.
Task rankings
Difficulty level
Task tags
Task type
«
«
Cycles in complete bipartite graph
Task number: 4198
Show that the number of cycles in the complete bipartite graph Kn,n is \displaystyle \sum_{k = 2}^ n \binom{n}{k}^2 \frac{k! (k-1)!}{2} .
Solution
The term \binom{n}{k} corresponds to the selection of vertices from one part. It is in the square root because we choose independently from both parts.
If we choose one vertex arbitrarily, its successors from the same part form a permutation on k-1 vertices, while from the other on k vertices. The same cycle can be traversed in two directions, so it is counted twice.
