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.

Difficulty level: Easy task (using definitions and simple reasoning)
Routine calculation training
Cs translation
Send comment on task by email