Mathematics for Computer Science

Chapter 15 Cardinality Rules506

(c)Explain whyjAmjDbn=mc 1 form 2.

(d)Consider any two relatively prime numbersp;qn. What is the one number
in.Ap\Aq/Ap
q?

(e)LetPbe a finite set of at least two primes. Give a simple formula for

j

\

p 2 P

Apj:

(f)Use the Inclusion-Exclusion principle to obtain a formula forjC 150 jin terms
the sizes of intersections among the setsA 2 ;A 3 ;A 5 ;A 7 ;A 11. (Omit the intersec-
tions that are empty; for example, any intersection of more than three of these sets
must be empty.)

(g)Use this formula to find the number of primes up to 150.

Problems for Section 15.11

Class Problems

Problem 15.33.
According to the Multinomial theorem,.wCxCyCz/ncan be expressed as a
sum of terms of the form

n

r 1 ;r 2 ;r 3 ;r 4

!

wr^1 xr^2 yr^3 zr^4 :

(a)How many terms are there in the sum?

(b)The sum of these multinomial coefficients has an easily expressed value. What
is it?
X

r 1 Cr 2 Cr 3 Cr 4 Dn;

ri 2 N

n

r 1 ; r 2 ; r 3 ; r 4

!

D‹ (15.22)

Hint:How many terms are there when.wCxCyCz/nis expressed as a sum
of monomials inw;x;y;zbeforeterms with like powers of these variables are
collected together under a single coefficient?

Problem 15.34. (a)Give a combinatorial proof of the following theorem:

n2n^1 D

Xn

kD 1

k

n

k

!

(15.23)