login
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.
2

%I #15 Jul 14 2015 10:37:40

%S 0,1,91,869,4895,21562,83728,296268,977026,2990967,8418649,21740455,

%T 51758345,114517208,237528214,465636886,868918932,1553027197,

%U 2672453415,4447208761,7183467523,11298758534,17352329324,26081348272,38443650358,55667772435,79311064261

%N 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.

%H Alois P. Heinz, <a href="/A213287/b213287.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (9,-36,84,-126,126,-84,36,-9,1).

%F 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.

%F 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.

%e a(0) = 0: no word of length 8 is possible for an empty alphabet.

%e a(1) = 1: aaaaaaaa for alphabet {a}.

%e a(2) = 91: aaaaaaaa, aaaaaaab, ..., baababab, bbbbbbbb for alphabet {a,b}.

%p a:= n-> n*(-417562+ (1092135+ (-1113650+ (587165+ (-175728+ (30520+ (-2880+120*n) *n) *n) *n) *n) *n) *n)/120:

%p seq(a(n), n=0..40);

%Y Row n=8 of A213276.

%K nonn,easy

%O 0,3

%A _Alois P. Heinz_, Jun 08 2012