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

Author

Alois P. Heinz, Jun 08 2012

Keywords

• nonn
• easy

Examples

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

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

Crossrefs

Row n=4 of A213276.

Programs

Maple

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

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.