%I #50 Jan 26 2025 13:14:22
%S 1,1,1,3,6,12,24,48,96,192,384,768,1536,3072,6144,12288,24576,49152,
%T 98304,196608,393216,786432,1572864,3145728,6291456,12582912,25165824,
%U 50331648,100663296,201326592,402653184,805306368,1610612736,3221225472,6442450944,12884901888,25769803776
%N Dimension of 2-variable non-commutative harmonics (Hausdorff derivative). The dimension of the space of non-commutative polynomials in 2 variables which are killed by all symmetric differential operators (where for a monomial w, d_{xi} ( w ) = sum over all subwords of w deleting xi once).
%C Except for first couple of terms, series agrees with A003945.
%C a(n) written in base 2: a(0) = 1, a(1) = 1, a(2) = 1, a(n) for n >= 3: 11, 110, 11000, 110000, ..., i.e.: 2 times 1, (n-3) times 0 (see A003953(n-2)). - _Jaroslav Krizek_, Aug 17 2009
%C For n>=2, a(n) equals the numbers of words of length n-2 on alphabet {0,1,2} containing no subwords 00, 11 and 22. - _Milan Janjic_, Jan 31 2015
%C Also the number of compositions of n whose first or last part is equal to 1, for n >= 1. - _Peter Luschny_, Jan 29 2024
%D C. Reutenauer, Free Lie algebras. London Mathematical Society Monographs. New Series, 7. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1993. xviii+269 pp.
%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. See <a href="https://doi.org/10.4153/CJM-2008-013-4">also</a>, Canad. J. Math. 60 (2008), no. 2, 266-296.
%H C. Chevalley, <a href="http://www.jstor.org/stable/2372597">Invariants of finite groups generated by reflections</a>, Amer. J. Math. 77 (1955), 778-782.
%H <a href="/index/Rec#order_01">Index entries for linear recurrences with constant coefficients</a>, signature (2).
%F G.f.: (1-q)*(1-q^2)/(1-2*q).
%F a(n) = 2^n - 2^(n-1) - 2^(n-2) + 2^(n-3) (for n > 2).
%F a(0) = 1, a(1) = 1, a(2) = 1, a(n) = 3*2^(n-3) for n > 2.
%F a(n) = 3*2^(n-3) = 2^(n-3) + 2^(n-2) for n >= 3. - _Jaroslav Krizek_, Aug 17 2009
%F a(n) = ceiling(2^(n-2)) + floor(2^(n-3)). - _Martin Grymel_, Oct 17 2012
%F E.g.f.: (5 + 3*exp(2*x) + 2*x - 2*x^2)/8. - _Stefano Spezia_, Jan 26 2025
%e a(1) = 1 because x1 - x2 is killed by d_x1 + d_x2.
%e a(2) = 1 because x1 x2 - x2 x1 is killed by d_x1+d_x2, d_x1^2 + d_x2^2.
%e a(3) = 3 because x1 x1 x2 - 2 x1 x2 x1 + x2 x1 x1, x1 x2 x2 - 2 x2 x1 x2 + x2 x2 x1, x1 x1 x2 - x1 x2 x1 - x2 x1 x2 + x2 x2 x1 are all killed by d_x1 + d_x2, d_x1^2 + d_x2^2, d_x1 d_x2, d_x1^3 + d_x2^3 and d_x1^2 d_x2 + d_x1 d_x2^2.
%e From _Peter Luschny_, Jan 29 2024: (Start)
%e Compositions of n with 1 in the first or the last slot.
%e 1: [1];
%e 2: [1, 1];
%e 3: [1, 1, 1], [1, 2], [2, 1];
%e 4: [1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [3, 1];
%e 5: [1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 1], [1, 1, 3], [1, 2, 1, 1], [1, 2, 2], [1, 3, 1], [1, 4], [2, 1, 1, 1], [2, 2, 1], [3, 1, 1], [4, 1].
%e (End)
%p coeffs(convert(series((1-q)*(1-q^2)/(1-2*q),q,20),`+`)-O(q^20),q);
%t Table[Ceiling[2^(n-2)] + Floor[2^(n-3)], {n,0,30}] (* _Martin Grymel_, Oct 17 2012 *)
%Y Cf. A003945, A034008, A122367, A122392, A122393, A122394.
%K nonn,easy
%O 0,4
%A _Mike Zabrocki_, Aug 31 2006
%E More terms from _Michel Marcus_, Jan 26 2025