A124292 Number of free generators of degree n of symmetric polynomials in 4 noncommuting variables.

1, 1, 2, 6, 21, 78, 297, 1143, 4419, 17118, 66366, 257391, 998406, 3873015, 15024609, 58285737, 226111986, 877174110, 3402893997, 13201132950, 51212274057, 198672129783, 770725711035, 2989941920334, 11599136512038, 44997518922327, 174562710686622

Offset

1,3

Comments

Also the number of non-splitable set partitions (see Bergeron et al. reference) of length <= 4.

Also the number of nonisomorphic graded posets with 0 and 1 of rank n with no 3-element antichain. - Richard Stanley, Nov 30 2011

Also the number of nonisomorphic graded posets with 0 of rank n+1 with no 3-element antichain. (Using Stanley's definition of graded, that all maximal chains have length n.) - David Nacin, Feb 26 2012

References

R. Stanley, Enumerative combinatorics. Vol. 1, Cambridge University Press, Cambridge, 1997, pages 96-100.

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

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; MR2398749, Cand. J. Math 60 (2008) 266-296.

Yibo Gao and Kaarel Hänni, Boolean elements in the Bruhat order, arXiv:2007.08490 [math.CO], 2020.

R. P. Stanley, An Equivalence Relation on the Symmetric Group and Multiplicity-free Flag h-Vectors

M. C. Wolf, Symmetric functions of noncommutative elements, Duke Math. J. 2 (1936), 626-637.

Index entries for linear recurrences with constant coefficients, signature (6,-9,3).

Formula

O.g.f.: (1 - 5*q + 5*q^2)/(1 - 6*q + 9*q^2 - 3*q^3) = 1 - 1/(Sum_{k=0..4} q^k/(Product_{i=1..k} (1-i*q))).

a(n) = 6*a(n-1) - 9*a(n-2) + 3*a(n-3). - David Nacin, Feb 11 2012

a(n) = A055105(n,1) + A055105(n,2) + A055105(n,3) + A055105(n,4) = A055106(n,1) + A055106(n,2) + A055106(n,3).

Given matrix A = [[2,1,1],[1,3,0],[1,1,1]], a(n+1) = top left entry in A^n. - David Nacin, Feb 11 2012

a(n) = (1/3)*(x^(n-2) + y^(n-2) + z^(n-2)) for x = (2*cos(Pi/18))^2, y = (2*cos(5*Pi/18))^2, and z = (2*cos(7*Pi/18))^2. - Greg Dresden, Jan 28 2023

Maple

a:= n-> (Matrix([[2, 1, 1]]). Matrix(3, (i, j)-> if i=j-1 then 1 elif j=1 then [6, -9, 3][i] else 0 fi)^(n-1))[1, 3]: seq(a(n), n=1..26); # Alois P. Heinz, Sep 05 2008

Mathematica

m = {{2, 1, 1}, {1, 3, 0}, {1, 1, 1}}; Table[MatrixPower[m, n][[1, 1]], {n, 0, 40}] (* David Nacin, Feb 11 2012 *)
LinearRecurrence[{6, -9, 3}, {1, 1, 2}, 70] (* Vladimir Joseph Stephan Orlovsky, Feb 26 2012 *)

Prog

(Python)
def a(n, adict={1:1, 2:1, 3:2}):
    if n in adict:
        return adict[n]
    adict[n]=6*a(n-1)-9*a(n-2)+3*a(n-3)
    return adict[n] # David Nacin, Mar 04 2012

Crossrefs

Cf. A055105, A055106, A055107, A074664, A001519, A124293, A124294, A124295.

Sequence in context: A144169 A355152 A363813 * A277221 A360168 A129776

Adjacent sequences: A124289 A124290 A124291 * A124293 A124294 A124295

Keyword

nonn

Author

Mike Zabrocki, Oct 24 2006

Status

approved