cp's OEIS Frontend

a(k) is Heuberger and Wagner's G_k at lemma 6.2 (2). They show (theorem 3.3 (1)) that the largest number of maximum matchings in a tree of 7k+1 vertices is a(k+1) and there is a unique free tree with this many maximum matchings. (See A333347 for all tree sizes.) - Kevin Ryde, Apr 11 2020

Continued fraction expansion of (9+sqrt(85))/2 is A010734.

Heuberger and Wagner consider how many different maximum matchings a tree of n vertices may have. They determine the unique tree (free tree) of n vertices with the largest number of maximum matchings, or at n=6 and n=34 the two trees with equal largest number. a(n) is the largest number of maximum matchings. They show that a(n) grows as O(1.391...^n), where the power is ((11 + sqrt(85))/2)^(1/7) = A333346.

They note an algebraic interpretation too, that a(n) is the largest possible absolute value of the product of the nonzero eigenvalues of the adjacency matrix of a tree of n vertices. This is simply that, in the usual way, a term +- m*x^j in the characteristic polynomial of that matrix means there are m matchings which have j vertices unmatched. The smallest j with a nonzero m is the maximum matchings, and that m is also the product of the nonzero roots.

In Heuberger and Wagner's Sage code, optimal_m(n) is a(n) for the general case tree forms. Their general case symbolic calculations are in terms of lambda = (11 + sqrt(85))/2 = A333345 and its quadratic conjugate lambdabar = (11 - sqrt(85))/2 (called alpha and alphabar in the code). The resulting coefficients give constants c_0 through c_6 in their paper for a(n) -> c_{n mod 7} * lambda^(n/7) (theorem 1.2).

The combinations of powers of lambda and lambdabar occurring are linear recurrences. Recurrence coefficients can be found from a symbolic calculation, or from explicit values and an upper bound on recurrence orders from the patterns of branch lengths and powers. Each case n mod 7 is a recurrence of order up to 44. The simplest is G_k = A190872(k) for n == 1 (mod 7) in the formulas below. Other cases are G variants, and possible additional terms growing slower than G.

The full recurrence for all n is order 574 applying at n=31 onwards (after the last initial exception at n=30). See the links for recurrence coefficients and generating function.

First differences of A190872.

Heuberger and Wagner consider the number of maximum matchings a tree of n vertices may have. They show that the largest number of maximum matchings (A333347) grows as O(1.3916...^n) where the power is the constant here. This arises in their tree forms since each 7-vertex "C" part increases the number of matchings by a factor of matrix M=[8,3/5,3] (lemma 6.2). The larger eigenvalue of M is their lambda = A333345 and so a factor of lambda for each 7 vertices.