Let $n \ge 2$ be an integer. There are $n$ beads numbered $1, 2, \ldots, n$. Two necklaces made out of some of these beads are considered the same if we can get one by rotating the other (with no flipping allowed). For example, with $n \ge 5$, the necklace with four beads $1, 5, 3, 2$ in the clockwise order is same as the one with $5, 3, 2, 1$ in the clockwise order, but is different from the one with $1, 2, 3, 5$ in the clockwise order. We denote by $D_0(n)$ (respectively $D_1(n)$) the number of ways in which we can use all the beads to make an even number (resp. an odd number) of necklaces each of length at least $3$. Prove that $n - 1$ divides $D_1(n) - D_0(n)$.
Problem
Source: Indian IMOTC 2013, Team Selection Test 1, Problem 1
Tags: counting, derangement, function, combinatorics proposed, combinatorics, permutations, Permutation cycles
31.07.2013 02:40
Derangements would be permutations with all cycles of length at least 2; this question asks about all permutations with cycles of length at least 3. At first glance the problem looks like it could be very interesting, but actually to get the desired result requires only a tiny amount of analysis. Let us count the contribution to $D_1(n + 1)$ (respectively, $D_0(n + 1)$) that comes from permutations in which the entry 1 appears in a cycle of length $k + 1$. There are $\binom{n}{k}$ ways to choose the other entries to go in this cycle and $k!$ ways to choose which cycle to make with the $k + 1$ selected entries. Then the remaining $n - k$ entries must also be divided into cycles. If the result is to have an odd (respectively, even) number of cycles, then the remaining entries must be divided into an even (respectively, odd) number of cycles. Thus, \[ D_1(n + 1) = \sum_{k = 2}^n \binom{n}{k} k! D_0(n - k) \] and \[ D_0(n + 1) = \sum_{k = 2}^n \binom{n}{k} k! D_1(n - k). \] Taking the difference of these two equations and rewriting $\binom{n}{k} k! = \frac{n!}{(n - k)!}$, we have \[ D_1(n + 1) - D_0(n + 1) = \sum_{k = 2}^n \frac{n!}{(n - k)!} (D_0(n - k) - D_1(n - k)). \] Since $k \geq 2$, the first factor in each summand is divisible by $n$, while the second factor is an integer. So we have a sum of numbers divisible by $n$, which is certainly divisible by $n$. (Actually, we get for free from this argument that the difference $D_1(n + 1) - D_0(n + 1)$ is divisible by $n(n - 1)$.)
31.07.2013 02:51
Let $a_n = D_1(n) - D_0(n)$. Just to make sure I understand the problem correctly, I get $a_3 = 2$, $a_4 = 6$, $a_5 = 24$, and $a_6 = 80$. Are those values correct?
31.07.2013 02:58
That agrees with my understanding. (For $D_1(n)$ I have 0, 0, 0, 2, 6, 24, 120, 720, 5040, 42560, 413280 and for $D_0(n)$ I have 1, 0, 0, 0, 0, 0, 40, 420, 3948, 38304, 396576 as $n$ goes from 0 to 10.) I guess I should also say that throughout my solution I was using the identification "a division of the beads 1 to $n$ into some number of cycles" with "a permutation of length $n$, given in cycle notation," though of course the counting argument works just as well if one wants to go put the words "beads" and "necklaces" where I've put "entries" and "cycles." Also FWIW, I think that the generating functions for the two series are \[ \sum_{n \geq 0} D_0(n) \frac{x^n}{n!} = \frac{1}{2}\left(\frac{\exp\left(-\frac{x(x + 2)}{2}\right)}{1 - x} + (1 - x)\exp\left(\frac{x(x + 2)}{2}\right)\right) \] and \[ \sum_{n \geq 0} D_1(n) \frac{x^n}{n!} = \frac{1}{2}\left(\frac{\exp\left(-\frac{x(x + 2)}{2}\right)}{1 - x} - (1 - x)\exp\left(\frac{x(x + 2)}{2}\right)\right), \] if I haven't made any errors. (One can derive this from the recursions by solving a differential equation.)
31.07.2013 17:30
Then I conjecture that $a_n = (n - 1)(n - 2) b_{n - 3}$, where $b_n$ is the number of involutions on $n$ elements.
31.07.2013 19:29
Good conjecture: we can extract it from the GFs I gave, since taking the difference gives \[ A(x) = \sum_{n \geq 0} a_n \frac{x^n}{n!} = (x - 1)\exp\left(x + \frac{x^2}{2}\right). \] Your conjecture is equivalent to $A'(x) = x^2 \sum_{n \geq 0} b_n \frac{x^n}{n!}$; this is easy to check using the known GF $\sum_{n \geq 0} b_n \frac{x^n}{n!} = \exp\left(x + \frac{x^2}{2}\right)$. But obviously this is not totally satisfactory (for one thing, I've just pulled the GFs for $D_1$, $D_0$ out of thin air); a combinatorial proof would be nice.