|
|
A256117
|
|
Number T(n,k) of length 2n words such that all letters of the k-ary alphabet occur at least once and are introduced in ascending order and which can be built by repeatedly inserting doublets into the initially empty word; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
|
|
14
|
|
|
1, 0, 1, 0, 1, 2, 0, 1, 9, 5, 0, 1, 34, 56, 14, 0, 1, 125, 465, 300, 42, 0, 1, 461, 3509, 4400, 1485, 132, 0, 1, 1715, 25571, 55692, 34034, 7007, 429, 0, 1, 6434, 184232, 657370, 647920, 231868, 32032, 1430, 0, 1, 24309, 1325609, 7488228, 11187462, 6191808, 1447992, 143208, 4862
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
COMMENTS
|
In general, column k>2 is asymptotic to (4*(k-1))^n / ((k-2)^2 * (k-2)! * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jun 01 2015
|
|
LINKS
|
|
|
FORMULA
|
T(n,k) = Sum_{i=0..k} (-1)^i * A183135(n,k-i) / (i!*(k-i)!).
T(n,k) = A256116(n,k) / (k-1)! for k > 0.
|
|
EXAMPLE
|
T(0,0) = 1: (the empty word).
T(1,1) = 1: aa.
T(2,1) = 1: aaaa.
T(2,2) = 2: aabb, abba.
T(3,1) = 1: aaaaaa.
T(3,2) = 9: aaaabb, aaabba, aabaab, aabbaa, aabbbb, abaaba, abbaaa, abbabb, abbbba.
T(3,3) = 5: aabbcc, aabccb, abbacc, abbcca, abccba.
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 2;
0, 1, 9, 5;
0, 1, 34, 56, 14;
0, 1, 125, 465, 300, 42;
0, 1, 461, 3509, 4400, 1485, 132;
0, 1, 1715, 25571, 55692, 34034, 7007, 429;
0, 1, 6434, 184232, 657370, 647920, 231868, 32032, 1430;
...
|
|
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):
seq(seq(T(n, k), k=0..n), n=0..10);
|
|
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}];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Feb 22 2016, after Alois P. Heinz, updated Jan 01 2021 *)
|
|
CROSSREFS
|
Columns k=0-10 give: A000007, A057427, A010763(n-1) (for n>1), A258490, A258491, A258492, A258493, A258494, A258495, A258496, A258497.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|