14
$\begingroup$

It is obvious that $\sum_{p \in S_n} 1=n!$ because it is just counting how many permutations there are of $n$ symbols.

But I have also observed that $\sum_{p \in S_n} 2^{c(p)}=(n+1)!$, where $c(p)$ is the number of cycles of $p$.

What is the combinatorial interpretation of this identity?

An example. In $S_3$ we have one permutation with 3 cycles, three permutations with 2 cycles and two with 1 cycle. Then $1\times 2^3+3\times 2^2+2\times 2^1=24=4!$

$\endgroup$
14
  • $\begingroup$ What do you mean by the number of cycles of $p$? $\endgroup$
    – Rob Arthan
    Jan 31 '20 at 21:02
  • $\begingroup$ @RobArthan When a permutation acts on the set $\{1,...,n\}$ it will have invariant subsets where its action is transitive. These are the cycles. $\endgroup$
    – thedude
    Jan 31 '20 at 21:03
  • 1
    $\begingroup$ Take any permutation in $S_n$. Try to create a permutation in $S_{n+1}$. You need to add $n+1$. You want a scheme of adding $n+1$ so that it is a distinct permutation. For each cycle, you either include $n+1$ or you don't (possibly merging cycles). My guess would be that there is a scheme where this produces a distinct element of $S_{n+1}$. $\endgroup$ Jan 31 '20 at 21:06
  • 2
    $\begingroup$ This answer generalises your result. $\endgroup$
    – Milten
    Jan 31 '20 at 21:10
  • 1
    $\begingroup$ This also has a probabilistic interpretation - if $\sigma$ is a random permutation in $S_n$, then $E(2^{c(\sigma)}) = n+1$ $\endgroup$ Jan 31 '20 at 21:52
11
$\begingroup$

It can be seen as an application of Pólya's enumeration theorem.

Let us take $n$ beads and colour each of them black or white. We consider two colourings equivalent, if there are the same number of black and white beads. That is, if some permutation $\sigma\in S_n$ takes one of the colourings to the other. It is clear that there are then $n+1$ distinct colourings (since there can be $0,1,\ldots, n$ black beads). Pólya's theorem then says that: $$ n+1 = \frac{1}{|S_n|}\sum_{\sigma\in S_n}2^{c(\sigma)} = \frac{1}{n!}\sum_{\sigma\in S_n}2^{c(\sigma)} $$ The $2$ in the formula is the number of colours.

I guess this is somewhere between a combinatorial interpretation and just a proof... Depends on your attitude towards Pólya's theorem I guess.

EDIT: Let me just include the immediate generalisation. If we have $m$ colours, then there are $\binom{n+m-1}{n}$ different colourings (by stars and bars). So: $$ \sum_{\sigma\in S_n}m^{c(\sigma)} = n!\binom{n+m-1}{n} = \frac{(n+m-1)!}{(m-1)!} = m(m+1)\cdots(n+m-1) $$ This only works for $m\in\mathbb N$ of course. But as WE Tutorial School points out in a comment, this shows that the left and right hand sides are equal as polynomials in $m$, so the identity is proved for any value of $m$ (even complex and whatnot).

$\endgroup$
9
$\begingroup$

The sum in question counts the number of pairs $(f, p)$ where $f$ is a function from $\{1, 2, \dots, n\}$ to $\{1, 2\}$, and $p \in S_n$ such that $f \circ p = f$. I don't know if there is an easy way to see that this is equal to $(n + 1)!$, but here is an approach:

First let's verify that the sum does actually count what I say that it does. Suppose that we have already chosen the permutation $p$. A function $f$ satisfies the conditions above if and only if for each cycle of $p$, we have that $f$ maps every element of that cycle to the same element of $\{1, 2\}$. We can thus determine $f$ by choosing the image of each cycle, and there are two options for the image of each cycle, giving us $2^{c(p)}$ functions in total.

Let's now instead determine the sum by counting the pairs $(f, p)$ such that there are $k$ elements of $\{1, 2, \dots, n\}$ that are mapped to $1$ under $f$. There are $\binom{n}{k}$ ways to choose which $k$ elements these are. There are then $k!$ ways to choose how $p$ permutes these $k$ elements, and $(n - k)!$ ways to choose how $p$ permutes the remaining elements. This gives us $\binom{n}{k} k! (n - k)! = n!$ ways to choose the pair $(f, p)$. Noting that $k$ can take any value from $0$ to $n$, this gives us $(n + 1) n! = (n + 1)!$ pairs in total.

$\endgroup$
4
  • $\begingroup$ I hadn't heard of Polya's Enumeration Theorem before, but now that I have, I think that this may be essentially the same solution as @Milten's. $\endgroup$
    – Dylan
    Jan 31 '20 at 22:03
  • 2
    $\begingroup$ For your last paragraph, suppose that $f^{-1}(1)=\{x_1,x_2,\ldots,x_k\}$ and $f^{-1}(2)=\{y_1,y_2,\ldots,y_l\}$ with $x_1<x_2<\ldots<x_k$ and $y_1<y_2<\ldots<y_l$. There is a $1$-$1$ correspondence between the pairs $(f,p)$ and the permutations of $(0,1,2,\ldots,n)$ by taking $$(f,p)\mapsto \big(p(x_1),p(x_2),\ldots,p(x_k),0,p(y_1),p(y_2),\ldots,p(y_l)\big).$$ This is an alternative way to show that there are $(n+1)!$ pairs $(f,p)$. $\endgroup$ Jan 31 '20 at 22:36
  • 2
    $\begingroup$ If I am not mistaken, your proof also shows that $$\sum_{p\in S_n} r^{c(p)}=\frac{(n+r-1)!}{(r-1)!}$$ for all non-negative integer $r$. Hence, it follows that $$\sum_{p\in S_n} x^{c(p)} =x(x+1)(x+2)\cdots (x+n-1)$$ as a polynomial identity. $\endgroup$ Jan 31 '20 at 22:47
  • 1
    $\begingroup$ @Dylan Indeed it seems we had pretty much the same idea. I think you basically proved Pólya's theorem in your answer. I would say yours is probably cleaner as a combinatorial proof though :) $\endgroup$
    – Milten
    Feb 1 '20 at 9:16
8
$\begingroup$

The combinatorial class of permutations with the number of cycles marked is

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}( \mathcal{U} \times \textsc{CYC}_{=1}(\mathcal{Z}) + \mathcal{U}\times \textsc{CYC}_{=2}(\mathcal{Z}) + \mathcal{U}\times \textsc{CYC}_{=3}(\mathcal{Z}) + \cdots).$$

This gives the EGF

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

A permutation on $n$ elements and having $k$ cycles is represented by $u^k \frac{z^n}{n!}.$ For the sum we set $u=2$ and obtain

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

We then get for the answer

$$n! [z^n] H(z) = n! [z^n] \frac{1}{(1-z)^2} = n! {n+1\choose 1} = (n+1)!.$$

This is the claim.

Addendum. With two being replaced by $m$ we obtain

$$n! [z^n] H(z) = n! [z^n] \frac{1}{(1-z)^m} = n! \times {n+m-1\choose m-1} = n! \times {n+m-1\choose n}.$$

$\endgroup$
1
  • $\begingroup$ I apologise for using comments in this unintended way, but: I just wanted to tell you that this answer inspired me to begin reading Analytic Combinatorics by Flajolet & Sedgewick. I am now 200 pages deep and I love it. I had never heard of these methods before, so thank you :) $\endgroup$
    – Milten
    Sep 3 '20 at 9:05

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.