15
$\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, 2020 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, 2020 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$
    – SlipEternal
    Jan 31, 2020 at 21:06
  • 2
    $\begingroup$ This answer generalises your result. $\endgroup$
    – Milten
    Jan 31, 2020 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$
    – Michael Lugo
    Jan 31, 2020 at 21:52

3 Answers 3

Reset to default
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, 2020 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$
    – Batominovski
    Jan 31, 2020 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$
    – Batominovski
    Jan 31, 2020 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, 2020 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, 2020 at 9:05

You must log in to answer this question.

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