Good morning. I have the following;



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


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


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?

  • $\begingroup$ To be clear, your $b(r; n,k)$ is Wikipedia's $S_{r+1}(n, k)$? $\endgroup$ – Peter Taylor May 21 at 13:33
  • $\begingroup$ 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. $\endgroup$ – Eleven-Eleven May 21 at 13:48
  • $\begingroup$ And I think there's a typo in the definition of $\beta$: should the sum be over $n$? $\endgroup$ – Peter Taylor May 21 at 14:29
  • $\begingroup$ Yes...I will amend...thank you! It's always little things like that i miss... $\endgroup$ – 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.