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: A042418 A042420 A372560 * A372444 A174617 A055339

Adjacent sequences: A213282 A213283 A213284 * A213286 A213287 A213288

Keyword

nonn,easy

Author

Alois P. Heinz, Jun 08 2012

Status

approved