310 6 Combinatorics and Probability
899.LetEbe a set withnelements andFa set withpelements,p≤n. How many
surjective (i.e., onto) functionsf:E→Fare there?
900.A permutationσof a setSis called a derangement if it does not have fixed points,
i.e., ifσ(x) =x for allx ∈S. Find the number of derangements of the set
{ 1 , 2 ,...,n}.
901.Given a graph withnvertices, prove that either it contains a triangle, or there exists
a vertex that is the endpoint of at mostn 2 edges.
902.Letm≥5 andnbe given positive integers, and suppose thatPis a regular( 2 n+ 1 )-
gon. Find the number of convexm-gons having at least one acute angle and having
vertices exclusive among the vertices ofP.
903.LetS^1 ={z∈C||z|= 1 }. For all functionsf :S^1 →S^1 setf^1 =f and
fn+^1 =f◦fn,n≥1. Callw∈S^1 a periodic point offof periodniffi(w) =w
fori= 1 ,...,n−1 andfn(w)=w.Iff(z)=zm,ma positive integer, find the
number of periodic points offof period 1989.
904.For positive integersx 1 ,x 2 ,...,xndenote by[x 1 ,x 2 ,...,xn]their least common
multiple and by(x 1 ,x 2 ,...,xn)their greatest common divisor. Prove that for
positive integersa, b, c,
[a, b, c]^2
[a, b][b, c][c, a]=
(a,b,c)^2
(a, b)(b, c)(c, a).
905.A 150× 324 ×375 rectangular solid is made by gluing together 1× 1 ×1 cubes.
An internal diagonal of this solid passes through the interiors of how many of the
1 × 1 ×1 cubes?
6.3 Probability
6.3.1 Equally Likely Cases
In this section we consider experiments with finitely many outcomes each of which can
occur with equal probability. In this case the probability of an eventAis given by
P (A)=
number of favorable outcomes
total number of possible outcomes.
The computation of the probability is purely combinatorial; it reduces to a counting
problem.
We start with the example that gave birth to probability theory.