Skip to main content
added 439 characters in body
Source Link

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

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?

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

added 12 characters in body
Source Link

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?

I am trying to identify or find the ordinary 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?

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?

Source Link

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

I am trying to identify or find the ordinary 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?