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

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

Offset

0,1

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.

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.

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

Example

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

Prog

(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

Crossrefs

Cf. A338293.

Sequence in context: A332539 A296787 A341633 * A128299 A143672 A001510

Adjacent sequences: A377933 A377934 A377935 * A377937 A377938 A377939

Keyword

nonn

Author

Atabey Kaygun, Nov 11 2024

Extensions

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

Status

approved