Suppose there is a group of $n$ people giving gifts to one another. Everybody brings a gift but we want the gifts to be "well-distributed" in the group. By this I mean the following:

In how many ways can the gifts be given such that - nobody receives their own gift, and in addition - there is no $k$-element subset of the $n$ people where the gifts are exchanged only among these $k$ people, except for $k=n$.

Let me put this in mathematical words:

Let $K_n$ be the complete graph on $n$ vertices, which are labeled with the numbers $1,..,n$. How many Hamiltonian cycles with a specified start vertex $i_1$ are there such that vertex $j$ is not reached at time $j$. I.e., I would like to count ordered sequences $(i_1, ..., i_n)$ with all $i_j\in\{i,..,n\}$ distinct and such that $i_j\neq j$, and the subgraph spanned by the edges $(i_1,1), (i_2,2), ..., (i_n, n)$ is a Hamiltonian path.

One could also express this in terms of group elements $w$ of $S_n$ acting transitively on $\{1,...,n\}$ when taken to powers $w^0$,$w^1,w^2,\dotsc$.

• You are asking how to count the number of derangements. Other questions on this subject can be found here: stackexchange.com/search?q=counting+derangements Edit: you may also find the following Wikipedia articles interesting: en.wikipedia.org/wiki/Derangement, en.wikipedia.org/wiki/Rencontres_numbers Mar 20 '18 at 12:37
• In terms of permutations, it seems you are looking for long cycles, and their number is simply (n-1)! Mar 20 '18 at 12:46
• Robin Saunders' comment answers the question, I think. Mar 20 '18 at 13:35
• I think derangements are something else. Mar 20 '18 at 17:33

Everybody sits down. The host initiates the exchange of gifts. He stands up and chooses one of the $(n-1)$ others to give his gift to. The person that received the gift stands up and gives his gift to someone who is currently sitting, then that person gets up, etc., until the last one stands up and gives his gift to the host. (If someone gave his gift to someone who was already standing at that time, then we'd have a 'sub-circle'.) The $i$-th person to stand up has $(n-i)$ people sitting to choose from. Hence in total, there are $(n-1)!$ ways this can go.