[Math] exponential generating functions containing an even/odd number of cycles

combinatoricsgenerating-functions

How to derive the exponential generating functions that having an even/odd number of cycles?
And how to define a bijection between them? Is there any example of this? Thanks in advance!

Best Answer

Minor correction to the answer by joriki, If you are counting permutations with an even number of cycles, then there is one for $n=0$ but not for $n=1$, and for odd number of cycles it is the opposite. Therefore for the even number of cycles you get $$ \frac12(1-x+\frac1{1-x}) = \frac12\times\frac{2-2x+x^2}{1-x} =1+\frac12(\frac{x^2}{1-x}), $$ and for odd numbers of cycles you get similarly $$ \frac12(-1+x+\frac1{1-x}) = \frac12\times\frac{2x-x^2}{1-x} =x+\frac12(\frac{x^2}{1-x}) . $$

Related Solutions

Combinatorics – Number of Cycles in Even and Odd Permutations of $[n]$

Here is an argument completely different from joriki’s; it is also a complete solution.

A cycle is an odd permutation iff its length is even, so a permutation written as a product of disjoint cycles is even iff an even number of the factors are even cycles. Let $\pi=\sigma_1\dots\sigma_k$ be a permutation of $[n]$ written as a product of $k$ disjoint cycles. Then $n=|\,\sigma_1|+\dots+|\,\sigma_k|$, so the parity of $n$ is the same as the parity of the number of cycles of odd length. Thus, $\pi$ has an even number of cycles of even length iff $n$ and $k$ have the same parity, i.e., iff $(-1)^{n+k}=1$.

Let $e_n$ be the total number of cycles in even permutations of $[n]$, let $o_n$ be the total number of cycles in odd permutations of $[n]$, and let $d_n=e_n-o_n$. The total number of permutations of $[n]$ with $k$ cycles is given by $\left[n\atop k\right]$, the unsigned Stirling number of the first kind. Each of these $\left[n\atop k\right]$ permutations contributes $k$ cycles to $e_n$ if $(-1)^{n+k}=1$, and to $o_n$ if $(-1)^{n+k}=(-1)$. Thus, each contributes $(-1)^{n-k}k$ to $d_n$, and it follows that

$$d_n=\sum_k(-1)^{n+k}k\left[n\atop k\right]\;.$$

Now $(-1)^{n+k}\left[n\atop k\right]=(-1)^{n-k}\left[n\atop k\right]$ is the signed Stirling number of the first kind, for which we have the generating function $$\sum_k(-1)^{n+k}\left[n\atop k\right]x^k=x^{\underline{n}}\;.\tag{1}$$

(Here $x^{\underline{n}}=x(x-1)(x-2)\cdots(x-n+1)$ is the falling factorial, sometimes written $(x)_n$.)

Differentiate $(1)$ with respect to $x$ to obtain

$$\sum_k(-1)^{n+k}k\left[n\atop k\right]x^{k-1}=Dx^{\underline{n}}=(x-n+1)Dx^{\underline{n-1}}+x^{\underline{n-1}}\;,$$

where the last step is simply the product rule, since $x^{\underline{n}}=x^{\underline{n-1}}(x-n+1)$. But $$Dx^{\underline{n-1}}=\sum_k(-1)^{n-1+k}k\left[{n-1}\atop k\right]x^{k-1}\;,$$ so

$$\sum_k(-1)^{n+k}k\left[n\atop k\right]x^{k-1}=\sum_k(-1)^{n-1+k}k\left[{n-1}\atop k\right]x^{k-1}+x^{\underline{n-1}}\;.\tag{2}$$

Now evaluate $(2)$ at $x=1$ to get $$d_n=(2-n)d_{n-1}+[n=1]\;,\tag{3}$$ where the last term is an Iverson bracket. If we set $d_0=0$, $(3)$ yields $d_1=[1=1]=1$, which by direct calculation is the correct value: the only permutation of $[1]$ is the identity, which is even and has one cycle. It’s now a trivial induction to check that $d_n=(-1)^n(n-2)!$ for all $n\ge 1$: the induction step is

$$\begin{align*}d_{n+1}&=\Big(2-(n+1)\Big)d_n\\ &=(1-n)(-1)^n(n-2)!\\ &=(-1)^{n+1}(n-1)!\;. \end{align*}$$

Added: It occurs to me that there’s a rather easy argument that does not use generating functions. Let $\sigma$ be any $k$-cycle formed from elements of $[n]$; then $\sigma$ is a factor in $(n-k)!$ permutations of $[n]$. Moreover, exactly half of these permutations are even unless $n-k$ is $0$ or $1$. Thus, $\sigma$ contributes to $d_n$ iff $k=n$ or $k=n-1$.

There are $(n-1)!$ $n$-cycles; they are even permutations iff $n$ is odd, so they contribute $(-1)^{n-1}(n-1)!$ to $d_n$.

There are $n(n-2)!$ $(n-1)$-cycles: there are $n$ ways to choose the element of $n$ that is not part of the $(n-1)$-cycle, and the other $n-1$ elements can be arranged in $(n-2)!$ distinct $(n-1)$-cycles. The resulting permutation of $[n]$ is even iff $n-1$ is odd, i.e., iff $n$ is even, so they contribute $(-1)^nn(n-2)!$ to $d_n$.

It follows that $$\begin{align*}d_n&=(-1)^nn(n-2)!+(-1)^{n-1}(n-1)!\\ &=(-1)^n\Big(n(n-2)!-(n-1)!\Big)\\ &=(-1)^n(n-2)!\Big(n-(n-1)\Big)\\ &=(-1)^n(n-2)!\;. \end{align*}$$

Combinatorics – Exponential Generating Function for Derangements

Here’s one way. Start with the recurrence $d_{n+1}=nd_n+nd_{n-1}$, where $d_n$ is the number of derangements of $[n]=\{1,\dots,n\}$. Multiply by $\frac{x^n}{n!}$ and sum over $n\ge 0$:

$$\sum_{n\ge 0}d_{n+1}\frac{x^n}{n!}=\sum_{n\ge 0}nd_n\frac{x^n}{n!}+\sum_{n\ge 0}nd_{n-1}\frac{x^n}{n!}\;.\tag{1}$$

(Here I make the assumption that $d_{-1}=0$: this is consistent with the recurrence, so it causes no problems.) Let $$D(x)=\sum_{n\ge 0}d_n\frac{x^n}{n!}$$ be the exponential generating function in question. Then $$D\,'(x)=\sum_{n\ge 0}nd_n\frac{x^{n-1}}{n!}=\sum_{n\ge 1}d_n\frac{x^{n-1}}{(n-1)!}=\sum_{n\ge 0}d_{n+1}\frac{x^n}{n!}\;,\tag{2}$$

$$xD\,'(x)=x\sum_{n\ge 0}nd_n\frac{x^{n-1}}{n!}=\sum_{n\ge 0}nd_n\frac{x^n}{n!}\;,\tag{3}$$

and $$xD(x)=\sum_{n\ge 0}d_n\frac{x^{n+1}}{n!}=\sum_{n\ge 0}(n+1)d_n\frac{x^{n+1}}{(n+1)!}=\sum_{n\ge 1}nd_{n-1}\frac{x^n}{n!}=\sum_{n\ge 0}nd_{n-1}\frac{x^n}{n!}\;,\tag{4}$$ since by convention $d_{-1}=0$.

Compare $(2),(3)$, and $(4)$ with $(1)$, and you’ll see that

$$D\,'(x)=xD\,'(x)+xD(x)\;,$$ or $$(1-x)D\,'(x)=xD(x)\;.$$ This is a separable differential equation,

$$\frac{D\,'(x)}{D(x)}=\frac{x}{1-x}=-1+\frac1{1-x}\;,$$

which you can now solve for $D(x)$ by first-year calculus.

Here’s another way, quicker but sneakier. For any particular set $K$ of $k$ elements of $[n]$ there are $d_{n-k}$ permutations of $[n]$ that have $K$ as their set of fixed points. There are $\binom{n}k$ such subsets $K$, so there are $\binom{n}kd_{n-k}$ permutations of $[n]$ with exactly $k$ fixed points. Since there are $n!$ permutations of $[n]$ altogether, $$\sum_{k=0}^n\binom{n}kd_{n-k}=n!\;.\tag{5}$$ The lefthand side of $(5)$ is the $n$-th term of the binomial convolution of the sequences $\langle 1,1,1,\dots\rangle$ and $\langle d_n:n\in\Bbb N\rangle$, so the exponential generating function (egf) of the sequence

$$\left\langle\sum_{k=0}^n\binom{n}kd_{n-k}:n\in\Bbb N\right\rangle=\langle n!:n\in\Bbb N\rangle$$

is the product of the egfs of $\langle 1,1,1,\dots\rangle$ and $\langle d_n:n\in\Bbb N\rangle$. Clearly $$\sum_{n\ge 0}n!\frac{x^n}{n!}=\sum_{n\ge 0}x^n=\frac1{1-x}$$ and $$\sum_{n\ge 0}1\cdot\frac{x^n}{n!}=e^x\;,$$ so $$e^xD(x)=\frac1{1-x}\;,$$ and $$D(x)=\frac{e^{-x}}{1-x}\;.$$

Best Answer

Related Solutions

Combinatorics – Number of Cycles in Even and Odd Permutations of $[n]$

Combinatorics – Exponential Generating Function for Derangements

Related Question