A294603 Number of words of semilength n over n-ary alphabet, either empty or beginning with the first letter of the alphabet, such that the index set of occurring letters is an integer interval [1, k], that can be built by repeatedly inserting doublets into the initially empty word.

1, 1, 3, 20, 231, 3864, 85360, 2353546, 77963599, 3019479344, 133966276692, 6702399275538, 373406941221160, 22930441709648290, 1539004344848618466, 112089683771614695478, 8805334896381292460191, 742162775145283382779168, 66809386370870410069346476

Offset

0,3

Links

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

Formula

a(n) = Sum_{k=0..n} A256116(n,k).

Example

a(0) = 1: the empty word.
a(1) = 1: aa.
a(2) = 3: aaaa, aabb, abba.
a(3) = 20: aaaaaa, aaaabb, aaabba, aabaab, aabbaa, aabbbb, aabbcc, aabccb, aacbbc, aaccbb, abaaba, abbaaa, abbabb, abbacc, abbbba, abbcca, abccba, acbbca, accabb, accbba.

Maple

A:= proc(n, k) option remember; `if`(n=0, 1, k/n*
      add(binomial(2*n, j) *(n-j) *(k-1)^j, j=0..n-1))
    end:
T:= proc(n, k) option remember;
      add(A(n, k-i)*(-1)^i*binomial(k, i), i=0..k)/`if`(k=0, 1, k)
    end:
a:= n-> add(T(n, k), k=0..n):
seq(a(n), n=0..20);

Mathematica

A[n_, k_] := A[n, k] = If[n == 0, 1, k/n*
     Sum[Binomial[2*n, j]*(n-j) *If[j == 0, 1, (k - 1)^j], {j, 0, n - 1}]];
T[n_, k_] := T[n, k] =
     Sum[A[n, k - i]*(-1)^i*Binomial[k, i], {i, 0, k}]/If[k == 0, 1, k];
a[n_] := Sum[T[n, k], {k, 0, n}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 19 2022, after Alois P. Heinz *)

Crossrefs

Row sums of A256116.

Cf. A258498.

Sequence in context: A119758 A108527 A194972 * A240957 A335871 A195135

Adjacent sequences: A294600 A294601 A294602 * A294604 A294605 A294606

Keyword

nonn

Author

Alois P. Heinz, Nov 03 2017

Status

approved