|
|
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.
|
|
15
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,8
|
|
COMMENTS
|
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
|
|
LINKS
|
|
|
FORMULA
|
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.
|
|
EXAMPLE
|
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, ...
|
|
MAPLE
|
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);
|
|
MATHEMATICA
|
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 *)
|
|
CROSSREFS
|
Columns k=0-10 give: A000007, A000012, A000984, A089022, A035610, A130976, A130977, A130978, A130979, A130980, A131521.
Coefficients of row polynomials in k, (k-1) are given by A157491, A039599.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|