# Ordinary or Rational Generating Function for Associated Stirling Numbers $b(n,k)$

I am trying to identify or find the ordinary or rational generating function (not the exponential generating function) for the Associated Stirling numbers of the Second kind, denoted $$b(1;n,k)=b(n,k)$$ These numbers are the number of ways to partition a set of $n$ elements into $k$ disjoint parts whose partition cardinality are greater than 1.
If there isn't already an explicit formula, how I do go about attempting to derive such a thing?

EDIT: One thing that I do know is that $$b(n,j)=\sum_{k=0}^j(-1)^k\binom{n}{k}S(n-k,j-k)$$ where $S(n,k)$ are Stirling numbers of the second kind. Therefore, I can say that $$\sum_{n=0}^\infty b(n,j)x^n=\sum_{n=0}^\infty \left(\sum_{k=0}^j(-1)^k\binom{n}{k}S(n-k,j-k)\right)x^n$$ which is quite ugly. I also know that the Stirling Numbers of the Second kind have the ordinary generating function $$\sum_{n=0}^\infty S(n,k)x^n=\frac{x^k}{(1-x)(1-2x)...(1-kx)}$$ which I'm hoping to take advantage of after some brute force calculation...

EDIT 2: Aftr some brute force calculation, it appears that I have a series generated, that looks like $$b(n,j)=\sum_{k=0}^j(-1)^k\binom{n}{k}S(n-k,j-k)$$ $$\sum_{n=0}^\infty b(n,j)x^n=b(0,j)+b(1,j)+b(2,j)+b(3,j)+b(4,j)+...$$ Now $$b(0,j)=1$$ $$b(1,j)=S(1,j)$$ $$b(2,j)=S(2,j)-2S(1,j-1)$$ $$b(3,j)=S(3,j)-3S(2,j-1)$$ $$b(4,j)=S(4,j)-4S(3,j-1)+6S(2,j-2)$$ $$b(5,j)=S(5,j)-5S(4,j-1)+10S(3,j-2)$$ $$b(6,j)=S(6,j)-6S(5,j-1)+15S(4,j-2)-20(3,j-3)$$ $$b(7,j)=S(7,j)-7S(6,j-1)+21S(5,j-2)-35(4,j-3)$$ $$...$$ Rearranging I can see that I have $$\sum_{n=0}^\infty b(n,j)x^n=\sum_{n=0}^\infty S(n,j)x^n-\sum_{n=1}^\infty nS(n-1,j-1)x^n+\sum_{n=2}^\infty \frac{n(n-1)}{2!}S(n-2,j-2)x^n-\sum_{n=3}^\infty \frac{n(n-1)(n-2)}{3!}S(n-3,j-3)x^n+...$$ And it looks like a derivative is taking effect but my powers of $x$ are not changing, but it also looks like I'm running in circles. I feel like my bounds are incorrect...Should, for example, I change $$\sum_{n=1}^\infty nS(n-1,j-1)x^n=\sum_{n=0}^\infty (n+1)S(n,j-1)x^{n+1}$$ $$\sum_{n=2}^\infty \frac{n(n-1)}{2!}S(n-2,j-2)x^n=\sum_{n=0}^\infty \frac{(n+2)(n+1)}{2!}S(n,j-2)x^{n+2}$$ Any suggestions?

EDIT 3: By comparing the first few numbers given $j$ values 2,3,4, there seems to be a trend, the generating function is structured $$\sum_{n=0}^{\infty}b(n,j)x^n=\frac{f(x)}{\prod_{k=1}^{j}(1-kx)^{j-k+1}}$$ The degree of the numerator is greater than the degree of the denominator in the cases where $j=2,3,4$ and the ratios of degree(numerator) to degree(denominator) for $j=2,3,4$ are $$\frac{4}{3}, \frac{9}{6}, \frac{14}{10}$$

• Cross-posted from MSE: math.stackexchange.com/questions/971991/… Please do not cross-post without saying so. And please wait a while for an answer at one site before cross-posting to another. – Todd Trimble Oct 14 '14 at 2:45
• Sorry...will do – Eleven-Eleven Oct 14 '14 at 2:55
• The recurrence relation in oeis.org/A008299: b(n+1,k) = kb(n,k) + nb(n-1,k-1) makes me wonder whether the ordinary generating function can be rational. Note the occurence of n in the second term. – Amritanshu Prasad Oct 14 '14 at 5:18
• I can see your point. Perhaps a non-rational then..... – Eleven-Eleven Oct 14 '14 at 19:26
• I understand that you want $\beta_k(x):=\sum_{n\ge0} b(n,k)x^n$: these are actually rational functions. – Pietro Majer Sep 30 '16 at 18:08

Yes , the series $\beta_k(x):=\sum_{n\ge0} b(n,k) x^n$ are indeed rational functions, with the poles as you said.

One step back. The Exponential Generating Function of the polynomials $\big\{\sum_{k\ge0} b(n,k)t^k \big\}_{n\ge0}$ is $$\sum_{n\ge0}\Big(\sum_{k\ge0} b(n,k) t^k \Big)\frac{x^n}{n!} =e^{t(e^x-1-x)}$$ by the combinatorial meaning of the exponential of an EGF. Hence also, for any $k\ge0$, $$\sum_{n\ge0} b(n,k) \frac{x^n}{n!}=\frac{(e^x-1-x)^k}{k!}.$$

To convert the latter into an ordinary Generating Function, apply the usual transformation $u(x)\mapsto \frac{1}{ x}\int_0^{\infty}u(s) e^{-\frac{s}{x}}ds$

$$\sum_{n\ge0} b(n,k) x^n =\frac{1}{k!x} \int_0^{\infty} (e^s-1-s)^k e^{-\frac{s}{x}}ds ,$$ which clearly produces a rational function: if we expand the term $(e^s-1-s)^k$ and integrate with a linear change of variables we get a finite sum $$\sum_{n\ge0} b(n,k) x^n =\frac{(-1)^k}{x}\sum_{i\ge0, j\ge0\atop i+j\le k} \frac{(-1)^j}{i!j!}\Big(\frac{x}{1-jx}\Big)^{k-i-j+1} ,$$ which is a rational function of the form you suggested in last edit.

Rmk: the above transformation can be applied formally, as all needed identities holds in a formal context; however, for $|x|<1/k$ the convergence of the integrals and series are ensured. $$*$$  One can show that $\beta_k(x)$ is a rational function, without computing it explicitly. The recursive relation of the coefficients $b(n,k)$, translated into the sequence $\beta_k$ reads: $$(1-kx)\beta_k=x^2(x\beta_{k-1})'$$ for $k\ge1$. Since $\beta_0(x):=1$, it follows by induction that $\beta_k$ are rational functions of the form $$\beta_k(x)=\frac{x^{2k}P_k(x)}{(1-x)^k(1-2x)^{k-1}\cdots(1-kx)},$$ for polynomials $P_k(x)$ of degree $\binom{k}{2}$.

• I gave you credit for answering my question. I have another question though. Is there a way to discern the $P_k(x)$ and if so, what method could i employ to find them specifically? – Eleven-Eleven Dec 31 '16 at 20:08
• Hello. I noticed the comments and edits were taken down. I wanted to get more in depth with the edits you made, but now I dont see them Do you know whathappened? – Eleven-Eleven Jan 4 '17 at 15:06
• Hi -I just removed the last comments as I started thinking they were not that useful. It was this 1) the values $P_k(1/j)$ for $j=1,\dots, k$ can be computed iteratively form the iteration, and have a not-too bad expression. If one can also compute e.g. some derivatives in these points, $P^{(i)}_k(1/j)$, collecting ${k\choose 2}+1$ linear conditions, then $P_k$ would be identified as the Hermite interpolation polynomial at these points. – Pietro Majer Jan 4 '17 at 17:01
• A better way to do this should be working directly on the expression for $\beta_k$ given above, finding its partial fraction decomposition. – Pietro Majer Jan 4 '17 at 17:03
• I think i agree with you in terms of the $\beta_k$. Part of the reason i need this is i am relating function expansions to identify identities, so having it in the partial fraction summation form helps, i believe, for what i need. – Eleven-Eleven Jan 4 '17 at 23:30

Using the recurrent relation $b(n+1,k) = k\cdot b(n,k) + n\cdot b(n-1,k-1)$ it is easy to get that the ordinary generating function $B(x,y) = \sum_{n,k} b(n,k)\cdot x^n\cdot y^k$ satisfies the following PDE: $$\frac{\partial B(x,y)}{\partial y} + x^2\frac{\partial B(x,y)}{\partial x} = \frac{1-x^2y}{xy} B(x,y) - x.$$ Making substitution $z = \frac{1}{x}$ and $w(y,z)=B(1/z,y)$, it reduces to $$\frac{\partial w(y,z)}{\partial y} - \frac{\partial w(y,z)}{\partial z} = \frac{z^2-y}{yz} w(y,z) - \frac{1}{z}.$$

While it is known how to solve this equation, its solution involves integral of the form $$\int \frac{e^y dy}{y^u (u-y)^2},$$ which is not expressed in elementary (let alone, rational) functions. I suspect (but did not check carefully) that $w(y,z)$ (and thus $B(x,y)$) can be more or less easily expressed in terms of incomplete gamma function.