A143395 - OEIS

%I #70 Sep 21 2022 13:41:17

%S 1,0,1,0,3,1,0,7,9,1,0,15,55,18,1,0,31,285,205,30,1,0,63,1351,1890,

%T 545,45,1,0,127,6069,15421,7770,1190,63,1,0,255,26335,116298,95781,

%U 24150,2282,84,1,0,511,111645,830845,1071630,416451,62370,3990,108,1,0,1023

%N Triangle read by rows: T(n,k) = number of forests of k labeled rooted trees of height at most 1, with n labels, where any root may contain >= 1 labels, n >= 0, 0 <= k <= n.

%C This is the Sheffer triangle (1,exp(x)*(exp(x)-1)) (Jobotinsky type). See the e.g.f. given by V. Jovovic below, and the W. Lang link under A006232 (second part) for general Sheffer remarks and the conversion to the umbral notation of S. Roman's book. - _Wolfdieter Lang_, Oct 08 2011

%C From _Peter Bala_, Jan 07 2015: (Start)

%C T(n,k) counts the ways a set of size n can be partitioned into k nonempty blocks and then a nonempty subset chosen from each block. An example is given below.

%C This triangle is the particular case a = 1, b = 1, c = 0 of the triangle of generalized Stirling numbers of the second kind S(a,b,c) defined in the Bala link. A008277 is the case a = 1, b = 0, c = 0.

%C Define a polynomial sequence x_(n) by putting x_(0) = 1, x_(1) = x and for n >= 2 setting x_(n) = x*(x - (n+1))*(x - (n+2))*...*(x - (2*n-1)), that is, x_(n) = (-1)^(n+1)*n!*(x/(2*n - x))*binomial(2*n - x,n) for n >= 0. Then this table is the triangle of connection constants for expressing the monomial polynomials x^n in terms of the basis polynomials x_(k), that is, x^n = sum {k = 0..n} T(n,k)*x_(k), n = 0,1,2,.... Examples are given below.

%C Matrix factorization: Let M be the infinite lower unit triangular array with (n,k)-th entry (2^(n+1-k)-1)*binomial(n,k). For k = 0,1,2,... define M(k) to be the lower unit triangular block array

%C /I_k 0\

%C \ 0  M/ having the k X k identity matrix I_k as the upper left block; in particular, M(0) = M. It follows from the recurrence equation given in the Formula section that the infinite product M(0)*M(1)*M(2)*..., which is clearly well-defined, is equal to the present triangle (but with the first row and column omitted). See the Example section. (End)

%C The Bell transform of 2^(n+1)-1. For the definition of the Bell transform see A264428. - _Peter Luschny_, Jan 18 2016

%H Alois P. Heinz, <a href="/A143395/b143395.txt">Rows n = 0..140, flattened</a>

%H Eli Bagno, Riccardo Biagioli, and David Garber, <a href="https://arxiv.org/abs/1901.07830">Some identities involving second kind Stirling numbers of types B and D</a>, arXiv:1901.07830 [math.CO], 2019.

%H Peter Bala, <a href="/A143395/a143395.pdf">A 3 parameter family of generalized Stirling numbers</a>

%H Takao Komatsu, Eli Bagno, and David Garber, <a href="https://arxiv.org/abs/2209.06674">A q,r-analogue of poly-Stirling numbers of second kind with combinatorial applications</a>, arXiv:2209.06674 [math.CO], 2022.

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%F G.f. for column k: x^k/Product_{t=k..2*k} (1-t*x).

%F T(n,k) = Sum_{t=k..n} C(n,t) * Stirling2(t,k) * k^(n-t).

%F E.g.f.: exp(y*exp(x)*(exp(x)-1)). - _Vladeta Jovovic_, Dec 08 2008

%F T(n,k) = Sum_{m=0..k} Stirling2(n,k+m)*(k+m)!/(m!*(k-m)!). - _Vladimir Kruchinin_, Apr 06 2011

%F Let P be Pascal's triangle A007318. The first column of the array exp(t*(P^2-P)) gives the row generating polynomials of this triangle.

%F The row polynomials R(n,t) satisfy the recurrence R(n+1,t) = t*(Sum_{k = 0..n} (2^(k+1)-1)*C(n,k)*R(n-k,t)) with R(0,t) = 1. For example, the row 4 polynomial R(4,t) = 15*t + 55*t^2 + 18*t^3 + t^4 = t*((7*t + 9*t^2 + t^3) + 3*3*(3*t+t^2) + 7*3*t + 15*1). - _Peter Bala_, Oct 12 2011

%F From _Peter Bala_, Jan 07 2015: (Start)

%F T(n,k) = (1/k!)*Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*(j + k)^n.

%F Recurrence equation: T(n+1,k+1) = Sum_{j = k..n} (2^(n-j+1) - 1)*binomial(n,j)*T(j,k) with T(0,0) = 1 and T(n,0) = 0 for n >= 1. This leads to the matrix factorization noted in the Comments section.

%F The inverse array is a signed version of A038455. (End)

%e T(3,2) = 9: {1}{2}<-3, {1}{3}<-2, {1}{2,3}, {2}{1}<-3, {2}{3}<-1, {2}{1,3}, {3}{1}<-2, {3}{2}<-1, {3}{1,2}.

%e Triangle begins:

%e   1;

%e   0,   1;

%e   0,   3,    1;

%e   0,   7,    9,     1;

%e   0,  15,   55,    18,    1;

%e   0,  31,  285,   205,   30,    1;

%e   0,  63, 1351,  1890,  545,   45,  1;

%e   0, 127, 6069, 15421, 7770, 1190, 63,  1;

%e   ...

%e From _Peter Bala_, Jan 07 2015: (Start)

%e T(4,2) = 55: There are 7 partitions of the set {1,2,3,4} into 2 blocks. For the 3 set partitions of the type {a,b}{c,d} we can choose a nonempty subset from each block in one of 3*3 ways giving 3*3*3 = 27 possibilities in all. The remaining 4 set partitions of {1,2,3,4} into 2 blocks are of the form {a,b,c}{d} and we can choose a nonempty subset from each block in 7*1 ways giving 4*7*1 = 28 possible choices. Thus in total T(4,2) = 27 + 28 = 55.

%e Recurrence equation example:

%e T(4,2) = sum {j = 1..3} (2^(4-j) - 1)*binomial(3,j)*T(j,1) = 7*3*1 + 3*3*3 + 1*1*7 = 55.

%e Connection constants:

%e Row 3 = [0, 7, 9, 1]. Hence x^3 = 7*x + 9*x*(x - 3) + x*(x - 4)*(x - 5); Row 4 = [0, 15, 55, 18, 1]. Hence x^4 = 15*x + 55*x*(x - 3) + 18*x*(x - 4)*(x - 5) + x*(x - 5)*(x - 6)*(x - 7).

%e With the array M(k) as defined in the Comments section, the infinite product M(0)*M(1)*M(2)*... begins

%e / 1        \/1           \/1       \       / 1        \

%e | 3  1     ||0  1        ||0 1      |      | 3  1      |

%e | 7  6  1  ||0  3  1     ||0 0 1    |... = | 7  9  1   |

%e |15 21 9 1 ||0  7  6  1  ||0 0 3 1  |      |15 55 18 1 |

%e |...       ||0 15 21  9 1||0 0 7 6 1|      |...        |

%e |...       ||...         ||...      |      |           |

%e (End)

%p T:= (n, k)-> add(binomial(n,t)*Stirling2(t,k)*k^(n-t), t=k..n):

%p seq(seq(T(n, k), k=0..n), n=0..11);

%t t[0, 0]=1; t[n_, k_]:= SeriesCoefficient[Exp[y*Exp[x]*(Exp[x]-1)], {x, 0, n}, {y, 0, k}]*n!; Table[t[n, k], {n, 0, 10}, {k, 0, n}]//Flatten (* _Jean-François Alcover_, Dec 05 2013, after _Vladeta Jovovic_ *)

%t Table[If[n==k==0, 1, If[k==0, 0, Sum[Binomial[n, j]*StirlingS2[j, k]* k^(n-j), {j,k,n}]]], {n,0,10}, {k,0,n}]//Flatten (* _G. C. Greubel_, Mar 07 2019 *)

%o (Sage) # uses[bell_matrix from A264428]

%o bell_matrix(lambda n: 2^(n+1)-1, 10) # _Peter Luschny_, Jan 18 2016

%o (PARI) {T(n,k) = sum(j=k, n, binomial(n,j)*stirling(j,k,2)*k^(n-j))};

%o for(n=0,10, for(k=0,n, print1(T(n,k), ", "))) \\ _G. C. Greubel_, Mar 07 2019

%o (Magma) [[(&+[Binomial(n,j)*StirlingSecond(j,k)*k^(n-j): j in [k..n]]): k in [0..n]]: n in [0..10]]; // _G. C. Greubel_, Mar 07 2019

%Y Columns k=0-9: A000007, A000225, A016269(n-2), A028025(n-3), A143399, A143400, A143401, A143402, A143403, A143404.

%Y Diagonal: A000012.

%Y See also A048993, A008277, A007318, A143405 for row sums.

%K nonn,tabl

%O 0,5

%A _Alois P. Heinz_, Aug 12 2008