A136628 - OEIS

%I #10 Feb 19 2018 03:36:41

%S 0,1,1,3,9,29,105,390,1528,6119,25140,104936,444637,1905331,8246619,

%T 35988793,158199975,699788234,3112679085,13913394416,62465305846,

%U 281551756181,1273583739390,5779693081500,26306751243309

%N Number of unlabeled PQ-trees with n leaves.

%C 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.

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

%H Christian G. Bower, <a href="/A136628/b136628.txt">Table of n, a(n) for n = 0..511</a>

%H <a href="/transforms_pari.txt">Transforms in PARI</a>

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%F 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.

%o (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]

%K nonn

%O 0,4

%A _Christian G. Bower_, Jan 14 2008