VOOZH about

URL: https://oeis.org/A256117

⇱ A256117 - OEIS

login
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
OFFSET
0,6
COMMENTS
T(n,k) is the number of ordered rooted trees with n colored edges counted up to permutations of the colors, such that each edge can be k different colors, no parent and child edge are the same color, and all k colors appear at least once. - John Tyler Rascoe, Nov 26 2025
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.
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
G.f. of column k: (1/k!) * Sum_{i=0..k} (-1)^i * binomial(k,k-i)/(1 - 2*(k-i)*x/(1 + sqrt(1 - 4*(k-i-1)*x))). - John Tyler Rascoe, Nov 25 2025
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.
Main diagonal gives A000108.
T(n+2,n+1) gives A002055(n+5).
Row sums give A258498.
T(2n,n) gives A258499.
Sequence in context: A021836 A255306 A072551 * A352372 A219034 A372244
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Mar 15 2015
STATUS
approved