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).
Previous Page Next Page