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.
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
KEYWORD
nonn
AUTHOR
Julien Courtiel, May 22 2017
STATUS
approved