login
Number of 5-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 #12 Jun 13 2015 00:54:15

%S 0,1,14,74,276,895,2506,6104,13224,26061,47590,81686,133244,208299,

%T 314146,459460,654416,910809,1242174,1663906,2193380,2850071,3655674,

%U 4634224,5812216,7218725,8885526,10847214,13141324,15808451,18892370,22440156,26502304

%N Number of 5-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="/A213284/b213284.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (6,-15,20,-15,6,-1).

%F a(n) = n*(94-204*n+155*n^2-45*n^3+6*n^4)/6.

%F G.f.: x*(1+8*x+5*x^2+22*x^3+84*x^4)/(1-x)^6.

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

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

%e a(2) = 14: aaaaa, aaaab, aaaba, aaabb, aabaa, aabab, aabba, abaaa, abaab, ababa, baaaa, baaab, baaba, bbbbb for alphabet {a,b}.

%p a:= n-> n*(94+(-204+(155+(-45+6*n)*n)*n)*n)/6:

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

%Y Row n=5 of A213276.

%K nonn,easy

%O 0,3

%A _Alois P. Heinz_, Jun 08 2012