A213028 Number A(n,k) of 3n-length k-ary words that can be built by repeatedly inserting triples of identical letters into the initially empty word; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 8, 1, 0, 1, 4, 21, 38, 1, 0, 1, 5, 40, 183, 196, 1, 0, 1, 6, 65, 508, 1773, 1062, 1, 0, 1, 7, 96, 1085, 7240, 18303, 5948, 1, 0, 1, 8, 133, 1986, 20425, 110524, 197157, 34120, 1, 0, 1, 9, 176, 3283, 46476, 412965, 1766416, 2189799, 199316, 1, 0

Offset: 0

Author

Alois P. Heinz, Jun 03 2012

Keywords

• nonn
• tabl

Examples

			A(0,k) = 1: the empty word.
A(n,1) = 1: (aaa)^n.
A(2,2) = 8: there are 8 words of length 6 over alphabet {a,b} that can be built by repeatedly inserting triples of identical letters into the initially empty word: aaaaaa, aaabbb, aabbba, abbbaa, baaabb, bbaaab, bbbaaa, bbbbbb.
A(1,3) = 3: aaa, bbb, ccc.
A(2,3) = 21: aaaaaa, aaabbb, aaaccc, aabbba, aaccca, abbbaa, acccaa, baaabb, bbaaab, bbbaaa, bbbbbb, bbbccc, bbcccb, bcccbb, caaacc, cbbbcc, ccaaac, ccbbbc, cccaaa, cccbbb, cccccc.
Square array A(n,k) begins:
  1, 1,    1,      1,       1,       1,        1, ...
  0, 1,    2,      3,       4,       5,        6, ...
  0, 1,    8,     21,      40,      65,       96, ...
  0, 1,   38,    183,     508,    1085,     1986, ...
  0, 1,  196,   1773,    7240,   20425,    46476, ...
  0, 1, 1062,  18303,  110524,  412965,  1170066, ...
  0, 1, 5948, 197157, 1766416, 8755985, 30921756, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 1..140, flattened

Crossrefs

Rows n=0-2 give: A000012, A001477, A000567.

Columns k=0-2 give: A000007, A000012, A047098.

Cf. A183134, A183135, A213027, A256311.

Programs

Maple

A:= (n, k)-> `if`(n=0, 1,
    k/n *add(binomial(3*n, j) *(n-j) *(k-1)^j, j=0..n-1)):
seq(seq(A(n, d-n), n=0..d), d=0..12);

Mathematica

Unprotect[Power]; 0^0 = 1; A[n_, k_] := If[n==0, 1, k/n*Sum[Binomial[3*n, j]*(n-j)*(k-1)^j, {j, 0, n-1}]]; Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, Feb 22 2017, translated from Maple *)

Formula

A(n,k) = k/n * Sum_{j=0..n-1} C(3*n,j) * (n-j) * (k-1)^j if n>0, k>1; A(0,k) = 1; A(n,k) = k if n>0, k<2.

A(n,k) = k * A213027(n,k) if n>0, k>1; else A(n,k) = A213027(n,k).