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
N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math/0502082 [math.CO], 2005; Canad. J. Math. 60 (2008), no. 2, 266-296.
M. B. Can and B. E. Sagan, Partitions, rooks, and symmetric functions in noncommuting variables, arXiv:math.CO/1008.2950. Electron. J. Combin. 18 (2011), no. 2, Paper 3.
William Y.C. Chen, Teresa X.S. Li, and David G.L. Wang, A Bijection between Atomic Partitions and Unsplitable Partitions, Electron. J. Combin. 18 (2011), no. 1, Paper 7.
M. Rosas and B. Sagan, Symmetric Functions in Noncommuting Variables, Transactions of the American Mathematical Society, 358 (2006), no. 1, 215-232.
M. C. Wolf, Symmetric functions of noncommutative elements, Duke Math. J. 2 (1936), 626-637.
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
N. J. A. Sloane, Jun 14 2000
EXTENSIONS
More terms from Mike Zabrocki, Feb 04 2005
STATUS
approved