cp's OEIS Frontend

A333347 Largest number of maximum matchings in a tree of n vertices.

%I A333347 #27 Aug 22 2021 13:28:11
%S A333347 1,1,1,2,3,4,5,8,11,15,21,30,41,56,81,112,153,216,303,418,571,819,
%T A333347 1133,1560,2187,3063,4235,5832,8280,11455,15807,22140,30966,42823,
%U A333347 59049,83709,115808,160083,224100,313059,432992,597861,846279,1170793,1618650,2268000,3164955
%N A333347 Largest number of maximum matchings in a tree of n vertices.
%C A333347 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.
%C A333347 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.
%C A333347 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).
%C A333347 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.
%C A333347 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.
%H A333347 Kevin Ryde, <a href="/A333347/b333347.txt">Table of n, a(n) for n = 0..1500</a>
%H A333347 Clemens Heuberger and Stephan Wagner, <a href="https://doi.org/10.1016/j.disc.2011.07.028">The Number of Maximum Matchings in a Tree</a>, Discrete Mathematics, volume 311, issue 21, November 2011, pages 2512-2542; <a href="https://arxiv.org/abs/1011.6554">arXiv preprint</a>, arXiv:1011.6554 [math.CO], 2010.
%H A333347 Clemens Heuberger and Stephan Wagner, <a href="https://www.math.tugraz.at/~cheub/publications/max-card-matching/">Number of Maximum Matchings In a Tree - Sage Code Worksheet</a>.
%H A333347 Kevin Ryde, <a href="/A333347/a333347.gp.txt">recurrence and generating function</a>, in PARI/GP.
%H A333347 Kevin Ryde, <a href="http://user42.tuxfamily.org/pari-vpar/index.html">vpar</a> examples/most-maximum-matchings.gp creating, counting, and recurrences, in PARI/GP.
%H A333347 Kevin Ryde, <a href="http://user42.tuxfamily.org/graph-maker-other/MostMaximumMatchingsTree-samples.pdf">Sample Tree Drawings</a>.
%H A333347 <a href="/index/Rec#order_574">Index entries for linear recurrences with constant coefficients</a>, order 574.
%F A333347 For n == 0 (mod 7) and k = n/7 >= 1, a(n) = 8*A190872(k) - 7*A190872(k-1).
%F A333347 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)]
%F A333347 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)]
%Y A333347 Cf. A190872, A333345, A333346 (growth power), A333348 (matching number).
%K A333347 nonn
%O A333347 0,4
%A A333347 _Kevin Ryde_, Mar 15 2020