

A193405


The Matula numbers of the rooted trees that have a perfect matching.


3



2, 5, 6, 15, 18, 22, 23, 26, 31, 41, 45, 54, 55, 65, 66, 69, 78, 93, 94, 103, 122, 123, 135, 137, 158, 162, 165, 166, 167, 195, 198, 202, 207, 211, 234, 235, 242, 253, 254, 279, 282, 283, 286, 299, 305, 309, 338, 341, 358, 366, 369, 394, 395, 401, 403, 405, 411, 415, 419, 431, 451, 474, 486, 495, 498
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

The MatulaGoebel number of a rooted tree can be defined in the following recursive manner: to the onevertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the tth prime number, where t is the MatulaGoebel 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 MatulaGoebel numbers of the m branches of T.
It is known that a tree has at most one perfect matching.
Complement of A193406.


REFERENCES

F. Goebel, On a 11correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131142.
I. Gutman and YeongNan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 1722.
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, 33143319.
C. D. Godsil, Algebraic Combinatorics, Chapman & Hall, New York, 1993.


LINKS

Table of n, a(n) for n=1..65.
E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288.
Index entries for sequences related to MatulaGoebel numbers


FORMULA

Define b(n) (c(n)) to be the generating polynomials of the matchings of the rooted tree with MatulaGoebel number n that contain (do not contain) the root, with respect to the size of the matching. We have the following recurrence for the pair M(n)=[b(n),c(n)]. M(1)=[0,1]; if n=p(t) (=the tth 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 (a modified matching polynomial). The tree has a perfect matching if and only if the degree of this polynomial is 1/2 of the number of vertices of the tree.


EXAMPLE

2,6,31 are in the sequence because they are the Matula numbers of the paths on 2,4,6 vertices, respectively.


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: PM := {}: for n to 500 do if N(n) = 2*degree(m(n)) then PM := `union`(PM, {n}) else end if end do: PM;


CROSSREFS

Cf. A061775, A193406.
Sequence in context: A287203 A291211 A193402 * A037079 A101325 A042980
Adjacent sequences: A193402 A193403 A193404 * A193406 A193407 A193408


KEYWORD

nonn


AUTHOR

Emeric Deutsch, Feb 12 2012


STATUS

approved



