The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A206483 The matching number of the rooted tree having Matula-Goebel number n. 1
 0, 1, 1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 3, 1, 2, 3, 1, 2, 2, 3, 3, 2, 3, 3, 3, 2, 2, 3, 3, 1, 3, 2, 3, 3, 2, 2, 3, 2, 3, 3, 2, 3, 4, 3, 3, 2, 2, 3, 3, 3, 1, 4, 4, 2, 2, 3, 2, 3, 3, 3, 3, 1, 4, 4, 2, 2, 4, 3, 2, 3, 3, 3, 4, 2, 3, 4, 3, 2, 4, 3, 3, 3, 3, 3, 3, 3, 2, 4, 3, 3, 4, 4, 3, 2, 3, 3, 4, 3, 3, 3, 4, 3, 4, 2, 2, 4, 3, 4 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,5 COMMENTS A matching in a graph is a set of edges, no two of which have a vertex in common. The matching number of a graph is the maximum of the cardinalities of all the matchings in the graph. Consequently, the matching number of a graph is the degree of the matching-generating polynomial of the graph (see the MathWorld link). The Matula-Goebel number of a rooted tree can be defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m>=2 there corresponds the product of the Matula-Goebel numbers of the m branches of T. After activating the Maple program, which yields the sequence, the command m(n) will yield the matching-generating  polynomial of the rooted tree corresponding to the Matula-Goebel number n. REFERENCES F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143. I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142. I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22. D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Review, 10, 1968, 273. É. Czabarka, L. Székely, and S. Wagner, The inverse problem for certain tree parameters, Discrete Appl. Math., 157, 2009, 3314-3319. C. D. Godsil, Algebraic Combinatorics, Chapman & Hall, New York, 1993. LINKS E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288. Eric Weisstein's World of Mathematics, Matching-Generating Polynomial FORMULA Define b(n) (c(n)) to be the generating polynomials of the matchings of the rooted tree with Matula-Goebel number n that contain (do not contain) the root, with respect to the size of the matching (a k-matching has size k). We have the following recurrence for the pair M(n)=[b(n),c(n)]. M(1)=[0,1]; if n=p(t) (=the t-th prime), then M(n)=[xc(t),b(t)+c(t)]; if n=rs (r,s,>=2), then M(n)=[b(r)c(s)+c(r)b(s), c(r)c(s)]. Then m(n)=b(n)+c(n) is the generating polynomial of the matchings of the rooted tree with respect to the size of the matchings (called the matching-generating polynomial). The matching number is the degree of this polynomial. EXAMPLE a(11)=2 because the rooted tree corresponding to n=11 is a path abcde on 5 vertices. We have matchings with 2 edges (for example, (ab, cd)) but not with 3 edges. MAPLE with(numtheory): N := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 1 elif bigomega(n) = 1 then 1+N(pi(n)) else N(r(n))+N(s(n))-1 end if end proc: M := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then [0, 1] elif bigomega(n) = 1 then [x*M(pi(n)), M(pi(n))+M(pi(n))] else [M(r(n))*M(s(n))+M(r(n))*M(s(n)), M(r(n))*M(s(n))] end if end proc: m := proc (n) options operator, arrow: sort(expand(M(n)+M(n))) end proc: seq(degree(m(n)), n = 1 .. 110); CROSSREFS Cf. A202853. Sequence in context: A212632 A025885 A198337 * A087011 A294602 A000174 Adjacent sequences:  A206480 A206481 A206482 * A206484 A206485 A206486 KEYWORD nonn AUTHOR Emeric Deutsch, Feb 14 2012 STATUS approved

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.

Last modified May 28 21:37 EDT 2020. Contains 334690 sequences. (Running on oeis4.)