A287223 Numbers of tree alignments.

0, 0, 2, 6, 22, 88, 370, 1612, 7232, 33304, 157102, 757804, 3731352, 18720504, 95519428, 494733144, 2596388976, 13783481424, 73906300822, 399722732236, 2178164438936, 11946745980632, 65898275096796, 365308080119688, 2033992114316240, 11369167905107888, 63769939599193228, 358804271821028088, 2024523256299630832

Offset

0,3

Comments

The notion of tree alignment is due to Jiang, Whang and Zhang (Alignment of trees—an alternative to tree edit).

References

C. Chauve, J. Courtiel and Y. Ponty, Counting, Generating and Sampling Tree Alignments, in Algorithms for Computational Biology, 2016, Lecture Notes in Computer Science, vol 9702.

Links

Table of n, a(n) for n=0..28.

Formula

G.f.: (1+sqrt(1-4*t)) * (2+8*t^2-(2-8*t) * sqrt(1-4*t)-12*t+2*sqrt(2)*R ) / (-4*t*(4*sqrt(1-4*t))) where R = sqrt((1-8*t+12*t^2)*(2*t^2+(2*t-1)*sqrt(1-4*t)+1-4*t)) (no combinatorial interpretation known).

Example

For n = 3, the number 6=2x3 corresponds to the number of alignments between a one-vertex tree and a two-vertices tree, or between a two-vertices tree and a one-vertex tree.

Crossrefs

Sequence in context: A049127 A199481 A049137 * A365246 A333080 A096267

Adjacent sequences: A287220 A287221 A287222 * A287224 A287225 A287226

Keyword

nonn

Author

Julien Courtiel, May 22 2017

Status

approved