A213283 Number of 4-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, 9, 36, 118, 315, 711, 1414, 2556, 4293, 6805, 10296, 14994, 21151, 29043, 38970, 51256, 66249, 84321, 105868, 131310, 161091, 195679, 235566, 281268, 333325, 392301, 458784, 533386, 616743, 709515, 812386, 926064, 1051281, 1188793, 1339380, 1503846

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 (5,-10,10,-5,1).

Formula

a(n) = n*(-9+17*n-8*n^2+2*n^3)/2.

G.f.: x*(1+4*x+x^2+18*x^3)/(1-x)^5.

Example

a(0) = 0: no word of length 4 is possible for an empty alphabet.
a(1) = 1: aaaa for alphabet {a}.
a(2) = 9: aaaa, aaab, aaba, aabb, abaa, abab, baaa, baab, bbbb for alphabet {a,b}.
a(3) = 36: aaaa, aaab, aaac, aaba, aabb, aabc, aaca, aacb, aacc, abaa, abab, abac, abca, acaa, acab, acac, acba, baaa, baab, baac, baca, bbbb, bbbc, bbcb, bbcc, bcaa, bcbb, bcbc, caaa, caab, caac, caba, cbaa, cbbb, cbbc, cccc for alphabet {a,b,c}.

Maple

a:= n-> n*(-9+(17+(-8+2*n)*n)*n)/2:
seq(a(n), n=0..40);

Crossrefs

Row n=4 of A213276.

Sequence in context: A369888 A259279 A168569 * A188162 A353389 A023872

Adjacent sequences: A213280 A213281 A213282 * A213284 A213285 A213286

Keyword

nonn,easy

Author

Alois P. Heinz, Jun 08 2012

Status

approved