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

Improve this question
$\endgroup$
4

1 Answer 1

Reset to default
4
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you, yes indeed I only was asking for long cycles, as Philippe Nadeau pointed out. $\endgroup$
    – Petra Schwer
    Commented Mar 20, 2018 at 16:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .