Nội dung

Counting Rooted Trees : The Universal Law t(n) ∼ Cρ−nn−3/2 Jason P. Bell∗ Department of Mathematics, Simon Fraser University, 8888 University Dr., Burnaby, BC,V5A 1S6 Canada jpb@math.sfu.ca Stanley N. Burris Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario, N2L 3G1 Canada snburris@thoralf.uwaterloo.ca www.thoralf.uwaterloo.ca Karen A. Yeats Department of Mathematics and Statistics, Boston University 111 Cummington Street, Boston, MA 02215 USA kayeats@math.bu.edu Submitted: Jul 19, 2004; Accepted: Jul 28, 2006; Published: Aug 3, 2006 Mathematics Subject Classifications: Primary 05C05; Secondary 05A16, 05C30, 30D05 Abstract Combinatorial classes T that are recursively defined using combinations of the standard multiset, sequence, directed cycle and cycle constructions, and their restrictions, have generating series T(z) with a positive radius of convergence; for most of these a simple test can be used to quickly show that the form of the asymptotics is the same as that for the class of rooted trees: Cρ −n n−3/2 , where ρ is the radius of convergence of T. ∗ We are greatly indebted to the referee for bringing up important questions, especially regarding the role of Set, that led us to thoroughly rework the paper. The second and third authors would like to thank NSERC for support of this research. the electronic journal of combinatorics 13 (2006), #R63 1 1 Introduction The class of rooted trees, perhaps with additional structure as in the planar case, is unique among the well studied classes of structures. It is so easy to find endless possibilities for defining interesting subclasses as the fixpoint of a class construction, where the constructions used are combinations of a few standard constructions like sequence, multiset and add-a-root. This fortunate situation is based on a simple reconstruction property: removing the root from a tree gives a collection of trees (called a forest); and it is trivial to reconstruct the original tree from the forest (by adding a root). Since we will be frequently referring to rooted trees, and rarely to free (i.e., unrooted) trees, from now on we will assume, unless the context says otherwise, that the word ‘tree’ means ‘rooted tree’. 1.1 Cayley’s fundamental equation for trees Cayley [5] initiated the tree investigations1 in 1857 when he presented the well known infinite product representation2 Y
−t(j) T(z) = z 1 − zj . j≥1 Cayley used this to calculate t(n) for 1 ≤ n ≤ 13 . More than a decade later ([7], [8], [10]) he used this method to give recursion procedures for finding the coefficients of generating functions for the chemical diagrams of certain families of compounds. 1.2 Pólya’s analysis of the generating series for trees Following on Cayley’s work and further contributions by chemists, Pólya published his classic 1937 paper3 that presents: (1) his group-theoretic approach to enumeration, and (2) the primary analytic technique to establish the asymptotics of recursively defined classes of trees. Let us review the latter as it has provided the paradigm for all subsequent investigations into generating series defined by recursion equations. Let T(z) be the generating series for the class of all unlabelled trees. Pólya first converts Cayley’s equation to the form X  T(z) = z · exp T(z m )/m . m≥1 1 This was in the context of an algorithm for expanding partial differential operators. Trees play an important role in the modern theory of differential equations and integration—see for example Butcher [3]. 2 This representation uses t(n) to count the number of trees on n vertices. Cayley actually used t(n) to count the number of trees with n edges, so his formula was Y
−t(j−1) T(z) = z 1 − zj . j≥1 3 Republished in book form in [26]. the electronic journal of combinatorics 13 (2006), #R63 2 From this he quickly deduces that: the radius of convergence ρ of T(z) is in (0, 1) and T(ρ) < ∞. He defines the bivariate function X  E(z, w) := zew · exp T(z m )/m , m≥2
giving the recursion equation T = E z, T . Since E(z, w) is holomorphic in a neighborhood of T he can invoke the Implicit Function Theorem to show that a necessary condition for z to be a dominant singularity, that is a singularity on the circle of convergence, of T is
Ew z, T(z) = 1. From this Pólya
deduces that T
has a unique dominant singularity, namely z = ρ. Next, since Ez ρ, T(ρ) , Eww ρ, T(ρ) 6= 0, the Weierstraß Preparation Theorem shows that ρ is a square-root type singularity. Applying well known results derived from the Cauchy Integral Theorem Z T(z) 1 dz (1) t(n) = 2πi C z n+1 one has the famous asymptotics t(n) ∼ Cρ−n n−3/2 (?) which occur so frequently in the study of recursively defined classes. 1.3 Subsequent developments Bender ([1], 1974) proposed a general version of the Pólya result, but Canfield ([4], 1983) found a flaw in the proof, and proposed a more restricted version. Harary, Robinson and Schwenk ([17], 1975) gave a 20 step guideline on how to carry out a Pólya style analysis of a recursion equation. Meir and Moon ([21], 1989) made some further proposals on how to modify Bender’s approach; in particular it was found that the hypothesis that the coefficients of E be nonnegative was highly desirable, and covered a great number of important cases. This nonnegativity condition has continued to find favor, being used in Odlyzko’s survey paper [23] and in the forthcoming book [15] of Flajolet and Sedgewick. Odlyzko’s version seems to be a current standard—here it is (with minor corrections due to Flajolet and Sedgewick [15]). Theorem 1 (Odlyzko [23], Theorem 10.6). Suppose X E(z, w) = eij z i w j with e00 = 0, e01 < 1, (∀i, j) eij ≥ 0 (2) i,j≥0 T(z) = X i≥1 ti z i with (∀i) ti ≥ 0 (3) are such that the electronic journal of combinatorics 13 (2006), #R63 3 (a) T(z) is analytic at x = 0
(b) T(z) = E z, T(z) (c) E(z, w) is nonlinear in w (d) there are positive integers i, j, k with i < j < k such that ti , tj , tk > 0 gcd(j − i, k − i) = 1. Suppose furthermore that there exist δ, r, s > 0 such that (e) E(z, w) is analytic in |z| < r + δ and |w| < s + δ (f) E(r, s) = s (g) Ew (r, s) = 1 (h) Ez (r, s) 6= 0 and Eww (r, s) 6= 0. Then r is the radius of convergence of T, T(r) = s, and as n → ∞ s rEz (r, s) · r n n−3/2 . tn ∼ 2πEww (r, s) Remark 2. As with Pólya’s original result, the asymptotics in these more general theorems follow from information gathered on the location and nature of the dominant singularities of T. It has become popular to require that the solution T have a unique dominant singularity—to guarantee this happens the above theorem has the hypothesis (d). One can achieve this with a weaker hypothesis, namely one only needs to require
(d0 ) gcd {j − i : i < j and ti , tj > 0} = 1. Actually, given the other hypotheses of Theorem 1, the condition (d0 ) is necessary and sufficient that T have a unique dominant singularity. The generalization of Pólya’s result that we find most convenient is given in Theorem 28. We will also adopt the condition that E have nonnegative coefficients, but point out that under this hypothesis the location of the dominant singularities is quite easy to determine. Consequently the unique singularity condition is not needed to determine the asymptotics. For further remarks on previous variations and generalizations of the work of Pólya see § 7. The condition that the E have nonnegative coefficients forces us to omit the Set operator from our list of standard combinatorial operators. There are a number of complications in trying to extend the results of this paper to recursion equations w = G(z, w) where G has mixed signs appearing with its coefficients, including the problem of locating the dominant singularities of the solution. The situation with mixed signs is discussed in § 6. the electronic journal of combinatorics 13 (2006), #R63 4 1.4 Goal of this paper Aside from the proof details that show we do not need to require that the solution T have a unique dominant singularity, this paper is not about finding a better way of generalizing Pólya’s theorem on trees. Rather the paper is concerned with the ubiquity of the form (?) of asymptotics that Pólya found for the recursively defined class of trees.4 The goal of this paper is to exhibit a very large class of natural and easily recognizable operators Θ for which we can guarantee that a solution w = T(z) to the recursion equation w = Θ(w) has coefficients that satisfy (?) (?). By ‘easily recognizable’ we mean that you only have to look at the expression describing Θ—no further analysis is needed. This contrasts with the existing literature where one is expected to carry out some calculations to determine if the solution T will have certain properties. For example, in Odlyzko’s version, Theorem 1, there is a great deal of work to be done, starting with checking that the solution T is analytic at z = 0. In the formal specification theory for combinatorial classes (see Flajolet and Sedgewick [15]) one starts with the binary operations of disjoint union and disjoint sum and adds unary constructions that transform a collection of objects (like trees) into a collection of objects (like forests). Such constructions are admissible if the generating series of the output class of the construction is completely determined by the generating series of the input class. We want to show that a recursive specification using almost any combination of these constructions, and others that we will introduce, yield classes whose generating series have coefficients that obey the asymptotics (?) of Pólya. It is indeed a universal law. The goal of this paper is to provide truly practical criteria (Theorem 75) to verify that many, if not most, of the common nonlinear recursion equations lead to (?) (?). Here is a contrived example to which this theorem applies:  X
n
 X n (4) (2 + 1) DCyclePrimes (w) . w = z + zMSet Seq 6n w n n∈Odd n∈Even An easy application of Theorem 75 (see § 4.29) tells us this particular recursion equation has a recursively defined solution T(z) with a positive radius of convergence, and the asymptotics for the coefficients tn have the form (?) (?). The results of this paper apply to any combinatorial situation described by a recursion equation of the type studied here. We put our focus on classes of trees because they are by far the most popular setting for such equations. 4 The motivation for our work came when a colleague, upon seeing the asymptotics of Pólya for the first time, said “Surely the form (?) hardly ever occurs! (when finding the asymptotics for the solution of an equation w = Θ(w) that recursively defines a class of trees)”. A quick examination of the literature, a few examples, and we were convinced that quite the opposite held, that almost any reasonable class of trees defined by a recursive equation that is nonlinear in w would lead to an asymptotic law of Pólya’s form (?) (?). the electronic journal of combinatorics 13 (2006), #R63 5 1.5 First definitions We start with our basic notation for number systems, power series and open discs. Definition 3. (a) R is the set of reals; R≥0 is the set of nonnegative reals. (b) P is the set of positive integers. N is the set of nonnegative integers. (c) R≥0 [[z]] is the set of power series in z with nonnegative coefficients. (d) ρA is the radius (of convergence) of the power series A . P P n n (e) For A ∈ R≥0 [[z]] we write A = a(n)z or A = n n an z . (f) For r > 0 and z0 ∈ C the open disc of radius r about z0 is Dr (z0 ) := {z : |z−z0 | < r} 1.6 Selecting the domain We want to select a suitable collection of power series to work with when determining solutions w = T of recursion equations w = Φ(w). The intended application is that T be a generating series for some collection of combinatorial objects. Since generating series have nonnegative coefficients we naturally focus on series in R≥0 [[z]]. There is one restriction that seems most desirable, namely to consider as generating functions only series whose constant term is 0. A generating series T has the coefficient t(n) of z n counting (in some fashion) objects of size n. It has become popular when working with combinatorial systems to admit a constant coefficient when
it makes a result look simpler, for example with permutations we write A(z) = exp Q(z) , where A(z) is the exponential generating series for permutations, and Q(z) the exponential generating
series for cycles. Q(z) = log 1/(1 − z) will have a constant term 0, but A(z) = 1/(1 − z) will have the constant term 1. Some authors like to introduce an ‘ideal’ object of size 0 to go along with this constant term. There is a problem with this convention if one wants to look at compositions of operators. For example, suppose you wanted to look at sequences of permutations. The natural way to write theP generating series would be to apply the sequence operator Seq to 1/(1 − z) above, giving 1/(1 − z)n . Unfortunately this “series” has constant coefficient = ∞, so we do not have an analytical function. The culprit is the constant 1 in A(z). If we drop the 1, so that we are counting only ‘genuine’ permutations, the generating series for permutations is z/(1 − z); applying Seq to this gives z/(1 − 2z), an analytical function with radius of convergence 1/2. Consequently in this paper we return to the older convention of having the constant term be 0, so that we are only counting ‘genuine’ objects. Definition 4. For A ∈ R[[z]] we write A D 0 to say that all coefficients ai of A are nonnegative. Likewise for B ∈ R[[z, w]] we write B D 0 to say all coefficients bij are nonnegative. Let the electronic journal of combinatorics 13 (2006), #R63 6 (a) DOM[z] := {A ∈ R≥0 [[z]] : A(0) = 0}, the set of power series A D 0 with constant term 0; and let (b) DOM[z, w] := {E ∈ R≥0 [[z, w]] : E(0, 0) = 0}, the set of power series E D 0 with constant term 0 . Members of this class are called elementary power series. 5 When working with a member E ∈ DOM[z, w] it will be convenient to use various series formats for writing E, namely X E(z, w) = eij z i w j ij E(z, w) = X Ej (z)w j j E(z, w) = XX j  eij z w j . i i This is permissible from a function-theoretic viewpoint since all coefficients eij are nonnegative; for any given z, w ≥ 0 the three formats converge to the same value (possibly infinity). An immediate advantage of working with series having nonnegative coefficients is that the series is defined (possibly infinite) at its radius of convergence. Lemma 5. For T ∈ DOM[z] one has T(ρT ) ∈ [0, ∞]. Suppose T(ρT ) ∈ (0, ∞). Then ρT < ∞ ; in particular T is not a polynomial. If furthermore T has integer coefficients then ρT < 1. 2 The theoretical foundations We want to show that the series T that are recursively defined as solutions to functional equations w = G(z, w) are such that with remarkably frequency the asymptotics of the coefficients tn are given by (?) (?). Our main results deal with that G(z, w) is P thei case j holomorphic in a neighborhood of (0, 0), and the expansion gij z w is such that all coefficients gij are nonnegative. This covers most of the equations arising from combinations of the popular combinatorial operators like Sequence, MultiSet and Cycle. The referee noted that we had omitted one popular construction, namely Set, and the various restrictions SetM of Set, and asked that we explain this omission. Although the equation w = z +zSet(w) has been successfully analyzed in [17], there are difficulties when one wishes to form composite operators involving Set. These difficulties arise from the fact that the resulting equation w = G(z, w) has G with coefficients having mixed signs. A general discussion of the mixed signs case is given in § 6.1 and a particular discussion of the Set operator in § 6.2. Since the issue of mixed signs is so important we introduce the following abbreviations. 5 We use the name elementary since a recursion equation of the form w = E(z, w) is in the proper form to employ the tools of analysis that are presented in the next section. the electronic journal of combinatorics 13 (2006), #R63 7 Definition 6. A bivariate series E(z, w) and the associated functional equation w = E(z, w) are nonnegative if the coefficients of E are nonnegative. A bivariate series G(z, w) and the associated functional equation w = G(z, w) have mixed signs if some coefficients gij are positive and some are negative. To be able to locate the difficulties when working with mixed signs, and to set the stage for further research on this topic, we have put together an essentially complete outline of the steps we use to prove that a solution T to a functional equation w = E(z, w) satisfies the Pólya asymptotics (?) (?), starting with the bedrock results of analysis such as the Weierstraß Preparation Theorem and the Cauchy Integral Formula. Although this background material has often been cited in work on recursive equations, it has never been written down in a single unified comprehensive exposition. Our treatment of this background material goes beyond the existing literature to include a precise analysis of the nonnegative recursion equations whose solutions have multiple dominant singularities. 2.1 A method to prove (?) Given E ∈ DOM[z, w] and T ∈ DOM[z] such that T = E(z, T), we use the following steps to show that the coefficients tn satisfy (?) (?). (a) Show: T has radius of convergence ρ := ρT > 0. (b) Show: T(ρ) < ∞. (c) Show: ρ < ∞.  (d) Let: T(z) = z d V(z q ) where V(0) 6= 0 and gcd n : v(n) 6= 0 = 1. (e) Let: ω = exp(2πi/q). (f) Observe: T(ωz) = ω d T(z), for |z| < ρ. (g) Show: The set of dominant singularities of T is {z : z q = ρq }. (h) Show: T satisfies a quadratic equation, say Q0 (z) + Q1 (z)T(z) + T(z)2 = 0 for |z| < ρ and sufficiently near ρ, where Q0 (z), Q1 (z) are analytic at ρ. (i) Let: D(z) = Q1 (z)2 − 4Q0 (z), the discriminant of the equation in (g). (j) Show: D0 (ρ) 6= 0 in order to conclude that ρ is a branch point of order 2, that is, √ for |z| < ρ and sufficiently near ρ one has T(z) = A(ρ − z) + B(ρ − z) ρ − z, where A and B are analytic at 0, and B(0) < 0. (k) Design: A contour that is invariant under multiplication by ω to be used in the Cauchy Integral Formula to calculate t(n). the electronic journal of combinatorics 13 (2006), #R63 8 (l) Show: The full contour integral for t(n) reduces to evaluating the portion lying between the angles −π/q and π/q. (m) Optional: One has a Darboux expansion for the asymptotics of t(n). Given that E has nonnegative coefficients, items (a)–(f) can be easily established by imposing modest conditions on E (see Theorem 28). For (g) the method is to show that
one has a functional equation F z, T(z) = 0 holding for |z|
≤ ρ and sufficiently near
ρ, that F(z,
w) is holomorphic in a
neighborhood of ρ, T(ρ) , and that F ρ, T(ρ) = Fw ρ, T(ρ) = 0, but Fww ρ, T(ρ) 6= 0. These hypotheses allow one to apply the Weierstraß Preparation Theorem to obtain a quadratic equation for T(z). Theorem 7 (Weierstraß Preparation Theorem). Suppose F(z, w) is a function of two complex variables and (z0 , w0 ) is a point in C 2 such that: (a) F(z, w) is holomorphic in a neighborhood of (z0 , w0 ) (b) F(z0 , w0 ) = (c) ∂F ∂ k−1 F (z0 , w0 ) = · · · = (z0 , w0 ) = 0 ∂w ∂w k−1 ∂kF (z0 , w0 ) 6= 0. ∂w k Then in a neighborhood of (z0 , w0 ) one has F(z, w) = P(z, w)R(z, w), a product of two holomorphic functions P(z, w) and R(z, w) where (i) R(z, w) 6= 0 in this neighborhood, (ii) P(z, w) is a ‘monic polynomial of degree k’ in w, that is P(z, w) = Q0 (z)+Q1 (z)w+ · · · + Qk−1 (z)w k−1 + w k , and the Qi (z) are analytic in a neighborhood of z0 . Proof. An excellent reference is Markushevich [19], Section 16, p. 105, where one finds a leisurely and complete proof of the Weierstraß Preparation Theorem. There are two specializations of this result that we will be particularly interested in: k = 1 gives the Implicit Function Theorem, the best known corollary of the Weierstraß Preparation Theorem; and k = 2 gives a quadratic equation for T(z). 2.2 k = 1: The implicit function theorem Corollary 8 (k=1: Implicit Function Theorem). Suppose F(z, w) is a function of two complex variables and (z0 , w0 ) is a point in C 2 such that: (a) F(z, w) is holomorphic in a neighborhood of (z0 , w0 ) (b) F(z0 , w0 ) = 0 (c) ∂F (z0 , w0 ) 6= 0. ∂w the electronic journal of combinatorics 13 (2006), #R63 9 Then there is an ε > 0 and a function A(z) such that for z ∈ Dε (z0 ), (i) A(z) is analytic in Dε (z0 ) ,
(ii) F z, A(z) = 0 for z ∈ Dε (z0 ) , (iii) for all (z, w) ∈ Dε (z0 ) × Dε (w0 ), if F(z, w) = 0 then w = A(z). Proof. From Theorem 7 there is an ε > 0 and a factorization of F(z, w) = L(z, w)R(z, w), valid in Dε (z0 ) × Dε (w0 ), such that R(z, w) 6= 0 for (z, w) ∈ Dε (z0 ) × Dε (w0 ), and L(z, w) = L0 (z) + w, with L0 (z) analytic in Dε (z
0 ).
Thus A(z) = −L0 (z) is such that L z, A(z) = 0 on Dε (z0 ); so F z, A(z) = 0 on Dε (z0 ). Furthermore, if F(z, w) = 0 with (z, w) ∈ Dε (z0 ) × Dε (w0 ), then L(z, w) = 0, so w = A(z). 2.3 k = 2: The quadratic functional equation The fact that ρ is an order 2 branch point comes out of the k = 2 case in the Weierstraß Preparation Theorem. Corollary 9 (k = 2). Suppose F(z, w) is a function of two complex variables and (z 0 , w0 ) is a point in C 2 such that: (a) F(z, w) is holomorphic in a neighborhood of (z0 , w0 ) (b) F(z0 , w0 ) = (c) ∂F (z0 , w0 ) = 0 ∂w ∂2F (z0 , w0 ) 6= 0. ∂w 2 Then in a neighborhood of (z0 , w0 ) one has F(z, w) = Q(z, w)R(z, w), a product of two holomorphic functions Q(z, w) and R(z, w) where (i) R(z, w) 6= 0 in this neighborhood, (ii) Q(z, w) is a ‘monic quadratic polynomial’ in w, that is Q(z, w) = Q0 (z)+Q1 (z)w+ w 2 , where Q0 and Q1 are analytic in a neighborhood of z0 . 2.4 Analyzing the quadratic factor Q(z, w) Simple calculations are known (see [25]) for finding all the partial derivatives of Q and R
at z0 , w0 in terms of the partial derivatives of F at the same point. From this we can obtain important information about the coefficients of the discriminant D(z) of Q(z, w). Lemma 10. Given the hypotheses (a)-(c) of Corollary 9 let Q(z, w) and R(z, w) be as described in (i)-(ii) of that corollary. Then the electronic journal of combinatorics 13 (2006), #R63 10