A294603 -id:A294603 - cp's OEIS frontend

A256116 Number T(n,k) of length 2n k-ary words, either empty or beginning with the first letter of the alphabet and using each letter at least once, that can be built by repeatedly inserting doublets into the initially empty word; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 2, 0, 1, 9, 10, 0, 1, 34, 112, 84, 0, 1, 125, 930, 1800, 1008, 0, 1, 461, 7018, 26400, 35640, 15840, 0, 1, 1715, 51142, 334152, 816816, 840840, 308880, 0, 1, 6434, 368464, 3944220, 15550080, 27824160, 23063040, 7207200

Offset: 0

Alois P. Heinz, Mar 15 2015

			T(3,2) = 9: aaaabb, aaabba, aabaab, aabbaa, aabbbb, abaaba, abbaaa, abbabb, abbbba.
T(3,3) = 10: aabbcc, aabccb, aacbbc, aaccbb, abbacc, abbcca, abccba, acbbca, accabb, accbba.
T(4,2) = 34: aaaaaabb, aaaaabba, aaaabaab, aaaabbaa, aaaabbbb, aaabaaba, aaabbaaa, aaabbabb, aaabbbba, aabaaaab, aabaabaa, aabaabbb, aababbab, aabbaaaa, aabbaabb, aabbabba, aabbbaab, aabbbbaa, aabbbbbb, abaaaaba, abaabaaa, abaababb, abaabbba, ababbaba, abbaaaaa, abbaaabb, abbaabba, abbabaab, abbabbaa, abbabbbb, abbbaaba, abbbbaaa, abbbbabb, abbbbbba.
T(4,4) = 84: aabbccdd, aabbcddc, aabbdccd, aabbddcc, aabccbdd, aabccddb, aabcddcb, aabdccdb, aabddbcc, aabddccb, aacbbcdd, aacbbddc, aacbddbc, aaccbbdd, aaccbddb, aaccdbbd, aaccddbb, aacdbbdc, aacddbbc, aacddcbb, aadbbccd, aadbbdcc, aadbccbd, aadcbbcd, aadccbbd, aadccdbb, aaddbbcc, aaddbccb, aaddcbbc, aaddccbb, abbaccdd, abbacddc, abbadccd, abbaddcc, abbccadd, abbccdda, abbcddca, abbdccda, abbddacc, abbddcca, abccbadd, abccbdda, abccddba, abcddcba, abdccdba, abddbacc, abddbcca, abddccba, acbbcadd, acbbcdda, acbbddca, acbddbca, accabbdd, accabddb, accadbbd, accaddbb, accbbadd, accbbdda, accbddba, accdbbda, accddabb, accddbba, acdbbdca, acddbbca, acddcabb, acddcbba, adbbccda, adbbdacc, adbbdcca, adbccbda, adcbbcda, adccbbda, adccdabb, adccdbba, addabbcc, addabccb, addacbbc, addaccbb, addbbacc, addbbcca, addbccba, addcbbca, addccabb, addccbba.
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,    2;
  0, 1,    9,    10;
  0, 1,   34,   112,     84;
  0, 1,  125,   930,   1800,   1008;
  0, 1,  461,  7018,  26400,  35640,  15840;
  0, 1, 1715, 51142, 334152, 816816, 840840, 308880;

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-2 give: A000007, A057427, A010763(n-1) for n>0.
Main diagonal gives A065866(n-1) (for n>0).
Row sums give A294603.
Cf. A183135, A256117.

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(A(n, k-i)*(-1)^i*binomial(k, i), i=0..k)/
    `if`(k=0, 1, k):
seq(seq(T(n, k), k=0..n), n=0..12);

Unprotect[Power]; 0^0 = 1; A[n_, k_] := A[n, k] = If[n==0, 1, k/n*Sum[ Binomial[2*n, j]*(n-j)*(k-1)^j, {j, 0, n-1}]];
T[n_, k_] := Sum[A[n, k-i]*(-1)^i*Binomial[k, i], {i, 0, k}]/If[k==0, 1, k]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 22 2017, translated from Maple *)

T(n,k) = (Sum_{i=0..k} (-1)^i * C(k,i) * A183135(n,k-i)) / A028310(k).

T(n,k) = (k-1)! * A256117(n,k) for k > 0.

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.

Original entry on oeis.org

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

Offset: 0

Alois P. Heinz, May 31 2015

nonn

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

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

Row sums of A256117.

Cf. A294603, A321031.

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

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

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

cp's OEIS Frontend

A256116 Number T(n,k) of length 2n k-ary words, either empty or beginning with the first letter of the alphabet and using each letter at least once, that can be built by repeatedly inserting doublets into the initially empty word; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula