The On-Line Encyclopedia of Integer Sequences (OEIS)

A124292 revision #57

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

(list; graph; refs; listen; history; text; internal format)

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, M. Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables , 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.