login
Number of 6-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 Jun 13 2015 00:54:16

%S 0,1,27,165,712,2535,8151,23527,60600,140517,297595,584001,1075152,

%T 1875835,3127047,5013555,7772176,11700777,17167995,24623677,34610040,

%U 47773551,64877527,86815455,114625032,149502925,192820251,246138777,311227840,390081987,484939335

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

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (7,-21,35,-35,21,-7,1).

%F a(n) = n*(-332+757*n-632*n^2+255*n^3-48*n^4+4*n^5)/4.

%F G.f.: x*(1+20*x-3*x^2+89*x^3+106*x^4+507*x^5) / (1-x)^7.

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

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

%e a(2) = 27: aaaaaa, aaaaab, aaaaba, aaaabb, aaabaa, aaabab, aaabba, aaabbb, aabaaa, aabaab, aababa, aababb, aabbaa, aabbab, abaaaa, abaaab, abaaba, abaabb, ababaa, ababab, baaaaa, baaaab, baaaba, baaabb, baabaa, baabab, bbbbbb for alphabet {a,b}.

%p a:= n-> n*(-332+(757+(-632+(255+(-48+4*n)*n)*n)*n)*n)/4:

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

%Y Row n=6 of A213276.

%K nonn,easy

%O 0,3

%A _Alois P. Heinz_, Jun 08 2012