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,3

Comments

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

Links

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

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

Adjacent sequences: A294488 A294489 A294490 * A294492 A294493 A294494

Keyword

nonn

Author

Alois P. Heinz, Oct 31 2017

Status

approved