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

Author

Alois P. Heinz, Nov 03 2017

Keywords

• nonn

Examples

			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.
		

Links

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

Crossrefs

Row sums of A256116.

Cf. A258498.

Programs

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

Formula

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