A294491 Number of length 2n n-ary words that can be built by repeatedly inserting doublets into the initially empty word.

1, 1, 6, 87, 2092, 71445, 3183156, 175466347, 11544312984, 883404542025, 77115832253380, 7564442149980111, 823833773843404776, 98644885379708947357, 12880909497761085034632, 1821689155897508835803475, 277402856595034529463789616, 45253909471856604392088994065

Offset: 0

Author

Alois P. Heinz, Oct 31 2017

Keywords

• nonn

Comments

Also the number of rooted closed walks of length 2n on the infinite rooted n-ary tree.

Examples

			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.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..322

Crossrefs

Main diagonal of A183135.

Cf. A248828.

Programs

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

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.