login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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: A085852 A123125 A173018 * A200545 A294522 A058710

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 17 03:20 EST 2018. Contains 318192 sequences. (Running on oeis4.)