|
|
A055105
|
|
Triangle read by rows: T(n,k) = number of noncommutative symmetric polynomials of degree n that have exactly k different variables appearing in each monomial and which generate the algebra of all noncommutative symmetric polynomials (n >= 1, 1 <= k <= n).
|
|
15
|
|
|
1, 0, 1, 0, 1, 1, 0, 1, 4, 1, 0, 1, 12, 8, 1, 0, 1, 33, 44, 13, 1, 0, 1, 88, 208, 109, 19, 1, 0, 1, 232, 910, 753, 223, 26, 1, 0, 1, 609, 3809, 4674, 2091, 405, 34, 1, 0, 1, 1596, 15521, 27161, 17220, 4926, 677, 43, 1, 0, 1, 4180, 62185, 151134, 130480, 51702, 10342
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,9
|
|
COMMENTS
|
Also the number of irreducible (sometimes called 'unsplittable') set partitions of size n and length k. A set partition of [n] of length k is a set of sets A = {A_1,A_2,...,A_k} where A_i are nonempty and their union is {1..n}. Let B = {B_1,B_2,...,B_r} and C = {C_1,C_2,...,C_s} be set partitions of [n] and [m] respectively with min(B_i) < min(B_{i+1}) for 1 <= i < r and min(C_j) < min(C_{j+1}) for 1 <= j < s. Define B*C = { B_1 U (C_1+n), B_2 U (C_2+n), ..., B_r U (C_r+n), C_{r+1}+n,...,C_s+n } if r <= s and B*C = { B_1 U (C_1+n), B_2 U (C_2+n), ..., B_s U (C_s+n), B_{s+1}, ..., B_r } if s < r (here C_i+n means add n to every entry in C_i). A set partition A is reducible if A = B*C for some nonempty B and C. A set partition is irreducible if it is not reducible. - Mike Zabrocki, Feb 04 2005, corrected May 11 2014
|
|
LINKS
|
|
|
FORMULA
|
Let B_k(q) = Sum_{n>=0} Sum_{i=1..k} S_{n,i} where S_{n, i} are the Stirling numbers of the second kind. Then A_k(q) = 1/B_{k-1}(q) - 1/B_k(q) is the generating function for the k-th column of this table (k >= 0) A(q, t) = Sum_{k>=0} t^k(t-1)/B_k(q) = Sum_{n>=0} Sum_{k=1..n} T_{n, k}*q^n*t^k. - Mike Zabrocki, Feb 04 2005
|
|
EXAMPLE
|
T(1,1)=1 from Sum x_1; T(2,2)=1 from Sum x_1 x_2; T(3,2)=1 from Sum x_1 x_2 x_1; T(3,3)=1 from Sum x_1 x_2 x_3; ...
Triangle starts:
1;
0, 1;
0, 1, 1;
0, 1, 4, 1;
0, 1, 12, 8, 1;
...
T(4,3) = 4 because {1|23|4}, {1|2|34}, {1|24|3}, {13|2|4} are irreducible set partitions of size 4 and length 3 while {12|3|4}={1}*{1|2|3}, {14|2|3}={1|2|3}*{1} are both reducible.
|
|
MAPLE
|
Bk:=proc(k, n) local i, j; 1+add(add(stirling2(i, j), j=1..k)*q^i, i=1..n); end: Ak:=proc(k, n); series(1/Bk(k-1, n)-1/Bk(k, n), q, n+1); end: T:=proc(n, k); coeff(Ak(k, n), q, n); end: # Mike Zabrocki, Feb 04 2005
|
|
MATHEMATICA
|
b[k_, n_] := 1 + Sum[ q^i*Sum[ StirlingS2[i, j], {j, 1, k}], {i, 1, n}]; a[k_, n_] := Series[1/b[k-1, n] - 1/b[k, n], {q, 0, n+1}]; t[n_, k_] := SeriesCoefficient[a[k, n], n]; t[1, 1] = 1; Flatten[ Table[ t[n, k], {n, 1, 11}, {k, 1, n}]] (* Jean-François Alcover, Jun 26 2012, after Mike Zabrocki *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|