login
Square array A(n,k) by antidiagonals. A(n,k) is the number of length 2n k-ary words (n,k>=0), either empty or beginning with the first character of the alphabet, that can be built by repeatedly inserting doublets into the initially empty word.
22

%I #35 Oct 04 2018 19:59:08

%S 1,1,0,1,1,0,1,1,1,0,1,1,3,1,0,1,1,5,10,1,0,1,1,7,29,35,1,0,1,1,9,58,

%T 181,126,1,0,1,1,11,97,523,1181,462,1,0,1,1,13,146,1145,4966,7941,

%U 1716,1,0,1,1,15,205,2131,14289,48838,54573,6435,1,0

%N Square array A(n,k) by antidiagonals. A(n,k) is the number of length 2n k-ary words (n,k>=0), either empty or beginning with the first character of the alphabet, that can be built by repeatedly inserting doublets into the initially empty word.

%C Column k > 2 is asymptotic to 2^(2*n) * (k-1)^(n+1) / ((k-2)^2 * sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Sep 07 2014

%H Alois P. Heinz, <a href="/A183134/b183134.txt">Antidiagonals n = 0..140, flattened</a>

%H C. Kassel and C. Reutenauer, <a href="https://arxiv.org/abs/1303.3481">Algebraicity of the zeta function associated to a matrix over a free group algebra</a>, arXiv preprint arXiv:1303.3481, 2013

%H A. Lakshminarayan, Z. Puchala, K. Zyczkowski, <a href="https://arxiv.org/abs/1407.1169">Diagonal unitary entangling gates and contradiagonal quantum states</a>, arXiv preprint arXiv:1407.1169, 2014

%F A(n,k) = 1 if n=0, A(n,k) = k if n>0 and k<=1, and A(n,k) = 1/n * Sum_{j=0..n-1} C(2*n,j)*(n-j)*(k-1)^j else.

%F A(n,k) = A183135(n,k) if n=0 or k<2, A(n,k) = A183135(n,k)/k else.

%F G.f. of column k: 1/(1-k*x) if k<2, (1-1/k) * (1 + 2 / (k-2 + k * sqrt (1-(4*k-4)*x))) else.

%e A(3,2) = 10, because 10 words of length 6 beginning with the first character of the 2-letter alphabet {a, b} can be built by repeatedly inserting doublets (words with two equal letters) into the initially empty word: aaaaaa, aaaabb, aaabba, aabaab, aabbaa, aabbbb, abaaba, abbaaa, abbabb, abbbba.

%e Square array A(n,k) begins:

%e 1, 1, 1, 1, 1, 1, ...

%e 0, 1, 1, 1, 1, 1, ...

%e 0, 1, 3, 5, 7, 9, ...

%e 0, 1, 10, 29, 58, 97, ...

%e 0, 1, 35, 181, 523, 1145, ...

%e 0, 1, 126, 1181, 4966, 14289, ...

%p A:= proc(n, k)

%p local j;

%p if n=0 then 1

%p elif k<=1 then k

%p else add(binomial(2*n,j)*(n-j)*(k-1)^j, j=0..n-1)/n

%p fi

%p end:

%p seq(seq(A(n, d-n), n=0..d), d=0..10);

%t a[n_, k_] := If[ n == 0, 1 , If[ k <= 1, k, Sum [Binomial[2*n, j]*(n-j)*(k-1)^j, {j, 0, n-1}] / n ] ]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 10}] // Flatten (* _Jean-François Alcover_, Dec 09 2013, translated from Maple *)

%Y Rows 0-10 give: A000012, A057427, A004273, A079273(k) for k>0, A194716, A194717, A194718, A194719, A194720, A194721, A194722.

%Y Columns 0-10 give: A000007, A000012, A001700(n-1) for n>0, A194723, A194724, A194725, A194726, A194727, A194728, A194729, A194730.

%Y Main diagonal gives A248828.

%Y Coefficients of row polynomials for k>0 in k, (k+1) are given by A050166, A157491.

%Y Cf. A007318, A183135.

%K nonn,tabl

%O 0,13

%A _Alois P. Heinz_, Dec 26 2010