Mathematics for Computer Science

Chapter 14 Cardinality Rules604

Problems for Section 14.6

Practice Problems

Problem 14.27.
How many different permutations are there of the sequence of letters in “MISSIS-
SIPPI”?

Class Problems

Problem 14.28.
Find the coefficients of

(a)x^5 in.1Cx/^11

(b)x^8 y^9 in.3xC2y/^17

(c)a^6 b^6 in.a^2 Cb^3 /^5

Problem 14.29. (a)Use the Multinomial Theorem 14.6.5 to prove that

.x 1 Cx 2 C


Cxn/pxp 1 Cxp 2 C


Cxpn .modp/ (14.14)

for all primesp. (Do not prove it using Fermat’s “little” Theorem. The point of
this problem is to offer an independent proof of Fermat’s theorem.)

Hint:Explain why

 p

k 1 ;k 2 ;:::;kn

is divisible bypif all theki’s are positive integers
less thanp.

(b)Explain how (14.14) immediately proves Fermat’s Little Theorem 8.10.8:np^1 
1 .modp/whennis not a multiple ofp.

Homework Problems

Problem 14.30.
Thedegree sequenceof a simple graph is the weakly decreasing sequence of de-
grees of its vertices. For example, the degree sequence for the 5-vertex numbered
tree pictured in the Figure 14.7 in Problem 14.8 is.2;2;2;1;1/and for the 7-vertex
tree it is.3;3;2;1;1;1;1/.
We’re interested in counting how many numbered trees there are with a given
degree sequence. We’ll do this using the bijection defined in Problem 14.8 between
n-vertex numbered trees and lengthn 2 code words whose characters are integers
between 1 andn.