A157491 -id:A157491 - cp's OEIS frontend

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

Alois P. Heinz, Dec 26 2010

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

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

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

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.

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

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

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.

A183135 Square array A(n,k) by antidiagonals. A(n,k) is the number of length 2n k-ary words (n,k>=0) that can be built by repeatedly inserting doublets into the initially empty word.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 6, 1, 0, 1, 4, 15, 20, 1, 0, 1, 5, 28, 87, 70, 1, 0, 1, 6, 45, 232, 543, 252, 1, 0, 1, 7, 66, 485, 2092, 3543, 924, 1, 0, 1, 8, 91, 876, 5725, 19864, 23823, 3432, 1, 0, 1, 9, 120, 1435, 12786, 71445, 195352, 163719, 12870, 1, 0

Offset: 0

Alois P. Heinz, Dec 26 2010

A(n,k) is also the number of rooted closed walks of length 2n on the infinite rooted k-ary tree. - Danny Rorabaugh, Oct 31 2017

A(n,2k) is the number of unreduced words of length 2n that reduce to the empty word in the free group with k generators. - Danny Rorabaugh, Nov 09 2017

			A(2,2) = 6, because 6 words of length 4 can be built over 2-letter alphabet {a, b} by repeatedly inserting doublets (words with two equal letters) into the initially empty word: aaaa, aabb, abba, baab, bbaa, bbbb.
Square array A(n,k) begins:
  1,  1,   1,    1,     1,     1,  ...
  0,  1,   2,    3,     4,     5,  ...
  0,  1,   6,   15,    28,    45,  ...
  0,  1,  20,   87,   232,   485,  ...
  0,  1,  70,  543,  2092,  5725,  ...
  0,  1, 252, 3543, 19864, 71445,  ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
Jason Bell, Marni Mishna, On the Complexity of the Cogrowth Sequence, arXiv:1805.08118 [math.CO], 2018.
Beth Bjorkman et al., k-foldability of words, arXiv preprint arXiv:1710.10616 [math.CO], 2017.

Columns k=0-10 give: A000007, A000012, A000984, A089022, A035610, A130976, A130977, A130978, A130979, A130980, A131521.
Rows n=0-3 give: A000012, A001477, A000384, A027849(k-1) for k>0.
Main diagonal gives A294491.
Coefficients of row polynomials in k, (k-1) are given by A157491, A039599.
Cf. A007318, A183134, A256116, A256117.

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

A[, 1] = 1; A[n, k_] := If[n == 0, 1, k/n*Sum[Binomial[2*n, j]*(n - j)*(k - 1)^j, {j, 0, n - 1}]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 27 2013, translated from Maple *)

A(n,k) = k/n * Sum_{j=0..n-1} C(2*n,j)*(n-j)*(k-1)^j if n>0, A(0,k) = 1.
A(n,k) = A183134(n,k) if n=0 or k<2, A(n,k) = A183134(n,k)*k otherwise.
G.f. of column k: 1/(1-k*x) if k<2, 2*(k-1)/(k-2+k*sqrt(1-(4*k-4)*x)) otherwise.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula