A377936 - OEIS

%I #20 Nov 15 2024 09:03:34

%S 2,4,24,720,712800,666860040000,597568733024952150000000,

%T 474258018883889933710067708314342382812500000000

%N Number of matchings in the complete planted binary tree with 2^n leaves.

%C A planted binary tree has an initial root node with 1 child. The root is not considered to be a leaf. All internal nodes have degree 3. The total number of nodes is 2*n.

%H Andrew Howroyd, <a href="/A377936/b377936.txt">Table of n, a(n) for n = 0..11</a>

%H Atabey Kaygun <a href="https://kaygun.github.io/clean/2024-11-12-balanced-trees.html">Hosoya Index of Balanced Binary Trees</a>.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependentEdgeSet.html">Independent Edge Set</a>.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Matching.html">Matching</a>.

%F a(n) = u(n) + v(n) where u(n) = v(n-1)^2 and v(n) = v(n-1)^2 + 2*v(n-1)*u(n-1) with u(1) = v(1) = 1. - _Andrew Howroyd_, Nov 14 2024

%e The initial graphs for n=0..2 are:

%e       o        o                 o

%e       |        |                 |

%e       o        o                 o

%e              /   \             /   \

%e             o     o           o     o

%e                              / \   / \

%e                             o   o o   o

%o (PARI) lista(n)={my(u=vector(n), v=vector(n)); u[1]=v[1]=1; for(n=1, #u-1, u[n+1]=v[n]^2; v[n+1]=u[n+1] + 2*v[n]*u[n]); v+u} \\ _Andrew Howroyd_, Nov 14 2024

%Y Cf. A338293.

%K nonn

%O 0,1

%A _Atabey Kaygun_, Nov 11 2024

%E a(5) onwards from _Andrew Howroyd_, Nov 14 2024