Exponential Generating Function of guests at k tables

Question

Question: Let $g_n$ be the number of ways in which $n$ people can sit down at an unspecified number of tables that are arranged in a line, so that if $k$ tables have people around them, then those will be the first $k$ tables in the line. Two seating arrangements are considered identical if a person has the same left neighbor in both of them, and each person sits at the same table in both of them. Find the exponential generating function $G(x)$ of $g_n$.

I have been reading about exponential generating functions but am still quite confused by them. From my understanding, we need $G(x)= \sum_{n=0}^{\infty} \frac{a_{n}}{n!} x^{n}$. Here $a_{n}$ is counting the ways to impose some structure on an $n$ element set. I believe the structure I am looking to count is the following: the number of ways we can break the permutation $(12345...n)$ into $k$-cycles. Could I have some help?

edit: I see now it's not exactly the structure I described. Since something like $(12)(34)$ and$(34)(12)$ will be different seating arrangements but are the same cycle.

I have tried to describe some $g_{n}$ here. When $n=1$ $g_n = 1$, when $n =2$ I believe $g_{2} = 3$ since we have the arrangements $(1)(2),(12),(2)(1)$.

More progress: If $k$ is the amount of tables filled, it seems that we have a relation like $g_{n+1,k+1} = (k+1) g_{n,k} + n g_{n,k+1}$. But I wouldn't know how to turn this into an EGF.

If $k$ is fixed we could write the EGF like $\sum_{n} \sum_{k} g_{n,k} \frac{x^n}{n!}$

Answer 1

Your sequence can be found on OEIS here. The EGF can be found there as well.

---

The EGF for cycles is $$f(x) = \sum_{n=1}^\infty \frac{(n-1)!}{n!} x^n = \sum_{n=1}^\infty \frac{x^n}{n} = - \log (1-x).$$

Then the EGF of sequences of cycles is then $$1+f(x)+(f(x))^2 + \cdots = \frac{1}{1-f(x)} = \frac{1}{1+\log(1-x)}.$$

---

Some intuition on why this last step works: consider the coefficient of $x^5$ in $1+f(x)+(f(x))^2+\cdots$. It will be the sum of the coefficients of $x^5$ in $f(x), (f(x))^2,\ldots,(f(x))^5$ respectively.

• The contribution from $f(x)$ is $\frac{4!}{5!}x^5$, and indeed $4!$ counts the number of ways to seat $5$ people at one table.
• The contribution from $(f(x))^2$ is
• $$\left(\frac{3!}{4!}\cdot \frac{0!}{1!} + \frac{2!}{3!} \cdot \frac{1!}{2!} + \frac{1!}{2!} \cdot \frac{2!}{3!} + \frac{0!}{1!} \cdot \frac{3!}{4!}\right)x^5 = \frac{\binom{5}{4} 3!0! + \binom{5}{3} 2!1! + \binom{5}{2} 1!2! + \binom{5}{1}0!3!}{5!}x^5,$$ and indeed the expression in the numerator is the number of ways to seat $5$ people at two tables.
• The contribution from $(f(x))^5$ is $x^5 = \frac{5!}{5!} x^5$, and indeed there are $5!$ ways to seat $5$ people at $5$ tables.
• etc.

You can prove more formally that this works out in general.