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,3

Links

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

Formula

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

Example

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.

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 *)

Crossrefs

Column k=3 of A240608.

Sequence in context: A160438 A335725 A367656 * A054657 A024576 A057960

Adjacent sequences: A240606 A240607 A240608 * A240610 A240611 A240612

Keyword

nonn

Author

Alois P. Heinz, Apr 09 2014

Status

approved