A136628 Number of unlabeled PQ-trees with n leaves.

0, 1, 1, 3, 9, 29, 105, 390, 1528, 6119, 25140, 104936, 444637, 1905331, 8246619, 35988793, 158199975, 699788234, 3112679085, 13913394416, 62465305846, 281551756181, 1273583739390, 5779693081500, 26306751243309

Offset

0,4

Comments

A PQ-tree is a rooted tree with P-type internal nodes that have at least 3 children that are reversibly ordered (the reverse of the order is equivalent to the order) and Q-type internal nodes that have at least 2 unordered children.

References

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 242 (3.3.91).

Links

Christian G. Bower, Table of n, a(n) for n = 0..511

Transforms in PARI

Index entries for sequences related to rooted trees

Formula

G.f. satisfies: A(x) = x + (2-A(x)^2)/(2-2A(x)^2) + (1+A(x))*A(x^2)/(2-2A(x^2)) + exp(Sum_{i>=1} A(x^i)/i) - (A(x)^2+A(x^2))/2 - 2A(x) - 2.

Prog

(PARI) read("transforms_pari.txt"); {pqu(A) = A = trv_chain(A)+trv_euler(A)-trv_euler_2(A)-2*A; A[1]=0; A} {apqu(n) = local(SX, SY); SY = SX = [0, 1]; for(i=1, n, SY=concat(SY, 0); SX=concat(SX, 0); SY=SX+pqu(SY)); SY} A136628(n) = apqu(min(1, n-1))[n+1]

Crossrefs

Sequence in context: A091152 A148945 A177255 * A151031 A151032 A007472

Adjacent sequences: A136625 A136626 A136627 * A136629 A136630 A136631

Keyword

nonn

Author

Christian G. Bower, Jan 14 2008

Status

approved