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).

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

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

Table of n, a(n) for n=1..63.

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.

W. Y. C. Chen, T. X. S. Li and D. G. L. Wang, A Bijection between Atomic Partitions and Unsplitable Partitions, Electron. J. Combin. 18 (2011), no. 1, Paper 7, 7 pp.

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

Row sums are A074664. Cf. A055106, A055107.

Cf. A000110, A008277.

Sequence in context: A173018 A369971 A362868 * A348600 A200545 A294522

Adjacent sequences: A055102 A055103 A055104 * A055106 A055107 A055108

Keyword

nonn,tabl,nice

Author

N. J. A. Sloane, Jun 14 2000

Extensions

More terms from Mike Zabrocki, Feb 04 2005

Status

approved