A242049 -id:A242049 - cp's OEIS frontend

A338293 Number of matchings in the complete binary tree of n rows.

1, 1, 3, 15, 495, 467775, 448046589375, 396822986774382287109375, 316789536051348354157896789538095888519287109375

Offset: 0

Kevin Ryde, Oct 21 2020

nonn

A recurrence is formed by considering the root vertex matched or unmatched and a(n-1) or a(n-2) matchings in the subtrees below.
    unmatched         matched            matched
     /    \           /   \\             //   \
  any     any      any   matched     matched  any
                         /   \        /   \
                       any   any    any   any
  so:
    a(n-1)^2     +       2 * a(n-1)*a(n-2)^2     = a(n)
The Jacobsthal product formula (below) follows from this recurrence by induction by substituting the products for a(n-1) and a(n-2) and using J(n+1) = J(n) + 2*J(n-1) (its recurrence in A001045).
The Jacobsthal product terms, with multiplicity, in a(n) are a subset of the terms in any bigger a(m), so a(n) divides any bigger a(m) and so in particular this is a divisibility sequence.
Asymptotically, a(n) ~ (1/2)*C^(2^n) where C = 1.537176.. = A338294.  For growth power C, let c(n) = (2*a(n))^(1/2^n) so that C = lim_{n->oo} c(n).  The Jacobsthal products formula gives log(c(n)) = log(2)/2^n + log(J(n+1))/2^n + Sum_{k=1..n} log(J(k))/2^k.  Then discarding log(J(1)) = log(J(2)) = 0, and log(2)/2^n -> 0, and log(J(n+1))/2^n -> 0, leaves the terms of A242049 so that log(C) = A242049.
The asymptotic factor F = 1/2 is found by letting f(n) = a(n)/a(n-1)^2, so f(n) = J(n+1) / J(n) by the products formula, and f(n) = 2 + (-1)^n/J(n) -> 2 = 1/F.  This factor makes no difference to the growth power C, since any F^(1/2^n) -> 1, but it brings the approximation closer to a(n) sooner.

			n=0 rows is the empty tree and n=1 row is a single vertex.  Both have only the empty matching so a(0) = a(1) = 1.
n=2 rows is a path-3 and has 3 matchings: first two vertices, last two, or the empty matching, so a(2) = 3.
Jacobsthal products formula:
  a(4) = J(5) * J(4) * J(3)^2 * J(2)^4 * J(1)^8
       =  11  *   5  *    3^2 *    1^4 *    1^8 = 495.

Kevin Ryde, Table of n, a(n) for n = 0..12
Kevin Ryde, vpar examples/complete-binary-matchings.gp calculations and code in PARI/GP.
Index entries for sequences of form a(n+1)=a(n)^2 + ...
Index to divisibility sequences

Cf. A001045 (Jacobsthal numbers), A338294 (growth power), A242049 (log of growth power).

Cf. A076725 (independent sets), A158681 (Wiener index), A000975 (independence number and matching number).

a(n) = my(x=1,y=1); for(i=2,n, [x,y] = [x^2 + 2*x*y^2, x]); x;

a(n) = a(n-1)^2 + 2*a(n-1)*a(n-2)^2 starting a(0)=1 and a(1)=1.
a(n) = J(n+1) * J(n) * J(n-1)^2 * J(n-2)^4 * ... * J(1)^(2^(n-1)) where J(n) = (2^n - (-1)^n)/3 = A001045(n) is the Jacobsthal numbers.
A228607(n) = a(n+1)^2*(a(n+1)+3*a(n)^2). - R. J. Mathar, Jul 22 2022

A338294 Decimal expansion of the growth power of the number of matchings in the complete binary tree.

Original entry on oeis.org

1, 5, 3, 7, 1, 7, 6, 7, 1, 7, 1, 8, 2, 3, 5, 7, 9, 4, 9, 5, 9, 0, 1, 4, 0, 3, 2, 8, 9, 5, 5, 2, 2, 1, 6, 0, 2, 5, 0, 1, 5, 0, 8, 0, 9, 3, 4, 3, 2, 3, 6, 1, 7, 3, 2, 6, 5, 1, 0, 2, 0, 0, 2, 9, 5, 0, 1, 4, 0, 0, 8, 8, 2, 7, 0, 8, 8, 8, 1, 1, 2, 4, 3, 5, 3, 2, 9

Offset: 1

Kevin Ryde, Oct 21 2020

The number of matchings in the complete binary tree of n rows is A338293(n). It grows as A338293(n) ~ (1/2)*C^(2^n) where C is the present constant. See A338293 on how log(C) = A242049 follows from the number of matchings as a product of Jacobsthal numbers.

			1.537176717...

Kevin Ryde, vpar examples/complete-binary-matchings.gp calculations and code in PARI/GP.

Cf. A242049, A338293.

Equals exp(A242049).

Equals lim_{n->oo} A338293(n)^(1/2^n).

cp's OEIS Frontend

A338293 Number of matchings in the complete binary tree of n rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula