students with different names are forming a circle and standing toward the center of the circle. Initially name tags of the students are distributed to them at random. The students repeat the following process:
[process] Every student having one's own name tag gets out of the circle, and the remaining students pass their name tags to the right.
Find the number of initial distributions of name tags such that some students still remain after 4 processes.
Solution
Let be a finite set of positive integers and be a permutation (=bijection) on . A pair is called a "up" if holds, and is defined by the number of up's in .
Given a permutation on , define a permutation by
where means the functional composition. Then we can easily deduce the following lemma.
Lemma. Let be a permutation on without fixed points. Then we have
Let be the set of students and be the set of name tags. A distribution of name tags can be interpreted as a bijection . By simplifying to , we can regard as a permutation on . Let be the set of fixed points of . Define and . Then represents the state after the exit of each student having one's own name tag. It is obvious that . Also we can easily deduce the following:
Given a distribution , passing their name tags to the right derives a distribution .
Therefore is the distribution after one process. By the lemma we have
Thus, with a single process, the number of up's is decreased by 1. Thus if an initial distribution has at most 3 up's then every student has one's own name tag during 3 processes, i.e., every student gets out of the circle until 4 processes. Therefore the answer of this problem is
where is the set of permutations on .
Let be the set of and . By considering the position of in , we can easily deduce the following recurrence relation:
with and for . For we have
The recurrence relation yields . For we have
The recurrence relation yields . Finally, for , we have
The recurrence relation yields . Therefore the answer of this problem is