Exponential generating function wilf 3.12

74 Views Asked by At

Fix $k>0$. Let $f(n,k)$ be the number of permutations of $n$ letters whose longest cycle is length $k$. Find the exponential generating function of ${f(n,k)}$ for $n≥0$ for fixed $k$.

I know that if $F(n,k)$ is the number of n-permutations whose cycles have lengths $≤ k$, then F has the egf $\exp\left(\frac{x+\cdots+x^k}{k}\right)$. But $f(n,k)$ counts those whose longest cycle is length $k$, so if $k≥1, ~~f(n,k)=F(n,k)-F(n,k-1)$, and the required egf is

$$\exp\left(\dfrac{x+...+x^{k-1}}{k-1}\right) \cdot\exp\left(\dfrac{x^k}k-1\right).$$

Can you help fill in the details. This is from Wilfs Generatingfunctionology.

1

There are 1 best solutions below

3
On

You have the wrong formula for $F(n,k)$. It should be $$\exp \left( x + \frac{1}{2} x^2 + \dots + \frac{1}{k} x^{k} \right)$$

and the final formula for $f(n,k)$ is also incorrect. It should be $$\exp \left(x + \frac{1}{2} x^2 + \dots + \frac{1}{k-1} x^{k-1} \right) \cdot \left[ \exp \left( \frac{1}{k} x^k \right) -1 \right]$$

Can you take it from there?