A183134 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.

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, 181, 126, 1, 0, 1, 1, 11, 97, 523, 1181, 462, 1, 0, 1, 1, 13, 146, 1145, 4966, 7941, 1716, 1, 0, 1, 1, 15, 205, 2131, 14289, 48838, 54573, 6435, 1, 0

Offset: 0

Author

Alois P. Heinz, Dec 26 2010

Keywords

• nonn
• tabl

Comments

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

Examples

			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.
Square array A(n,k) begins:
  1,  1,   1,    1,    1,     1,  ...
  0,  1,   1,    1,    1,     1,  ...
  0,  1,   3,    5,    7,     9,  ...
  0,  1,  10,   29,   58,    97,  ...
  0,  1,  35,  181,  523,  1145,  ...
  0,  1, 126, 1181, 4966, 14289,  ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..140, flattened
• C. Kassel and C. Reutenauer, Algebraicity of the zeta function associated to a matrix over a free group algebra, arXiv preprint arXiv:1303.3481, 2013
• A. Lakshminarayan, Z. Puchala, K. Zyczkowski, Diagonal unitary entangling gates and contradiagonal quantum states, arXiv preprint arXiv:1407.1169, 2014

Crossrefs

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

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

Main diagonal gives A248828.

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

Cf. A007318, A183135.

Programs

Maple

A:= proc(n, k)
      local j;
      if n=0  then 1
    elif k<=1 then k
              else add(binomial(2*n,j)*(n-j)*(k-1)^j, j=0..n-1)/n
      fi
    end:
seq(seq(A(n, d-n), n=0..d), d=0..10);

Mathematica

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

Formula

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.

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

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.