Mathematics for Computer Science

Chapter 14 Cardinality Rules622

Problem 14.64.
When an integerkoccurs as thekth element of a sequence, we’ll say it is “in place”
in the sequence. For example, in the sequence

12453678

precisely the integers1;2;6;7and 8 occur in place. We’re going to classify the
sequences of distinct integers from 1 ton, that is the permutations ofŒ1;nç, accord-
ing to which integers do not occur “in place.” Then we’ll use this classification to
prove the combinatorial identity^10

nŠD 1 C

Xn

kD 1

.k1/
.k1/Š: (14.27)

Ifis a permutation ofŒ1;nç, let mnp./be themaximuminteger inŒ1;nçthat
does not occur in place in. For example, fornD 8 ,

mnp.12345687/D8;

mnp.21345678/D2;

mnp.23145678/D3:

(a)For how many permutations ofŒ1;nçis every element in place?

(b)How many permutationsofŒ1;nçhave mnp./D 1?

(c)How many permutations ofŒ1;nçhave mnp./Dk?

(d)Conclude the equation (14.27).

Problem 14.65.
Each day, an MIT student selects a breakfast from amongbpossibilities, lunch
from amonglpossibilities, and dinner from amongdpossibilities. In each case
one of the possibilities is Doritos. However, a legimate daily menu may include
Doritos for at most one meal. Give a combinatorial (not algebraic) proof based on
the number of legimate daily menus that

bldŒ.b1/C.l1/C.d1/C1ç

Db.l1/.d1/C.b1/l.d1/C.b1/.l1/d

3.b1/.l1/.d1/C.b1/.l1/.d1/

(^10) This problem is based on “Use of everywhere divergent generating function,”mathoverflow,
response 8,147 by Aaron Meyerowitz, Nov. 12, 2010.