|
%I #13 Jan 03 2021 06:40:22
%S 1,1,2,5,13,35,94,254,688,1872,5115,14038,38689,107055,297336,828699,
%T 2317098,6498114,18273861,51521238,145604868,412407942,1170507375,
%U 3328570513,9482518041,27059673745,77340925350,221382318131,634578781229,1821388557507
%N Number of n-length words w over a 3-ary alphabet such that w is empty or a prefix z concatenated with letter a_i and i=1 or 0 < #(z,a_{i-1}) >= #(z,a_i), where #(z,a_i) counts the occurrences of the i-th letter in z.
%H Alois P. Heinz, <a href="/A240609/b240609.txt">Table of n, a(n) for n = 0..1000</a>
%F a(n) ~ 29 * 3^(n+3/2) / (16*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Jul 16 2014
%e a(3) = 5: 111, 112, 121, 122, 123.
%e a(4) = 13: 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1213, 1221, 1223, 1231, 1232, 1233.
%e a(5) = 35: 11111, 11112, 11121, 11122, 11123, 11211, 11212, 11213, 11221, 11222, 11223, 11231, 11232, 11233, 12111, 12112, 12113, 12121, 12122, 12123, 12131, 12132, 12133, 12211, 12212, 12213, 12231, 12233, 12311, 12312, 12313, 12321, 12323, 12331, 12332.
%p a:= proc(n) option remember; `if`(n<3, [1, 1, 2][n+1],
%p ((87*n^5-380*n^4-95*n^3+848*n^2-76*n+96) *a(n-1)
%p +(n-1)*(29*n^4-117*n^3+228*n^2+404*n-528) *a(n-2)
%p -3*(n-1)*(n-2)*(29*n^3-59*n^2-34*n-96) *a(n-3))/
%p ((n-2)*(n+4)*(29*n^3-146*n^2+171*n-150)))
%p end:
%p seq(a(n), n=0..35);
%t b[n_, k_, l_] := b[n, k, l] = If[n == 0, 1, If[Length[l] < k, b[n - 1, k, Append[l, 1]], 0] + Sum[If[i == 1 || l[[i]] <= l[[i - 1]], b[n - 1, k, ReplacePart[l, i -> l[[i]] + 1]], 0], {i, 1, Length[l]}]];
%t a[n_] := b[n, Min[3, n], {}];
%t a /@ Range[0, 35] (* _Jean-François Alcover_, Jan 03 2021, after _Alois P. Heinz_ in A240608 *)
%Y Column k=3 of A240608.
%K nonn
%O 0,3
%A _Alois P. Heinz_, Apr 09 2014
|
