A213287 Number of 8-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, 91, 869, 4895, 21562, 83728, 296268, 977026, 2990967, 8418649, 21740455, 51758345, 114517208, 237528214, 465636886, 868918932, 1553027197, 2672453415, 4447208761, 7183467523, 11298758534, 17352329324, 26081348272, 38443650358, 55667772435, 79311064261

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 (9,-36,84,-126,126,-84,36,-9,1).

Formula

a(n) = n*(-417562 +1092135*n -1113650*n^2 +587165*n^3 -175728*n^4 +30520*n^5 -2880*n^6 +120*n^7)/120.

G.f.: x*(1+82*x +86*x^2 +266*x^3 +1273*x^4 +4234*x^5 +5880*x^6 +28498*x^7) / (1-x)^9.

Example

a(0) = 0: no word of length 8 is possible for an empty alphabet.
a(1) = 1: aaaaaaaa for alphabet {a}.
a(2) = 91: aaaaaaaa, aaaaaaab, ..., baababab, bbbbbbbb for alphabet {a,b}.

Maple

a:= n-> n*(-417562+ (1092135+ (-1113650+ (587165+ (-175728+ (30520+ (-2880+120*n) *n) *n) *n) *n) *n) *n)/120:
seq(a(n), n=0..40);

Crossrefs

Row n=8 of A213276.

Sequence in context: A047696 A043459 A038488 * A072393 A085952 A129255

Adjacent sequences: A213284 A213285 A213286 * A213288 A213289 A213290

Keyword

nonn,easy

Author

Alois P. Heinz, Jun 08 2012

Status

approved