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

Author

Mike Zabrocki, Oct 24 2006

Keywords

• nonn

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

Crossrefs

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

Programs

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

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

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