|
| |
|
|
A143395
|
|
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.
|
|
20
|
|
|
|
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, 545, 45, 1, 0, 127, 6069, 15421, 7770, 1190, 63, 1, 0, 255, 26335, 116298, 95781, 24150, 2282, 84, 1, 0, 511, 111645, 830845, 1071630, 416451, 62370, 3990, 108, 1, 0, 1023
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
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
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.
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.
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.
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
/I_k 0\
\ 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)
The Bell transform of 2^(n+1)-1. For the definition of the Bell transform see A264428. - Peter Luschny, Jan 18 2016
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f. for column k: x^k/Product_{t=k..2*k} (1-t*x).
T(n,k) = Sum_{t=k..n} C(n,t) * Stirling2(t,k) * k^(n-t).
T(n,k) = Sum_{m=0..k} Stirling2(n,k+m)*(k+m)!/(m!*(k-m)!). - Vladimir Kruchinin, Apr 06 2011
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.
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
T(n,k) = (1/k!)*Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*(j + k)^n.
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.
The inverse array is a signed version of A038455. (End)
|
|
|
EXAMPLE
|
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}.
Triangle begins:
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, 545, 45, 1;
0, 127, 6069, 15421, 7770, 1190, 63, 1;
...
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.
Recurrence equation example:
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.
Connection constants:
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).
With the array M(k) as defined in the Comments section, the infinite product M(0)*M(1)*M(2)*... begins
/ 1 \/1 \/1 \ / 1 \
| 3 1 ||0 1 ||0 1 | | 3 1 |
| 7 6 1 ||0 3 1 ||0 0 1 |... = | 7 9 1 |
|15 21 9 1 ||0 7 6 1 ||0 0 3 1 | |15 55 18 1 |
|... ||0 15 21 9 1||0 0 7 6 1| |... |
|... ||... ||... | | |
(End)
|
|
|
MAPLE
|
T:= (n, k)-> add(binomial(n, t)*Stirling2(t, k)*k^(n-t), t=k..n):
seq(seq(T(n, k), k=0..n), n=0..11);
|
|
|
MATHEMATICA
|
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 *)
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 *)
|
|
|
PROG
|
(Sage) # uses[bell_matrix from A264428]
bell_matrix(lambda n: 2^(n+1)-1, 10) # Peter Luschny, Jan 18 2016
(PARI) {T(n, k) = sum(j=k, n, binomial(n, j)*stirling(j, k, 2)*k^(n-j))};
for(n=0, 10, for(k=0, n, print1(T(n, k), ", "))) \\ G. C. Greubel, Mar 07 2019
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
