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

Offset

0,4

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 17 2009

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

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

Table of n, a(n) for n=0..29.

N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math.CO/0502082 , 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).

Formula

G.f.: (1-q)*(1-q^2)/(1-2*q) 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

Example

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)

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 *)

Crossrefs

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

Sequence in context: A169064 A169112 A169160 * A169208 A169256 A169304

Adjacent sequences: A122388 A122389 A122390 * A122392 A122393 A122394

Keyword

nonn,easy

Author

Mike Zabrocki, Aug 31 2006

Status

approved