|
%I #39 Jan 20 2024 16:07:05
%S 1,0,1,0,1,1,0,5,4,2,0,34,28,11,3,0,273,239,102,29,6,0,2436,2283,1045,
%T 325,73,11,0,23391,23475,11539,3852,968,181,23,0,237090,254309,133690,
%U 47640,12923,2756,444,46,0,2505228,2864283,1605280,607743,175976,40903,7650,1085,98
%N Triangle read by rows: T(n,k) is the number of planar tanglegrams of size n with 0 <= k < n leaf-matched pairs. A leaf matched pair is a pair of non-leaf vertices (u,v) in the tanglegram such that the induced subtrees rooted and u and v also form a tanglegram (equivalently, the leaves in these two subtrees are matched by the matching that forms the original tanglegram).
%C The generating function can be proven using a generalization of the proof for A349408.
%H Andrew Howroyd, <a href="/A349409/b349409.txt">Table of n, a(n) for n = 1..1275</a> (rows 1..50)
%H Kevin Liu, <a href="https://www.mat.univie.ac.at/~slc/wpapers/FPSAC2022/45.pdf">Planar Tanglegram Layouts and Single Edge Insertion</a>, Séminaire Lotharingien de Combinatoire (2022) Vol. 86, Issue B, Art. No. 45.
%F G.f.: F(x,q) = q*H(F(x,q)) + x + q*(F(x,q)^2 + F(x^2,q^2))/2 where coefficient of x^n*q^k is the number of planar tanglegrams with size n and k leaf-matched pairs, and H(x)/x^2 is the g.f. for A257887.
%e Triangle begins
%e 1;
%e 0, 1;
%e 0, 1, 1;
%e 0, 5, 4, 2;
%e 0, 34, 28, 11, 3;
%e 0, 273, 239, 102, 29, 6;
%e 0, 2436, 2283, 1045, 325, 73, 11;
%e 0, 23391, 23475, 11539, 3852, 968, 181, 23;
%e ...
%o (PARI) \\ here H(n)/x^2 is g.f. of A257887.
%o H(n)={(x - x^2 - serreverse(sum(k=0, n+1, (binomial(2*k, k)/(k+1))^2*x^(k+1)) + O(x^(n+3))))/2}
%o F(n)={my(h=H(n-2), p=O(x)); for(n=1, n, p = x + y*subst(h + O(x*x^n), x, p) + y*(p^2 + subst(subst(p,x,x^2),y,y^2))/2); p}
%o T(n)={[Vecrev(p) | p<-Vec(F(n))]}
%o {my(v=T(10)); for(n=1, #v, print(v[n]))} \\ _Andrew Howroyd_, Nov 18 2021
%Y Cf. A257887 (2nd column), A349408 (row sums), A001190 (diagonal).
%K nonn,tabl
%O 1,8
%A _Kevin Liu_, Nov 16 2021
|
