|
|
A287223
|
|
Numbers of tree alignments.
|
|
0
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|