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

%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