4
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Todd Trimble Oct 14 '14 at 2:45
  • $\begingroup$ Sorry...will do $\endgroup$ – Eleven-Eleven Oct 14 '14 at 2:55
  • $\begingroup$ 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. $\endgroup$ – Amritanshu Prasad Oct 14 '14 at 5:18
  • $\begingroup$ I can see your point. Perhaps a non-rational then..... $\endgroup$ – Eleven-Eleven Oct 14 '14 at 19:26
  • $\begingroup$ I understand that you want $\beta_k(x):=\sum_{n\ge0} b(n,k)x^n$: these are actually rational functions. $\endgroup$ – Pietro Majer Sep 30 '16 at 18:08
2
$\begingroup$

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. $$*$$ [edit] 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}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Eleven-Eleven Dec 31 '16 at 20:08
  • $\begingroup$ 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? $\endgroup$ – Eleven-Eleven Jan 4 '17 at 15:06
  • $\begingroup$ 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. $\endgroup$ – Pietro Majer Jan 4 '17 at 17:01
  • $\begingroup$ A better way to do this should be working directly on the expression for $\beta_k$ given above, finding its partial fraction decomposition. $\endgroup$ – Pietro Majer Jan 4 '17 at 17:03
  • $\begingroup$ 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. $\endgroup$ – Eleven-Eleven Jan 4 '17 at 23:30
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.