|
%I #33 Oct 08 2017 12:34:28
%S 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,
%T 1,232,910,753,223,26,1,0,1,609,3809,4674,2091,405,34,1,0,1,1596,
%U 15521,27161,17220,4926,677,43,1,0,1,4180,62185,151134,130480,51702,10342
%N 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).
%C 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
%H N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, <a href="https://arxiv.org/abs/math/0502082">Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables</a>, arXiv:math/0502082 [math.CO], 2005; Canad. J. Math. 60 (2008), no. 2, 266-296.
%H M. B. Can and B. E. Sagan, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i2p3">Partitions, rooks, and symmetric functions in noncommuting variables</a>, arXiv:math.CO/1008.2950. Electron. J. Combin. 18 (2011), no. 2, Paper 3.
%H W. Y. C. Chen, T. X. S. Li and D. G. L. Wang, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p7">A Bijection between Atomic Partitions and Unsplitable Partitions</a>, Electron. J. Combin. 18 (2011), no. 1, Paper 7, 7 pp.
%H M. Rosas and B. Sagan, <a href="http://dx.doi.org/10.1090/S0002-9947-04-03623-2">Symmetric Functions in Noncommuting Variables</a>, Transactions of the American Mathematical Society, 358 (2006), no. 1, 215-232.
%H M. C. Wolf, <a href="http://dx.doi.org/10.1215/S0012-7094-36-00253-3">Symmetric functions of noncommutative elements</a>, Duke Math. J. 2 (1936), 626-637.
%F 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
%e 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; ...
%e Triangle starts:
%e 1;
%e 0, 1;
%e 0, 1, 1;
%e 0, 1, 4, 1;
%e 0, 1, 12, 8, 1;
%e ...
%e 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.
%p 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
%t 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_ *)
%Y Row sums are A074664. Cf. A055106, A055107.
%Y Cf. A000110, A008277.
%K nonn,tabl,nice
%O 1,9
%A _N. J. A. Sloane_, Jun 14 2000
%E More terms from _Mike Zabrocki_, Feb 04 2005
|
