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



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A333347 Largest number of maximum matchings in a tree of n vertices. 6
1, 1, 1, 2, 3, 4, 5, 8, 11, 15, 21, 30, 41, 56, 81, 112, 153, 216, 303, 418, 571, 819, 1133, 1560, 2187, 3063, 4235, 5832, 8280, 11455, 15807, 22140, 30966, 42823, 59049, 83709, 115808, 160083, 224100, 313059, 432992, 597861, 846279, 1170793, 1618650, 2268000, 3164955 (list; graph; refs; listen; history; text; internal format)



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.


Kevin Ryde, Table of n, a(n) for n = 0..1500

Clemens Heuberger and Stephan Wagner, The Number of Maximum Matchings in a Tree, Discrete Mathematics, volume 311, issue 21, November 2011, pages 2512-2542; arXiv preprint, arXiv:1011.6554 [math.CO], 2010.

Clemens Heuberger and Stephan Wagner, Number of Maximum Matchings In a Tree - Sage Code Worksheet.

Kevin Ryde, recurrence and generating function, in Pari/GP.

Kevin Ryde, vpar examples/most-maximum-matchings.gp creating, counting, and recurrences, in Pari/GP.

Kevin Ryde, Sample Tree Drawings.

Index entries for linear recurrences with constant coefficients, order 574.


For n == 0 (mod 7) and k = n/7 >= 1, a(n) = 8*A190872(k) - 7*A190872(k-1).

For n == 1 (mod 7) and k = (n-1)/7, a(n) = A190872(k+1).  [Heuberger and Wagner theorem 3.3 (1) and lemma 6.2 (2)]

For n == 4 (mod 7) and k = (n-4)/7, a(n) = 3*A333344(k).  [Heuberger and Wagner theorem 3.3 (4) and lemma 6.2 (2)]


Cf. A190872, A333345, A333346 (growth power), A333348 (matching number).

Sequence in context: A261629 A244395 A271488 * A302592 A078762 A103262

Adjacent sequences:  A333344 A333345 A333346 * A333348 A333349 A333350




Kevin Ryde, Mar 15 2020



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 August 8 05:25 EDT 2020. Contains 336290 sequences. (Running on oeis4.)