login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A338293 Number of matchings in the complete binary tree of n rows. 2
1, 1, 3, 15, 495, 467775, 448046589375, 396822986774382287109375, 316789536051348354157896789538095888519287109375 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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.

LINKS

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

FORMULA

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.

EXAMPLE

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.

PROG

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

CROSSREFS

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).

Sequence in context: A309069 A122579 A138303 * A267096 A217449 A167220

Adjacent sequences:  A338290 A338291 A338292 * A338294 A338295 A338296

KEYWORD

nonn

AUTHOR

Kevin Ryde, Oct 21 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 8 22:49 EST 2021. Contains 349596 sequences. (Running on oeis4.)