# Methods for Determining Closed Form of Polynomial Numerator of a Rational Generating Function

Good morning. I have the following;

Let

$$\beta_k(x)=\sum_{n=0}^\infty{b(r;n,k)x^n}$$

Here, $$b(r; n,k)$$ are called Associated Sterling Numbers of the Second Kind, and are the number of ways to partition a set of 𝑛 elements into 𝑘 disjoint parts whose partition cardinalities are greater than r. For simplicity, I'm only interested in the case when $$r=1$$, and so from here we will use $$b(1;n,k)=b(n,k)$$.

It can be shown through integral transformations that this generating function can be written as a partial fraction decomposition

$$\beta_k(x)=\frac{(-1)^k}{x}\sum_{j=0}^k\sum_{i=0}^{k-j}\frac{(-1)^j}{i!j!}\left(\frac{x}{1-jx}\right)^{k-i-j+1}$$

For my purposes, I'm trying to write this as a single rational function, which can be done up to one exception. For all $$k$$, we have that

$$\beta_k(x)=\frac{x^{2k}P_k(x)}{(1-x)^k(1-2x)^{k-1}(1-3x)^{k-2}...(1-kx)}$$

Now i was able to come up with these polynomials $$P_k(x)$$ using brute force and mathematica, but I'm still trying to determine if there is a closed form for these. Does a closed form exist and if so what are the techniques used to determine such a form?

• To be clear, your $b(r; n,k)$ is Wikipedia's $S_{r+1}(n, k)$? – Peter Taylor May 21 at 13:33
• Yes, that would be correct. The $b(r;n,k)$ notation is used in papers that I've seen, but it is equivalent to Wiki's. Though as you may have noticed, wiki denotes the definition involving $r$ of "at least" where other papers have used "greater than" specifically when referring to the constraint on the least number of elements in each partition. – Eleven-Eleven May 21 at 13:48
• And I think there's a typo in the definition of $\beta$: should the sum be over $n$? – Peter Taylor May 21 at 14:29
• Yes...I will amend...thank you! It's always little things like that i miss... – Eleven-Eleven May 21 at 15:42

As the joke says, "If I wanted to go there I wouldn't start here". From Wikipedia we have (adjusting notation) $$b(r; n+1, k) = k b(r; n, k) + \binom{n}{r} b(r; n-r, k-1)$$

In particular, setting $$r=1$$, $$b(n+1, k) = k b(n, k) + n b(n-1, k-1)$$ yielding $$\beta_k(x) = \frac{x^2}{1 - kx} \left[ \beta_{k-1}(x) + x \frac{\textrm d}{\textrm dx} \beta_{k-1}(x)\right]$$ which has obvious similarities to the expression in the question. If we define $$Q_k(x) = \prod_{a=1}^k (1-ax)^{k+1-a}$$ and suppose that $$\beta_{k-1}(x) = \frac{x^{2(k-1)} P_{k-1}(x)}{Q_{k-1}(x)}$$ then

$$\begin{eqnarray}\beta_k(x) &=& \frac{x^2}{1 - kx} \left[ \frac{x^{2(k-1)} P_{k-1}(x)}{Q_{k-1}(x)} + x \frac{\textrm d}{\textrm dx} \frac{x^{2(k-1)} P_{k-1}(x)}{Q_{k-1}(x)}\right] \\ % &=& \frac{x^2}{1 - kx} \left[ \frac{x^{2(k-1)} P_{k-1}(x)}{Q_{k-1}(x)} + x \frac{x^{2(k-1)} Q_{k-1}(x) \frac{\textrm d}{\textrm dx} P_{k-1}(x) + P_{k-1}(x) Q_{k-1}(x) \frac{\textrm d}{\textrm dx} x^{2(k-1)} - x^{2(k-1)} P_{k-1}(x) \frac{\textrm d}{\textrm dx} Q_{k-1}(x)}{Q_{k-1}(x)^2}\right] \\ % &=& \frac{\left[x^{2k} + x^3 \frac{\textrm d}{\textrm dx} x^{2(k-1)} \right]P_{k-1}(x) Q_{k-1}(x) + x^{2k+1} Q_{k-1}(x) \frac{\textrm d}{\textrm dx} P_{k-1}(x) - x^{2k+1} P_{k-1}(x) \frac{\textrm d}{\textrm dx} Q_{k-1}(x)}{(1-kx)Q_{k-1}(x)^2}\\ % &=& \frac{(2k-1) x^{2k} P_{k-1}(x) Q_{k-1}(x) + x^{2k+1} \left[ Q_{k-1}(x) \frac{\textrm d}{\textrm dx} P_{k-1}(x) - P_{k-1}(x) \frac{\textrm d}{\textrm dx} Q_{k-1}(x) \right]}{(1-kx)Q_{k-1}(x)^2}\\ % &=& \frac{(2k-1) x^{2k} P_{k-1}(x) + x^{2k+1} \left[ \frac{\textrm d}{\textrm dx} P_{k-1}(x) - P_{k-1}(x) \sum_{a=1}^{k-1} \frac{a(a-k)}{(1 - ax)}\right]}{(1-kx)Q_{k-1}(x)}\\ % \end{eqnarray}$$

Clearly $$\sum_{a=1}^{k-1} \frac{a(a-k)}{(1 - ax)}$$ can be expressed as $$\frac{R(x)}{\prod_{a=1}^{k-1} (1 - ax)}$$ for some polynomial $$R_k(x)$$, so we have

$$\begin{eqnarray}\beta_k(x) &=& \frac{(2k-1) x^{2k} P_{k-1}(x) + x^{2k+1} \left[ \frac{\textrm d}{\textrm dx} P_{k-1}(x) - P_{k-1}(x) \frac{R_k(x)}{\prod_{a=1}^{k-1} (1 - ax)}\right]}{(1-kx)Q_{k-1}(x)}\\ % &=& \frac{(2k-1) x^{2k} P_{k-1}(x) \prod_{a=1}^{k-1} (1 - ax) + x^{2k+1} \left[ (\prod_{a=1}^{k-1} (1 - ax)) \frac{\textrm d}{\textrm dx} P_{k-1}(x) - P_{k-1}(x) R_k(x)\right]}{Q_k(x)}\\ \end{eqnarray}$$

and giving the recurrence

$$P_k(x) = P_{k-1}(x) \left( (2k-1) \prod_{a=1}^{k-1} (1 - ax) - xR_k(x)\right) + x\left(\prod_{a=1}^{k-1} (1 - ax)\right) \frac{\textrm d}{\textrm dx} P_{k-1}(x)$$

It's not all the way to a closed form, but I would consider it better than brute force. It allows for reasonably efficient computation with a CAS, as well as the simple observation that $$\deg R_k(x) = k - 2$$, so $$\deg P_k(x) \le \deg P_{k-1}(x) + k - 1$$