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

Links

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

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

Example

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

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

Crossrefs

Row sums of A256117.

Cf. A294603, A321031.

Sequence in context: A246860 A357596 A249014 * A189919 A360579 A251598

Adjacent sequences: A258495 A258496 A258497 * A258499 A258500 A258501

Keyword

nonn

Author

Alois P. Heinz, May 31 2015

Status

approved