4
$\begingroup$

While reviewing, I've come across a problem that seems to outline my lack of knowledge with regards to (specifically exponential) generating functions. For some reason, I understand "ordinary" generating functions fine in most contexts, but I cannot grasp exponential generating functions nearly as well.

The problem is as simply stated in the title:

Find the exponential generating function for the count of permutations with no Fixed Points.

The book states the answer (might be?), $\huge{\frac{e^{-x}}{1-x}}$, but doesn't give an explanation. Of course, knowing what the solution looks like and substituting the infinite series for $\frac{1}{1-x}$, I can see that the answer is $(1+x+x^2+x^3+...)(1-x+\frac{x^2}{2} -...)$. I can't even justify this generating function, let alone derive it on my own.

I've tried splitting the problem into smaller sub-problems (first take an element in a random permutation with no fixed points of length $n$, it has chance $\frac{1}{n-1}$ of being in a cycle of a length $\{2,3,...,n\}$...) but this clearly goes nowhere as it's much more of a probabilistic argument, and not really a "combinatoric" argument that I'm trying to understand.

$\endgroup$
5
$\begingroup$

Let $d_n$ be the number of derangements of $[n]$ (i.e., the number of permutations of $[n]$ with no fixed points). The number of permutations with $k$ fixed points is $\binom{n}kd_{n-k}$: there are $\binom{n}k$ ways to choose the $k$ fixed points, and $d_{n-k}$ derangements of the other $n-k$ points. There are $n!$ permutations altogether, so

$$\sum_k\binom{n}kd_{n-k}=n!\;.$$

Now take the exponential generating function on the lefthand side. To do this, let $$g(x)=\sum_nd_n\frac{x^n}{n!}\;,$$ the exponential generating function for the derangement numbers. We also know that

$$e^x=\sum_n(1)\frac{x^n}{n!}$$

is the exponential generating function for the sequence $\langle 1,1,1,\ldots\rangle$. Now take the convolution of these two exponential generating functions:

$$e^xg(x)=\sum_n\left(\sum_k\binom{n}k(1)d_{n-k}\right)\frac{x^n}{n!}=\sum_n(n!)\frac{x^n}{n!}=\frac1{1-x}\;,$$

so $$g(x)=\frac{e^{-x}}{1-x}\;.$$

$\endgroup$
  • $\begingroup$ A comment explaining the downvote would be helpful. $\endgroup$ – Brian M. Scott Nov 4 '14 at 3:34
  • $\begingroup$ Wasn't me! Thank you very much for the help-- I thought the problem might have been much more straightforward than it was! $\endgroup$ – druckermanly Nov 4 '14 at 3:37
  • $\begingroup$ @user2899162: You’re very welcome. $\endgroup$ – Brian M. Scott Nov 4 '14 at 3:37
  • $\begingroup$ (+1) Very nice work. By way of enrichment this MSE link I may prove useful reading, as might this MSE link II and this MSE link III. $\endgroup$ – Marko Riedel Nov 4 '14 at 20:11

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.