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$

1 Answer 1

Reset to default
7
$\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$
4
  • $\begingroup$ A comment explaining the downvote would be helpful. $\endgroup$ Commented Nov 4, 2014 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$ Commented Nov 4, 2014 at 3:37
  • $\begingroup$ @user2899162: You’re very welcome. $\endgroup$ Commented Nov 4, 2014 at 3:37
  • 1
    $\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$ Commented Nov 4, 2014 at 20:11

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.