%I #62 Jan 29 2023 06:03:17
%S 1,1,2,6,21,78,297,1143,4419,17118,66366,257391,998406,3873015,
%T 15024609,58285737,226111986,877174110,3402893997,13201132950,
%U 51212274057,198672129783,770725711035,2989941920334,11599136512038,44997518922327,174562710686622
%N Number of free generators of degree n of symmetric polynomials in 4 noncommuting variables.
%C Also the number of non-splitable set partitions (see Bergeron et al. reference) of length <= 4.
%C Also the number of nonisomorphic graded posets with 0 and 1 of rank n with no 3-element antichain. - _Richard Stanley_, Nov 30 2011
%C 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
%D R. Stanley, Enumerative combinatorics. Vol. 1, Cambridge University Press, Cambridge, 1997, pages 96-100.
%H Vincenzo Librandi, <a href="/A124292/b124292.txt">Table of n, a(n) for n = 1..1000</a>
%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; <a href="http://www.ams.org/mathscinet-getitem?mr=2398749">MR2398749</a>, Cand. J. Math 60 (2008) 266-296.
%H Yibo Gao and Kaarel Hänni, <a href="https://arxiv.org/abs/2007.08490">Boolean elements in the Bruhat order</a>, arXiv:2007.08490 [math.CO], 2020.
%H R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/multfree.pdf">An Equivalence Relation on the Symmetric Group and Multiplicity-free Flag h-Vectors</a>
%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.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (6,-9,3).
%F 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))).
%F a(n) = 6*a(n-1) - 9*a(n-2) + 3*a(n-3). - _David Nacin_, Feb 11 2012
%F a(n) = A055105(n,1) + A055105(n,2) + A055105(n,3) + A055105(n,4) = A055106(n,1) + A055106(n,2) + A055106(n,3).
%F 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
%F 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
%p 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
%t m = {{2, 1, 1}, {1, 3, 0}, {1, 1, 1}}; Table[MatrixPower[m, n][[1,1]], {n, 0, 40}] (* _David Nacin_, Feb 11 2012 *)
%t LinearRecurrence[{6, -9, 3}, {1, 1, 2}, 70] (* _Vladimir Joseph Stephan Orlovsky_, Feb 26 2012 *)
%o (Python)
%o def a(n, adict={1:1, 2:1, 3:2}):
%o if n in adict:
%o return adict[n]
%o adict[n]=6*a(n-1)-9*a(n-2)+3*a(n-3)
%o return adict[n] # _David Nacin_, Mar 04 2012
%Y Cf. A055105, A055106, A055107, A074664, A001519, A124293, A124294, A124295.
%K nonn
%O 1,3
%A _Mike Zabrocki_, Oct 24 2006