cp's OEIS Frontend

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.

Row sums give A007472.

The recurrence is analogous to that of Stirling numbers of the 2nd kind (A048993), but with a parity constraint. For even columns, T(n+1, 2*k) = 2*k*T(n, 2*k) + T(n, 2*k-1); for odd columns, T(n+1, 2*k+1) = 2*k*T(n, 2*k+1) + T(n, 2*k).

T(n,k) appear as coefficients in the following polynomials (which themselves are coefficients of t^n in the bivariate e.g.f.:

P_0(x) = 1

P_1(x) = 0 + x

P_2(x) = 0 + 0 + x^2

P_3(x) = 0 + 0 + 2x^2 + x^3

P_4(x) = 0 + 0 + 4x^2 + 4x^3 + x^4

P_5(x) = 0 + 0 + 8x^2 + 12x^3 + 8x^4 + x^5

P_6(x) = 0 + 0 + 16x^2 + 32x^3 + 44x^4 + 12x^5 + x^6

P_n(1) gives A007472.

T(n,k) enumerates the number of ways to partition n labeled objects in k compartments of urns with two compartments each with the following constraints:

- you can initially place a marble in any compartment of any urn

- you cannot use the same compartment in an urn again until you've used its other compartment

- you can freely place objects in any compartment of urns where both compartments are already used

- you cannot open a new urn until both compartments of all previously used urns are filled

Examples:

For T(3,2) we have two ways to place the objects in two compartments of a single urn

- {13|2}

- {1|23}

For T(3,3) we have one way to place each object in its own compartment (2 urns, 3 compartments used):

- {1|2}{3|}

For 4 objects we have:

- 4 cases for Z(4,2):

{134|2}

{14|23}

{13|24}

{1|234}

- 4 cases for Z(4,3):

{{13|2},{4|}}

{{1|23},{4|}}

{{14|2},{3|}}

{{1|24},{3|}}

- 1 case for Z(4,4):

{{1|2}, {3|4}}

Then A007472 counts the total number of ways to partition n labeled objects in such nonempty two-compartment urns.