login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

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

Table of n, a(n) for n=1..110.

E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288.

Eric Weisstein's World of Mathematics, Matching-Generating Polynomial

Index entries for sequences related to Matula-Goebel numbers

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))[2], M(pi(n))[1]+M(pi(n))[2]] else [M(r(n))[1]*M(s(n))[2]+M(r(n))[2]*M(s(n))[1], M(r(n))[2]*M(s(n))[2]] end if end proc: m := proc (n) options operator, arrow: sort(expand(M(n)[1]+M(n)[2])) 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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 20:57 EST 2019. Contains 319282 sequences. (Running on oeis4.)