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

1, 1, 1, 3, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 196608, 393216, 786432, 1572864, 3145728, 6291456, 12582912, 25165824, 50331648, 100663296, 201326592, 402653184, 805306368, 1610612736, 3221225472, 6442450944, 12884901888, 25769803776

Offset: 0

Author

Mike Zabrocki, Aug 31 2006

Keywords

• nonn
• easy

Comments

Except for first couple of terms, series agrees with A003945.

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

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

Also the number of compositions of n whose first or last part is equal to 1, for n >= 1. - Peter Luschny, Jan 29 2024

Examples

			a(1) = 1 because x1 - x2 is killed by d_x1 + d_x2.
a(2) = 1 because x1 x2 - x2 x1 is killed by d_x1+d_x2, d_x1^2 + d_x2^2.
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.
From _Peter Luschny_, Jan 29 2024: (Start)
Compositions of n with 1 in the first or the last slot.
 1: [1];
 2: [1, 1];
 3: [1, 1, 1], [1, 2], [2, 1];
 4: [1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [3, 1];
 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].
(End)
		

References

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

Links

• 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. See also, Canad. J. Math. 60 (2008), no. 2, 266-296.
• C. Chevalley, Invariants of finite groups generated by reflections, Amer. J. Math. 77 (1955), 778-782.
• Index entries for linear recurrences with constant coefficients, signature (2).

Crossrefs

Cf. A003945, A034008, A122367, A122392, A122393, A122394.

Programs

Maple

coeffs(convert(series((1-q)*(1-q^2)/(1-2*q),q,20),`+`)-O(q^20),q);

Mathematica

Table[Ceiling[2^(n-2)] + Floor[2^(n-3)], {n,0,30}] (* Martin Grymel, Oct 17 2012 *)

Formula

G.f.: (1-q)*(1-q^2)/(1-2*q).

a(n) = 2^n - 2^(n-1) - 2^(n-2) + 2^(n-3) (for n > 2).

a(0) = 1, a(1) = 1, a(2) = 1, a(n) = 3*2^(n-3) for n > 2.

a(n) = 3*2^(n-3) = 2^(n-3) + 2^(n-2) for n >= 3. - Jaroslav Krizek, Aug 17 2009

a(n) = ceiling(2^(n-2)) + floor(2^(n-3)). - Martin Grymel, Oct 17 2012

E.g.f.: (5 + 3*exp(2*x) + 2*x - 2*x^2)/8. - Stefano Spezia, Jan 26 2025

Extensions

More terms from Michel Marcus, Jan 26 2025