While working on another problem, I found the following combinatorial equality, but I got it analytically, and I'm curious to find a counting argument.

Fix $n$ a positive integer. For $n_1\leq n_2\leq \cdots \leq n_k$ with $\sum n_i=n$, let $s_{n_1,\dots,n_k}$ be the number of permutations in $\Sigma_n$ with sorted cycle lengths $n_1,n_2,\dots,n_k$.

Then show:

$$\sum_{n_1,\dots,n_k} 4^{k-1}s_{n_1,\dots,n_k}=n\cdot n!$$

where the sum is restricted to the case where all $n_i$ are odd.

I suppose we could just write $t_k$ as the number of permutations in $\Sigma_n$ composted of $k$ odd cycles, and write it as $\sum_{k} 4^{k-1}t_k = n\cdot n!$.

For example, for $n=5$, the possible permutations of signature $s_{5}=4!$, $s_{1,1,3}=2\binom{5}{2}=20$, $s_{1,1,1,1,1}=1$ so the sum is:

$$4^0\cdot24+4^2\cdot 20 + 4^4\cdot 1=600=5\cdot 5!$$

I have a proof of this, which is gross - it involves substituting the power series for $\theta=\arctan x$ into the power series for $\sin 4\theta$ and $\cos 4\theta$ (for odd and even $n$, respectively.) That seems unpleasant, so I am seeking a more direct combinatorial argument.

One thing I considered was the possibility of using the identity:

$$\sum_{n=0}^{m} n\cdot n! =(m+1)!-1$$


Permutations with odd cycles only and cycle count marked have the species

$$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{=1}(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_{=3}(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_{=5}(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_{=7}(\mathcal{Z}) + \cdots).$$

which yields the EGF

$$G(z,u) = \exp\left(uz+ u\frac{z^3}{3}+ u\frac{z^5}{5}+ u\frac{z^7}{7}+\cdots\right) \\ = \exp\left(u\sum_{k\ge 0}\frac{z^{2k+1}}{2k+1}\right) \\ = \exp\left(u\log\frac{1}{1-z} - u\sum_{k\ge 1} \frac{z^{2k}}{2k}\right) \\ = \exp\left(u\log\frac{1}{1-z} - u\frac{1}{2}\log\frac{1}{1-z^2}\right).$$

Now here we have $u=4$ so we continue with

$$\frac{1}{(1-z)^4} \exp\left(2\log(1-z^2)\right) = \frac{(1-z^2)^2}{(1-z)^4} = \frac{(1+z)^2}{(1-z)^2} \\ = (1+2z+z^2) \frac{1}{(1-z)^2}.$$

We get as our result the quantity

$$\frac{1}{4} n! [z^n] G(z, 4) = \frac{1}{4} n! \left({n+1\choose 1} + 2{n\choose 1} + {n-1\choose 1}\right) \\ = \frac{1}{4} n! (n+1+2n+n-1) = n! \times n.$$

| cite | improve this answer | |
  • $\begingroup$ That first step is much like my first step - I was using $z=ix$ so $\sum z^{2k+1}/(2k+1)=i\arctan x$. It's still not quite a "counting argument" as I wanted. $\endgroup$ – Thomas Andrews Apr 5 '16 at 21:01
  • $\begingroup$ I did notice that $\arctan(iz)/i$ appears here so possibly the above would not be considered a combinatorial proof. Let's hear what the combinatorial wizards have to say. $\endgroup$ – Marko Riedel Apr 5 '16 at 21:05
  • 3
    $\begingroup$ It's still a nice answer, and comes up with a more general formula with $4$ replaced by $2j$ - then the coefficient is always $n!$ times a polynomial of degree $j$ in $n$. $\endgroup$ – Thomas Andrews Apr 5 '16 at 21:39
  • 1
    $\begingroup$ If I go to the last expression prior to subbing $u=4$, it seems that $$\log\frac{1}{1-z}- \frac{1}{2}\log\frac{1}{1-z^2}=\frac{1}{2}\log\frac{1+z}{1-z}$$ and so one can simplify to $G(z,u)=\left(\frac{1+z}{1-z}\right)^{u/2}$. This also agrees with the $u=4$ case, and seems a bit simpler in statement. $\endgroup$ – Semiclassical Apr 5 '16 at 22:18

I am going to introduce a fancy structure, that is a coloured permutation.

A coloured permutation $\sigma$ is a permutation acting on $\{1,2,\ldots,n\}$, with the property that every element has an odd order. Moreover, the elements of $\{1,\ldots,n\}$ are coloured with some colour from $\{\text{cyan},\text{magenta},\text{yellow},\text{black}\}$ and the permutation is colour-preserving, i.e. the colour of $\sigma(a)$ is the same as the colour of $a$. We want to count the number of coloured permutations, given by: $$ L_n=\!\!\!\!\sum_{\substack{n_1,\ldots,n_k \text{ odd}\\ n_1+\ldots n_k=n}}\!\!\! 4^k\cdot s_{n_1,\ldots,n_k}.$$

Preliminary lemma: the number of permutations of $\{1,\ldots,k\}$ such that every element has an odd order is given by: $$ C_k = k!\cdot [x^k]\frac{1}{1-x}\cdot\exp\left(-\frac{x^2}{2}-\frac{x^4}{4}-\ldots\right)= k!\cdot [x^k]\sqrt{\frac{1+x}{1-x}}. $$

Consequence: the number of coloured permutations is given by $$ \sum_{c+m+y+k=n}\binom{n}{c}\binom{n-c}{m}\binom{n-c-m}{y} C_c C_m C_y C_k = n!\cdot [x^n]\left(\frac{1+x}{1-x}\right)^2=4n\cdot n!.$$

Done. Double counting wins again.

Another chance would be given by showing that $L_{n+1}-L_n = (n+1)!-n!$ by some recursive argument. However, I was not able to find it.

| cite | improve this answer | |
  • $\begingroup$ This is nice work (+1) even though it uses the same EGF for the $C_k$ as I have in my answer. A colored permutation must have the color constant on its cycles so we get the number of possible colorings as $4^k$ with $k$ the number of cycles and from this point on you could continue as in my proof. $\endgroup$ – Marko Riedel Apr 5 '16 at 23:17
  • $\begingroup$ @MarkoRiedel: I have to say there aren't many differences between your solution and mine, beyond the phrasing. I still have the strong feeling that we are missing something really tricky that is able to show $L_{n+1}-L_n=(n+1)!-n!$ in a few lines. $\endgroup$ – Jack D'Aurizio Apr 5 '16 at 23:20
  • $\begingroup$ Maybe something like: if $\sigma\in S_n$ has order $2^m\cdot d$, by squaring $\sigma$ $m$ times we get an element with an odd order, that is associated with certain coloured permutations. But then? $\endgroup$ – Jack D'Aurizio Apr 5 '16 at 23:23
  • 1
    $\begingroup$ Addendum. What you have presented here is the combinatorial species $$\mathfrak{P}(\mathfrak{C}_{\mathrm{odd}}(\mathcal{Z})) \mathfrak{P}(\mathfrak{C}_{\mathrm{odd}}(\mathcal{Z})) \mathfrak{P}(\mathfrak{C}_{\mathrm{odd}}(\mathcal{Z})) \mathfrak{P}(\mathfrak{C}_{\mathrm{odd}}(\mathcal{Z}))$$ which is a perfectly valid approach to the problem and a genuine alternative to what I submitted. $\endgroup$ – Marko Riedel Apr 5 '16 at 23:57

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.