A338294 -id:A338294 - 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

A242049 Decimal expansion of 'lambda', the Lyapunov exponent characterizing the asymptotic growth rate of the number of odd coefficients in Pascal trinomial triangle mod 2, where coefficients are from (1+x+x^2)^n.

Original entry on oeis.org

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

Offset: 0

Jean-François Alcover, Aug 13 2014

			0.429947433342452720114697035519922323324065011589304617040276...
= log(1.53717671718235794959014032895522160250150809343236...)

Steven Finch, Pascal Sebah and Zai-Qiao Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008, p. 14.
Sara Kropf and Stephan Wagner, q-Quasiadditive functions, arXiv:1605.03654 [math.CO], 2016. See section 5 example 8 mean mu for the case s_n is the Jacobsthal sequence.
Kevin Ryde, vpar examples/complete-binary-matchings.gp calculations and code in PARI/GP, see log(C).

Cf. A338294.

Cf. A242208 (1+x+x^2)^n, A242021 (1+x+x^3)^n, A242022 (1+x+x^2+x^3+x^4)^n, A241002 (1+x+x^4)^n, A242047 (1+x+...+x^4+x^5)^n, A242048 (1+x+...+x^5+x^6)^n.

digits = 105; lambda = (1/4)*NSum[Log[(1/3)*(2^(k+2) - (-1)^k)]/2^k, {k, 1, Infinity}, WorkingPrecision -> digits + 5, NSumTerms -> 500]; RealDigits[lambda, 10, digits] // First

(1/4)*suminf(k=1, (log((1/3)*(2^(k+2) - (-1)^k))/2^k)) \\ Michel Marcus, May 14 2020

Equals (1/4)*Sum_{k >= 1} (log((1/3)*(2^(k+2) - (-1)^k))/2^k).
From Kevin Ryde, Feb 13 2021: (Start)
Equals log(A338294).
Equals Sum_{k>=1} (1/k)*( 1/(1+(-2)^(k+1)) - 1/(-3)^k ) (an alternating series).
(End)

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