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

1, 1, 2, 5, 13, 35, 94, 254, 688, 1872, 5115, 14038, 38689, 107055, 297336, 828699, 2317098, 6498114, 18273861, 51521238, 145604868, 412407942, 1170507375, 3328570513, 9482518041, 27059673745, 77340925350, 221382318131, 634578781229, 1821388557507

Offset: 0

Author

Alois P. Heinz, Apr 09 2014

Keywords

• nonn

Examples

			a(3) = 5: 111, 112, 121, 122, 123.
a(4) = 13: 1111, 1112, 1121, 1122, 1123, 1211, 1212, 1213, 1221, 1223, 1231, 1232, 1233.
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.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000

Crossrefs

Column k=3 of A240608.

Programs

Maple

a:= proc(n) option remember; `if`(n<3, [1, 1, 2][n+1],
      ((87*n^5-380*n^4-95*n^3+848*n^2-76*n+96) *a(n-1)
      +(n-1)*(29*n^4-117*n^3+228*n^2+404*n-528) *a(n-2)
      -3*(n-1)*(n-2)*(29*n^3-59*n^2-34*n-96) *a(n-3))/
      ((n-2)*(n+4)*(29*n^3-146*n^2+171*n-150)))
    end:
seq(a(n), n=0..35);

Mathematica

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]}]];
a[n_] := b[n, Min[3, n], {}];
a /@ Range[0, 35] (* Jean-François Alcover, Jan 03 2021, after Alois P. Heinz in A240608 *)

Formula

a(n) ~ 29 * 3^(n+3/2) / (16*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jul 16 2014