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
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
KEYWORD
nonn,easy
AUTHOR
Mike Zabrocki, Aug 31 2006
STATUS
approved