A recurrence is formed by considering the root vertex matched or unmatched and a(n1) or a(n2) matchings in the subtrees below.
unmatched matched matched
/ \ / \\ // \
any any any matched matched any
/ \ / \
any any any any
so:
a(n1)^2 + 2 * a(n1)*a(n2)^2 = a(n)
The Jacobsthal product formula (below) follows from this recurrence by induction by substituting the products for a(n1) and a(n2) and using J(n+1) = J(n) + 2*J(n1) (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(n1)^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.
