login
A294491
Number of length 2n n-ary words that can be built by repeatedly inserting doublets into the initially empty word.
3
1, 1, 6, 87, 2092, 71445, 3183156, 175466347, 11544312984, 883404542025, 77115832253380, 7564442149980111, 823833773843404776, 98644885379708947357, 12880909497761085034632, 1821689155897508835803475, 277402856595034529463789616, 45253909471856604392088994065
OFFSET
0,3
COMMENTS
Also the number of rooted closed walks of length 2n on the infinite rooted n-ary tree.
LINKS
FORMULA
a(n) = Sum_{j=0..n-1} binomial(2*n,j)*(n-j)*(n-1)^j for n>0, a(0) = 1.
a(n) = [x^n] 2*(n-1)/(n-2+n*sqrt(1-(4*n-4)*x)) for n>1, a(n) = 1 for n<2.
a(n) = A183135(n,n).
a(n) = n * A248828(n) for n>0, a(0) = 1.
EXAMPLE
a(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.
MAPLE
a:= n-> `if`(n=0, 1, add(binomial(2*n, j)*(n-j)*(n-1)^j, j=0..n-1)):
seq(a(n), n=0..21);
CROSSREFS
Main diagonal of A183135.
Cf. A248828.
Sequence in context: A239749 A277337 A138216 * A239750 A245984 A245982
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Oct 31 2017
STATUS
approved