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

Author

Alois P. Heinz, Jun 08 2012

Keywords

• nonn
• easy

Examples

			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}.
		

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).

Crossrefs

Row n=8 of A213276.

Programs

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);

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.