A122391 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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

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

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

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

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