A213285 Number of 6-length words w over n-ary alphabet such that for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z.

0, 1, 27, 165, 712, 2535, 8151, 23527, 60600, 140517, 297595, 584001, 1075152, 1875835, 3127047, 5013555, 7772176, 11700777, 17167995, 24623677, 34610040, 47773551, 64877527, 86815455, 114625032, 149502925, 192820251, 246138777, 311227840, 390081987, 484939335

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

Formula

a(n) = n*(-332+757*n-632*n^2+255*n^3-48*n^4+4*n^5)/4.

G.f.: x*(1+20*x-3*x^2+89*x^3+106*x^4+507*x^5) / (1-x)^7.

Example

a(0) = 0: no word of length 6 is possible for an empty alphabet.
a(1) = 1: aaaaaa for alphabet {a}.
a(2) = 27: aaaaaa, aaaaab, aaaaba, aaaabb, aaabaa, aaabab, aaabba, aaabbb, aabaaa, aabaab, aababa, aababb, aabbaa, aabbab, abaaaa, abaaab, abaaba, abaabb, ababaa, ababab, baaaaa, baaaab, baaaba, baaabb, baabaa, baabab, bbbbbb for alphabet {a,b}.

Maple

a:= n-> n*(-332+(757+(-632+(255+(-48+4*n)*n)*n)*n)*n)/4:
seq(a(n), n=0..40);

Crossrefs

Row n=6 of A213276.

Sequence in context: A224001 A042418 A042420 * A174617 A055339 A269054

Adjacent sequences: A213282 A213283 A213284 * A213286 A213287 A213288

Keyword

nonn,easy

Author

Alois P. Heinz, Jun 08 2012

Status

approved