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

2, 4, 24, 720, 712800, 666860040000, 597568733024952150000000, 474258018883889933710067708314342382812500000000

Offset: 0

Author

Atabey Kaygun, Nov 11 2024

Keywords

• nonn

Comments

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.

Examples

			The initial graphs for n=0..2 are:
      o        o                 o
      |        |                 |
      o        o                 o
             /   \             /   \
            o     o           o     o
                             / \   / \
                            o   o o   o
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..11
• Atabey Kaygun Hosoya Index of Balanced Binary Trees.
• Eric Weisstein's World of Mathematics, Independent Edge Set.
• Eric Weisstein's World of Mathematics, Matching.

Crossrefs

Cf. A338293.

Programs

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

Formula

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

Extensions

a(5) onwards from Andrew Howroyd, Nov 14 2024