Exponential generating function of the relation $B(n,k)=B(n-1,k-1)+(n-1)B(n-2,k-1)$ —just over $n$—

Question

Let $B(n,k)$ the number of permutations of the set $[n]=\{1,\ldots,n\}$ that are decomposable in $k$ disjoint cycles of order $1$ or $2$. For example, $\mu=(1,3)(2,5)(4)(6,7)(8)$ is counted by $B(8,5)$. Find the exponential generating function $A(x)$ for the sequence $B(n,k)$ $$A(x)=\sum_{n\geq k}B(n,k)\frac{x^n}{n!}.$$

Well, this is my approach. It's necessary that $n\geq k\geq0$. For $n\geq2$ and $k\geq1$, one can prove the identity $$B(n,k)=B(n-1,k-1)+(n-1)B(n-2,k-1).$$ We also must have $B(n,0)=B(0,n)=B(1,n)=1$ for all $n\geq0$. Taking the derivative of $A(x)$ —to cancel the term $(n-1)$— and using the recurrence relation we get

$$ \begin{align*} A'(x) &=\sum_{n\geq 1}B(n,k)\frac{x^{n-1}}{(n-1)!}\\ &=1+\sum_{n\geq 0}B(n+2,k)\frac{x^{n+1}}{(n+1)!}\\ &=1+\sum_{n\geq 0}\left[B(n+1,k-1)+(n+1)B(n,k-1)\right]\frac{x^{n+1}}{(n+1)!}\\ &=1+\sum_{n\geq1}B(n,k-1)\frac{x^n}{n!}+x\sum_{n\geq0}B(n,k-1)\frac{x^n}{n!}. \end{align*} $$ I would like to find a functional equation, or a O.D.E to solve $A(x)$, but I don't know how to manipulate the term $B(n,k-1)$ to get it. Any ideas?

Secondly, I suspect $A(x)$ must be in terms of $k$, am I right? Thirdly, I found the sequence in the OEIS A122848, and a closed formula for the coefficient is $$B(n,k)=\frac{n!}{(n-k)!(2k-n)!2^{n-k}},$$ but I'd like to avoid to prove this, preferably. Still, any answer is welcome.

Answer 1

Sometimes good notation can help get a quick grasp on a problem. Using the notation from Analytic Combinatorics by Flajolet and Sedgewick we get for the combinatorial class of permutations consisting of fixed points and two-cycles (involutions)

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\mathcal{U}\times \textsc{CYC}_{=1}(\mathcal{Z}) + \mathcal{U}\times \textsc{CYC}_{=2}(\mathcal{Z})).$$

This gives the mixed exponential generating function

$$Q(z,u) = \exp\left(u\left(z+\frac{z^2}{2}\right)\right)$$

so that

$$[u^k] Q(z, u) = \frac{1}{k!} \left(z+\frac{z^2}{2}\right)^k.$$

Extracting the coefficient on $z$ we get

$$n! [z^n] \frac{1}{k!} z^k \left(1+\frac{z}{2}\right)^k = n! \frac{1}{k!} [z^{n-k}] \left(1+\frac{z}{2}\right)^k = n! \frac{1}{k!} {k\choose n-k} \frac{1}{2^{n-k}} \\ = \frac{n!}{(n-k)! \times (2k-n)! \times 2^{n-k}}.$$

Answer 2

Since $k$ acts as a parameter in the definition of $A(x)$, you should include $k$ as a subscript to reflect that: $$ A_k(x)=\sum_{n\ge k} B(n,k)\frac{x^n}{n!} $$ Your work is correct, except that you should not pull out the $+1$ out front. The correct expression is $$ \begin{align} A_k'(x) &= \sum_n B(n,k-1)\frac{x^n}{n!}+x\sum_n B(n,k-1)\frac{x^n}{n!} \\&= (1+x)\sum_n B(n,k-1)\frac{x^n}{n!} \\&=(1+x)A_{k-1}(x) \end{align} $$ That is, $$ A_k(x)=\int_0^x (1+t)A_{k-1}(t)\,dt $$ This recursive equation, together with the base case $A_0(x)=1$, determines $A_k(x)$ for all $k\ge 0$. However, it is not clear how to solve this recursion.

---

Note that $B(n,k)$ also satisfies the recursion $$ k\cdot B(n,k)=n\cdot B(n-1,k-1)+\binom n2B(n-2,k-1) $$ Applying a similar exponential generating function analysis to this recursion instead yields $$ A_k(x)=\frac1k\left(x+\frac{x^2}2\right)A_{k-1}(x), $$ which quickly leads to a closed form for $A_k(x)$.