Mathematics for Computer Science

15.2. Counting Sequences 451

is the set of all sequences whose first term is drawn fromP 1 , second term is drawn
fromP 2 and so forth.

Rule 15.2.1(Product Rule).IfP 1 ;P 2 ;:::Pnare finite sets, then:

jP 1 P 2 :::PnjDjP 1 j
jP 2 j


jPnj

For example, suppose adaily dietconsists of a breakfast selected from setB, a
lunch from setL, and a dinner from setDwhere:

BDfpancakes;bacon and eggs;bagel;Doritosg

LDfburger and fries;garden salad;Doritosg

DDfmacaroni;pizza;frozen burrito;pasta;Doritosg

ThenBLDis the set of all possible daily diets. Here are some sample elements:

.pancakes;burger and fries;pizza/

.bacon and eggs;garden salad;pasta/

.Doritos;Doritos;frozen burrito/

The Product Rule tells us how many different daily diets are possible:

jBLDjDjBj
jLj
jDj

D 4 
 3 
 5

D60:

15.2.2 Subsets of ann-element Set

The fact that there are 2 nsubsets of ann-element set was proved in Theorem 5.1.5
by setting up a bijection between the subsets and the length-nbit-strings. So the
original problem about subsets was tranformed into a question about sequences —
exactly according to plan!. Now we can fill in the missing explanation of why there
are 2 nlength-nbit-strings: we can write the set of alln-bit sequences as a product
of sets:
f0;1gnWWDf„0;1gf0;1ƒ‚g:::f0;1...g
nterms

:

Then Product Rule gives the answer:

jf0;1gnjDjf0;1gjnD 2 n: