A258498 Number of words of length 2n such that the index set of occurring letters is {1, 2, ..., k}, all letters are introduced in ascending order, and the words can be built by repeatedly inserting doublets into the initially empty word.

1, 1, 3, 15, 105, 933, 9988, 124449, 1761287, 27813479, 483482018, 9153385959, 187129080977, 4102129113670, 95861136747795, 2376234441556411, 62216635372018209, 1714347701138957189, 49553280367466054768, 1498300016807379304877, 47270249397381096576643

Offset: 0

Author

Alois P. Heinz, May 31 2015

Keywords

• nonn

Examples

			a(3) = 15: aaaaaa, aaaabb, aaabba, aabaab, aabbaa, aabbbb, abaaba, abbaaa, abbabb, abbbba, aabbcc, aabccb, abbacc, abbcca, abccba.
		

Links

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

Crossrefs

Row sums of A256117.

Cf. A294603, A321031.

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:= (n, k)-> add((-1)^i*A(n, k-i)/(i!*(k-i)!), i=0..k):
a:= n-> add(T(n, k), k=0..n):
seq(a(n), n=0..25);

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_] := Sum[(-1)^i*A[n, k - i]/(i!*(k - i)!), {i, 0, k}];
a[n_] := Sum[T[n, k], {k, 0, n}];
a /@ Range[0, 25] (* Jean-François Alcover, Jan 01 2021, after Alois P. Heinz *)

Formula

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

a(n) ~ Bell(n-1)*Catalan(n) ~ n^n * exp(n/LambertW(n)-1-n) * 4^n / (sqrt(Pi) * sqrt(1+LambertW(n)) * LambertW(n)^(n-1) * n^(5/2)). - Vaclav Kotesovec, Jun 02 2015