0

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.

nmasanta
  • 9,222
ymmas
  • 43

1 Answers1

1

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?

awkward
  • 14,736
  • Where do you get F(n,k) – ymmas Jun 14 '20 at 20:44
  • @SammyCowgill That's the formula stated in the solution to exercise 3.12 in generatingfunctionology. I added the $x^2$ term for clarity. In your post, you seem to have erroneously inserted some parentheses. If you understand sections 3.5 ("Permutations and their cycles") and 3.7 ("A subclass of permutations") in the book, you should understand how to derive the EGF. – awkward Jun 14 '20 at 23:12
  • By the way, I personally find the presentation of this topic given in either An Introduction to the Analysis of Algorithms, Second Edition or Analytic Combinatorics by Sedgewick and Flajolet to be easier to follow than the "cards, decks, and hands" in Wilf's book (although I think Wilf has, overall, the best introduction to GFs). – awkward Jun 14 '20 at 23:20