1.6. Combinatorial results 9 number ρ such that, for each positive real number c 0, lim x→∞ R(cx) R(x) = cρ, in which case we say that the function R is of index ρ. One can prove that any regularly varying function of index ρ can be written in the form R(x) = xρL(x), where L is a slowly oscillating function. A nice result concerning slowly oscillating functions is the following. Proposition 1.9. Let L : [M, +∞) → R+, where M 0. Assume that L ∈ C1[M, +∞). Then L ∈ L ⇐⇒ x M dt L(t) = (1 + o(1)) x L(x) (x → ∞). (See Problem 1.12.) Various examples and applications are provided in the problems at the end of this chapter. 1.6. Combinatorial results Of frequent use in several arguments is the Pigeon Hole principle, which can be stated as follows: Proposition 1.10. (Pigeon Hole principle) Given n objects which are to be inserted in n − 1 distinct boxes, one can always find one particular box containing at least two of these objects. The other frequently used combinatorial tool is the Inclusion-Exclusion principle, which can be stated as follows: Proposition 1.11. (Inclusion-Exclusion principle) Denoting by P (A) the probability that an event A occurs, by P (A ∪ B) the probability that A or B occurs and by P (A ∩ B) the probability that A and B occur, and letting A1,A2,...,An be events, then P (A1 ∪ A2 ∪ . . . ∪ An) = 1≤i≤n P (Ai) − 1≤ij≤n P (Ai ∩ Aj) + 1≤ijk≤n P (Ai ∩ Aj ∩ Ak) − · · · + (−1)n+1P (A1 ∩ A2 ∩ . . . ∩ An).

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2012 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.