OFFSET
0,2
COMMENTS
a(n) is the number of words of length n over an alphabet of size 6 which do not contain any strictly decreasing factor (consecutive subword) of length 3.
Equivalently, dimensions of homogeneous components of the universal associative envelope for a certain nonassociative triple system [Bremner].
This is the g.f. corresponding to row 6 of A225682.
LINKS
R. H. Hardin and N. J. Sloane, Table of n, a(n) for n = 0..239 [The first 210 terms were computed by R. H. Hardin]
M. R. Bremner, Free associative algebras, noncommutative Grobner bases, and universal associative envelopes for nonassociative structures, arXiv:1303.0920 [math.RA], 2013
A. Burstein and T. Mansour, Words restricted by 3-letter generalized multipermutation patterns, Annals. Combin., 7 (2003), 1-14. See Th. 3.13.
Index entries for linear recurrences with constant coefficients, signature (6,0,-20,15,0,-1).
FORMULA
G.f.: 1 / (1 - 6*x + 20*x^3 - 15*x^4 + x^6).
a(n) = 6*a(n-1) - 20*a(n-3) + 15*a(n-4) - a(n-6).
EXAMPLE
a(n) is also the number of words of length n over an alphabet of size 6 which do not contain any strictly increasing factor of length 3. Some solutions for n=5:
..5....5....0....3....2....4....3....3....3....3....0....3....3....1....0....1
..1....5....0....0....4....5....1....1....3....5....1....0....2....0....3....4
..3....5....1....0....4....3....1....4....5....0....1....5....1....0....0....3
..0....0....0....4....1....1....1....4....2....4....1....1....2....5....4....1
..1....4....2....0....0....0....1....3....1....4....3....2....2....2....4....5
MATHEMATICA
CoefficientList[Series[1 / (1 - 6*x + 20*x^3 - 15*x^4 + x^6), {x, 0, 20}], x] (* Vaclav Kotesovec, Jan 26 2015 *)
LinearRecurrence[{6, 0, -20, 15, 0, -1}, {1, 6, 36, 196, 1071, 5796}, 30] (* Harvey P. Dale, Jul 28 2019 *)
PROG
(PARI) Vec(1/(1-6*x+20*x^3-15*x^4+x^6) + O(x^30)) \\ Michel Marcus, Jan 26 2015
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
R. H. Hardin, Nov 22 2011
EXTENSIONS
Entry revised by N. J. A. Sloane, May 17 2013, merging this with A225381
Typo in name corrected by Michel Marcus, Jan 26 2015
STATUS
approved