636 ANSWERS TO EXERCISES 4.6.3 18. Call f(m) (Web site hosting)
636 ANSWERS TO EXERCISES 4.6.3 18. Call f(m) a nice function if (logf(m))r & -+ 0 as m + 00. A polynomial in m is nice. The product of nice functions is nice. If g(m) -+ 0 and c is a positive constant, then Pgcrn) is nice; also ( m$m)) is nice, for by Stirling s approximation this is equivalent to saying that g(m)log(l/g(m)) + 0. Now replace each term of the summation by the maximum term that is attained for any s, t, V. The total number of terms is nice, and so are (T$), ( t ) 5 2t+ , and /3 , because (t -Jr- w)/m -+ 0. Finally, ((,zSja) 5 (2m)2t/t! < (4m2/t)tet, where (4e)t is nice; setting t to its maximum value (1 - f ~)m/X(m), we have the upper bound (myt) = (mx(m)/(l -+))t = 2m( -t 2) . f(m), where f(m) is nice. Hence the entire sum is less than cP for large m, if o = 21PV, 0 < 11 < 4~. 19. (a) A4 n N, A4 U N, M M N, respectively; see Eqs. 4.6.2-6, 4.5.2-7. (b) f(z)g(z), lcm(f(z),g(z)), gcd(f(z),g(z)). (For the same reasons as (a), be- cause the manic irreducible polynomials over the complex numbers are precisely the polynomials z -<.) (c) Commutative laws AHB = BuA, AIJB = BuA, AnB = BnA. Associative lawsA~(Bl&C) = (AuB)uC, Au(BuC) = (AuB)uC, An(BnC) = (AnB)nC. Distributive laws A u (I3 n C) = (A u B) n (A u C), An (B u C) = (An B) U (A n C), A u (B u C) = (A U B) U (A M C), A M (B n C) = (A M B) n (A l3 C). Idempotent lawsAUA=A,AnA=A. AbsorptionlawsAu(AnB)=A,An(AUB)=A, An(AwB)=A,Au(AkgB)=AkdB. Identityandzerolaws0~A=A,0UA=A, 0 n A = 0, where 0 is the empty multiset. Counting law A kb B = (A U B) kl (A fl B). Further properties analogous to those of sets come from the partial ordering defined bytheruleAcBiffAnB=A(iffAUB=B). Notes: Other common applications of multisets are zeros and poles of meromorphic functions, invariants of matrices in canonical form, invariants of finite Abelian groups, etc.; multisets can be useful in combinatorial counting arguments and in the develop- ment of measure theory. The terminal strings of a noncircular context-free grammar form a multiset that is a set if and only if the grammar is unambiguous. Although multisets appear frequently in mathematics, they often must be treated rather clum- sily because there is currently no standard way to treat sets with repeated elements. Several mathematicians have voiced their belief that the lack of adequate terminology and notation for this common concept has been a definite handicap to the development of mathematics. (A multiset is, of course, formally equivalent to a mapping from a set into the nonnegative integers, but this formal equivalence is of little or no practical value for creative mathematical reasoning.) The author has discussed this matter with many people in an attempt to find a good remedy. Some of the names suggested for the concept were list, bunch, bag, heap, sample, weighted set, collection; but these words either conflict with present terminology, have an improper connotation, or are too much of a mouthful to say and to write conveniently. It does not seem out of place to coin a new word for such an important concept, and multiset has been sug- gested by N. G. de Bruijn. The notation A u B has been selected by the author to avoid conflict with existing notations and to stress the analogy with set union. It would not be as desirable to use A + B for this purpose, since algebraists have found that A + B is a good notation for { cr + p 1 (^Y E A and p E B}. If A is a multiset of nonnegative integers, let G(z) = xnEA zn be a generating function corresponding to A. (Generating functions with nonnegative integer coefficients obviously correspond one-to-one with multisets of nonnegative integers.) If G(z) corresponds to A and H(z) to B, then G(z) + H(z) corresponds to A w B and G(z)H(z) corresponds to A + B.