login
A213027
Number A(n,k) of 3n-length k-ary words, either empty or beginning with the first letter of the alphabet, 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, by antidiagonals.
12
1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 4, 1, 0, 1, 1, 7, 19, 1, 0, 1, 1, 10, 61, 98, 1, 0, 1, 1, 13, 127, 591, 531, 1, 0, 1, 1, 16, 217, 1810, 6101, 2974, 1, 0, 1, 1, 19, 331, 4085, 27631, 65719, 17060, 1, 0, 1, 1, 22, 469, 7746, 82593, 441604, 729933, 99658, 1, 0
OFFSET
0,13
COMMENTS
In general, column k > 1 is asymptotic to a(n) ~ 3^(3*n+1/2) * (k-1)^(n+1) / (sqrt(Pi) * (2*k-3)^2 * 4^n * n^(3/2)). - Vaclav Kotesovec, Aug 31 2014
LINKS
FORMULA
A(n,k) = 1/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) = 1/k * A213028(n,k) if n>0, k>1; else A(n,k) = A213028(n,k).
EXAMPLE
A(0,k) = 1: the empty word.
A(n,1) = 1: (aaa)^n.
A(2,2) = 4: there are 4 words of length 6 over alphabet {a,b}, either empty or beginning with the first letter of the alphabet, that can be built by repeatedly inserting triples of identical letters into the initially empty word: aaaaaa, aaabbb, aabbba, abbbaa.
A(2,3) = 7: aaaaaa, aaabbb, aaaccc, aabbba, aaccca, abbbaa, acccaa.
A(3,2) = 19: aaaaaaaaa, aaaaaabbb, aaaaabbba, aaaabbbaa, aaabaaabb, aaabbaaab, aaabbbaaa, aaabbbbbb, aabaaabba, aabbaaaba, aabbbaaaa, aabbbabbb, aabbbbbba, abaaabbaa, abbaaabaa, abbbaaaaa, abbbaabbb, abbbabbba, abbbbbbaa.
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, ...
0, 1, 1, 1, 1, 1, 1, ...
0, 1, 4, 7, 10, 13, 16, ...
0, 1, 19, 61, 127, 217, 331, ...
0, 1, 98, 591, 1810, 4085, 7746, ...
0, 1, 531, 6101, 27631, 82593, 195011, ...
0, 1, 2974, 65719, 441604, 1751197, 5153626, ...
MAPLE
A:= (n, k)-> `if`(n=0, 1, `if`(k<2, k,
1/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
a[0, _] = 1; a[_, k_ /; k < 2] := k; a[n_, k_] := 1/n*Sum[Binomial[3*n, j]*(n-j)*(k-1)^j, {j, 0, n-1}]; Table[a[n-k, k], {n, 0, 12}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Dec 11 2013 *)
CROSSREFS
Rows n=0-3 give: A000012, A057427, A016777(k-1), A127854(k-1).
Main diagonal gives: A218472.
Sequence in context: A295281 A256461 A174699 * A347618 A290459 A290458
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Jun 03 2012
STATUS
approved