A200782 Expansion of 1 / (1 - 6*x + 20*x^3 - 15*x^4 + x^6).

1, 6, 36, 196, 1071, 5796, 31395, 169884, 919413, 4975322, 26924106, 145698840, 788446400, 4266656226, 23088902733, 124944995676, 676136621430, 3658895818470, 19800020091895, 107147296401684, 579824822459421, 3137707025200000

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

Column 5 of A200785.

G.f. corresponds to row 6 of A225682.

Sequence in context: A215453 A267229 A048980 * A055299 A261520 A345340

Adjacent sequences: A200779 A200780 A200781 * A200783 A200784 A200785

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