

A193406


The Matula numbers of the rooted trees that have no perfect matchings.


2



1, 3, 4, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 19, 20, 21, 24, 25, 27, 28, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39, 40, 42, 43, 44, 46, 47, 48, 49, 50, 51, 52, 53, 56, 57, 58, 59, 60, 61, 62, 63, 64, 67, 68, 70, 71, 72, 73, 74, 75, 76, 77, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 95, 96, 97, 98, 99, 100
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


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 A193405.


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..81.
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

3 and 11 are in the sequence because they are the Matula numbers of paths on 3 and 5 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: NPM := {}: for n to 100 do if N(n) <> 2*degree(m(n)) then NPM := `union`(NPM, {n}) else end if end do: NPM;


CROSSREFS

Cf. A061775, A193405.
Sequence in context: A316973 A213622 A246847 * A104426 A097044 A198330
Adjacent sequences: A193403 A193404 A193405 * A193407 A193408 A193409


KEYWORD

nonn


AUTHOR

Emeric Deutsch, Feb 12 2012


STATUS

approved



