1
$\begingroup$

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$.

$\endgroup$
4
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you, yes indeed I only was asking for long cycles, as Philippe Nadeau pointed out. $\endgroup$ Mar 20 '18 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.