A213288 Number of 9-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, 162, 2074, 13280, 64924, 273248, 1050777, 3754472, 12602451, 39598078, 115470300, 311272072, 777274550, 1808153452, 3946185587, 8137258032, 15957939797, 29935676058, 53988338158, 94013898576, 158665898944, 260355640952, 416527654621, 651260985944

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 (10,-45,120,-210,252,-210,120,-45,10,-1).

Formula

a(n) = n*(3353416 -9177198*n +10002755*n^2 -5796570*n^3 +1984509*n^4 -416052*n^5 +52920*n^6 -3780*n^7 +120*n^8)/120.

G.f.: x*(1+152*x +499*x^2 -290*x^3 +6224*x^4 +6496*x^5 +41203*x^6 +52034*x^7 +256561*x^8) / (1-x)^10.

Example

a(0) = 0: no word of length 9 is possible for an empty alphabet.
a(1) = 1: aaaaaaaaa for alphabet {a}.
a(2) = 162: aaaaaaaaa, aaaaaaaab, ..., baabababa, bbbbbbbbb for alphabet {a,b}.

Maple

a:= n-> n*(3353416+ (-9177198+ (10002755+ (-5796570+ (1984509+ (-416052+ (52920+ (-3780+120*n) *n) *n) *n) *n) *n) *n) *n)/120:
seq(a(n), n=0..40);

Crossrefs

Row n=9 of A213276.

Sequence in context: A206145 A342850 A304166 * A302532 A288489 A303413

Adjacent sequences: A213285 A213286 A213287 * A213289 A213290 A213291

Keyword

nonn,easy

Author

Alois P. Heinz, Jun 08 2012

Status

approved