|
%I #39 Jan 05 2021 21:38:59
%S 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,
%T 4400,1485,132,0,1,1715,25571,55692,34034,7007,429,0,1,6434,184232,
%U 657370,647920,231868,32032,1430,0,1,24309,1325609,7488228,11187462,6191808,1447992,143208,4862
%N 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.
%C 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
%H Alois P. Heinz, <a href="/A256117/b256117.txt">Rows n = 0..140, flattened</a>
%F T(n,k) = Sum_{i=0..k} (-1)^i * A183135(n,k-i) / (i!*(k-i)!).
%F T(n,k) = A256116(n,k) / (k-1)! for k > 0.
%e T(0,0) = 1: (the empty word).
%e T(1,1) = 1: aa.
%e T(2,1) = 1: aaaa.
%e T(2,2) = 2: aabb, abba.
%e T(3,1) = 1: aaaaaa.
%e T(3,2) = 9: aaaabb, aaabba, aabaab, aabbaa, aabbbb, abaaba, abbaaa, abbabb, abbbba.
%e T(3,3) = 5: aabbcc, aabccb, abbacc, abbcca, abccba.
%e Triangle T(n,k) begins:
%e 1;
%e 0, 1;
%e 0, 1, 2;
%e 0, 1, 9, 5;
%e 0, 1, 34, 56, 14;
%e 0, 1, 125, 465, 300, 42;
%e 0, 1, 461, 3509, 4400, 1485, 132;
%e 0, 1, 1715, 25571, 55692, 34034, 7007, 429;
%e 0, 1, 6434, 184232, 657370, 647920, 231868, 32032, 1430;
%e ...
%p A:= proc(n, k) option remember; `if`(n=0, 1, k/n*
%p add(binomial(2*n, j)*(n-j)*(k-1)^j, j=0..n-1))
%p end:
%p T:= (n, k)-> add((-1)^i*A(n, k-i)/(i!*(k-i)!), i=0..k):
%p seq(seq(T(n, k), k=0..n), n=0..10);
%t 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 T[n_, k_] := Sum[(-1)^i*A[n, k - i]/(i!*(k - i)!), {i, 0, k}];
%t 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 *)
%Y Columns k=0-10 give: A000007, A057427, A010763(n-1) (for n>1), A258490, A258491, A258492, A258493, A258494, A258495, A258496, A258497.
%Y Main diagonal gives A000108.
%Y T(n+2,n+1) gives A002055(n+5).
%Y Row sums give A258498.
%Y T(2n,n) gives A258499.
%Y Cf. A183135, A256116, A256311.
%K nonn,tabl
%O 0,6
%A _Alois P. Heinz_, Mar 15 2015
|
