Counting by Mapping

A B

… f …
 This
Lecture
We will study how to define mappings to
count.

There will be many examples shown.

• Bijection
rule

• Division
rule

• More
mapping
 Counting Rule:
Bijection
If f is a bijection from A to B,
then |A| = |B|

A B

… f …

To compute |A|, one strategy is to define a bijection of A

and B,
where B is easier to count and we can compute |B| directly.
 Power
Set
How many subsets of a set S?

P(S) = the power set of S

= the set of all subsets of
S
for S = {a, b, c},
P(S) = {∅, {a}, {b}, {c}, {a,b}, {a,c},
{b,c}, {a,b,c} }

Suppose S has n elements.

How large is the power set of

S?
 Bijection: Power Set and Binary
Strings
S : {s1, s2, s3, s4, s5,
… , s n}
We define a bijection between subsets and binary
strings

A: the set of all subsets of S

A B
… …
f B: the set of all binary strings of
length n

The mapping is defined in the following

way:
subset: {s1, s3, s4,
… , s n}
string: 1 0 1 1 0 …
1
 Bijection: Power Set and Binary
Strings
The mapping is defined in the following
way:
subset: {s1, s3, s4, A B
… , s n} … …
string: 1 0 1 1 0 … f
1

This mapping is a bijection, because

❖ two different subsets are mapped to two different strings
(injection)
❖ each binary string represents some subset (surjection).
Therefore, |A| = |B|, and |B| can be computed
directly.

So, |n-bit binary strings| = |

P(S)|
 A Chess
Problem
In how many different ways can we place a pawn
(p),
a knight (k), and a bishop (b) on a chessboard so
that
no two pieces share a row or a column?
 A Chess
Problem
We define a mapping between configurations
to
sequences (r(p), c(p), r(k), c(k), r(b), c(b)),
where r(p), r(k), and r(b) are distinct rows,
and c(p), c(k), and c(b) are distinct columns.

A: the set of the configurations of the 3

A B pieces
… …
f
B: the set of the such sequences of 6
numbers

If we can define a bijection between A and B,

and also calculate |B|, then we can determine
|A|.
 A Chess
Problem
We define a mapping between configurations
to
sequences (r(p), c(p), r(k), c(k), r(b), c(b)),
where r(p), r(k), and r(b) are distinct rows,
and c(p), c(k), and c(b) are distinct columns.

(7,6,2,5,5,2
)

(2,5 This is a bijection,

) because:
❖ it is an injection
(5,2
) ❖ it is a surjection
So, to count the number of chess configurations,
(7,6
) it is equivalent to count the number of such
 A Chess
Problem
We define a mapping between configurations
to
sequences (r(p), c(p), r(k), c(k), r(b), c(b)),
where r(p), r(k), and r(b) are distinct rows,
and c(p), c(k), and c(b) are distinct columns.

Using the generalized product

rule,
there are 8 choices of r(p) and
c(p),
there are 7 choices of r(k) and
c(k),
Thus, total number of
configurations
there are 6 choices of r(b) and
(7,6,2,5,5,2 = (8x7x6)2 = 112896.
c(b).
)
 Counting Doughnut
Selections
There are five kinds of doughnuts.

How many different ways to select a dozen

doughnuts?
00 (none) 000000 00
00
Chocolate Lemon Sugar Glazed
Plain
A ::= all selections of a dozen
doughnuts

Hint: define a A B
bijection! … …
f
 Counting Doughnut
Selections
A ::= all selections of a dozen
doughnuts
B::= all 16-bit binary strings with exactly four
1’s.
Define a bijection between A and
B.

00110000001001
00
00 1 1 000000 1 00 1
00
00 (none) 000000 00
00
Chocolate Lemon Sugar Glazed
Plain
Each doughnut is represented by a 0,
and four 1’s are used to separate five types of
 Counting Doughnut
Selections
A ::= doughnuts selections B::= all 16-bit strings with four
1’s.
12 0 0 0 0 00000000000011
Chocolate Lemon Sugar Glazed
11
Plain
2 3 0 3 4 00100011000100
Chocolate Lemon Sugar Glazed
00
Plain

2 0 6 2 00110000001001
2
Chocolate Lemon Sugar Glazed
00
Plain
0 0 0 0
12 11110000000000
Chocolate Lemon Sugar Glazed 00
13
Plain
 Counting Doughnut
Selections
c chocolate, l lemon, s sugar, g glazed, p plain
maps to
0c10l10s10g1
0p
A ::= all selections of a dozen
doughnuts
B::= all 16-bit binary strings with exactly four
1’s.
This is a bijection because

•Two doughnut selections map to two different strings. (injection)

(think of a doughnut selection as a sequence of 5 numbers
(c,l,s,g,p),
consider the first number which is different in the two
sequences). 14
 Counting Doughnut
Selections

c chocolate, l lemon, s sugar, g glazed, p

plain
maps to a
bijection
0c10l10s10g1
0 p
A ::= all selections of a dozen
doughnuts
B::= all 16-bit binary strings with exactly four
1’s.
 Choosing Non-Adjacent
Books

There are 20 books arranged in a row on a

shelf.

How many ways to choose 6 of these books so

that
noall
A ::= two adjacentof
selections books are selected?
6 non-adjacent books from 20
books

Hint: define a A B
bijection! … …
f
 Choosing Non-Adjacent
Books
A ::= all selections of 6 non-adjacent books from 20
books
B::= all 15-bit binary strings with exactly six
1’s.

Map each zero to a non-chosen book, each of the first five 1’s to a
chosen
book followed by a non-chosen book, and the last 1 to a chosen book.
This is a bijection,
because:
❖ it is an injection
❖ it is a surjection
 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14
1 0 0 1 1 0 0 0 1 0 0 1 0 0 1

1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2
0 1 2 3 4 5 6 7 8 9 0
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14
0 1 1 0 0 0 1 0 0 1 0 0 1 0 1

1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2
0 1 2 3 4 5 6 7 8 9 0
 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14
1 0 0 1 1 0 0 0 1 0 0 1 0 1 0

1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2
0 1 2 3 4 5 6 7 8 9 0

Note that, this is the last

one chosen; but not
necessarily the last one of
the selection
 Choosing Non-Adjacent
Books

A ::= all selections of 6 non-adjacent books from 20

books
B::= all 15-bit binary strings with exactly six
1’s.
 Counting
Loops
for i=1 to n do
for j=1 to i do
for k=1 to j do
printf(“hello world\
n”);

How many “hello world” will this program

print?

A ::= all (i,j,k) triple

B::= all strings with n-1 zeroes and 3

ones.

21
 Counting
Loops
for i=1 to n do
for j=1 to i do
for k=1 to j do
printf(“hello world\
n”);

There are n possible values for the

i,j,k.
1 2 3 4 5 …
n
…

Imagine there are n-1 separators for the n

values.
If i=4, j=2, k=2, then there are two zeroes in 2 and one zero
in 4. 22
 Counting
Loops
for i=1 to n do
for j=1 to i do
for k=1 to j do
printf(“hello world\
n”);

There are n possible values for the

i,j,k.
1 2 3 4 5 …
n n–
1+3
… C3
k j i

In general, the position of the first zero corresponds to the value

of k.
The position of the second zero corresponds to the value of j.
The position of the third zero corresponds to the value of i. 23
10– 10–
1+3 = 1+3
C3 C3

= 22
0
 Counting Non-Negative Integer
Solutions
How many solutions are there to the equation
x1+x2+x3+x4=10,

where x1,x2,x3,x4 are nonnegative integers?

It is just like buying 10 doughnuts from 4
types.
A ::= all non-negative integer solutions
x1+x2+x3+x4=10
B::= all 13-bit binary strings with exactly three
1’s.

Think of there are 10 points to be distributed into 4

variables.
x1 x 2 x3
e.g. Suppose x1=3, x2=5, x3=2,
x4
x4=0,
0 0 0 0 0 0 0 0 0
0 the 3 ones are used for 25

separations.
 Counting Non-Negative Integer
Solutions
How many solutions are there to the equation
x1+x2+x3+x4=10,

where x1,x2,x3,x4 are nonnegative integers?

It is just like buying 10 doughnuts from 4
types.
A ::= all non-negative integer solutions
x1+x2+x3+x4=10
B::= all 13-bit binary strings with exactly three
1’s.

It is not difficult to verify that this is a

bijection,
by the same argument as in doughnut
selections.
So, the are exactly integer
solutions. 26
 Counting Positive Integer
Solutions
How many integer solutions to x1+x2+x3+x4=14 if
each xi>=1?

Set xi=yi+1. So, y1 = x1-1; y2 = x2-1; y3 = x3-1; y4 =

x4-1;

Consider the equation y1+y2+y3+y4=10 where

each yi >=0.

There is a bijection between the solutions for y

and

the solutions for x.

27
Therefore we can apply the previous result,
 Counting Positive Integer
Solutions
How many integer solutions to x1+x2+x3+x4<=10 if
each xi>=0?

Consider the equation y1+y2+y3+y4+y5=10 where

each yi>=0.

There is a bijection between the solutions for y and

the solutions for x.

Therefore we can apply the previous result,

and conclude that the answer is

because we need 4 ones and 10 zeroes.

28
 Choosing Non-Adjacent Books
Revisited
A ::= all selections of 6 non-adjacent books from 20
books
B::= the set of integer solutions to
x1+x2+x3+x4+x5+x6<=20
where x1>=1 and x2,x3,x4,x5,x6>=2.
Here, each xi represents to pick the xith book after the previous chosen
book.
1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2
0 1 2 3 4 5 6 7 8 9 0

e.g. this configuration corresponds to x1=1, x2=4, x3=2, x4=5,

x5=4, x6=4.

It is not difficult to check that this is a

bijection. 29
 Choosing Non-Adjacent Books
Revisited
A ::= all selections of 6 non-adjacent books from 20
books
B::= the set of integer solutions to
x1+x2+x3+x4+x5+x6<=20
where
Set, x1 = y1+1 => yx11>=
>=10 and
and xfor
2,xi3,x
∈4,x 5,x6>=2.
{2..6}, xi = yi+2 => yi>= 0, So,
y1,y2,y3,y4,y5,y6>=0
C::= the set ofSo, we can
integer say: |B|=|C|
solutions to for
y1+y2+y3+y4+y5+y6<=9
where y1,y2,y3,y4,y5,y6>=0.
Again, we can say |C|=|D|
for
D::= the set of integer solutions to
y1+y2+y3+y4+y5+y6+y7=9
where y1,y2,y3,y4,y5,y6,y7>=0.

So, |D| exactly integer solutions are

=
there to the equation x1 + x2 + x3 + x4=
10, where x1,x2,x3,x4 are nonnegative
integers?
30
This
Lecture

• Bijection
rule

• Division
rule

• More
mapping
 Division
Rule
if function from A to B is k-to-1,
then

(generalizes the Bijection Rule)

 Another Chess
Problem
In how many different ways can you
place two identical rooks on a
chessboard so that
they do not share a row or column?
 Another Chess
Problem
We define a mapping between
configurations
to sequences (r(1), c(1), r(2), c(2)),
where r(1) and r(2) are distinct rows,
and c(1) and c(2) are distinct columns.
A ::= all sequences (r(1),c(1),r(2),c(2)) with r(1) ≠ r(2) and c(1)
≠ c(2)
B::= all valid rook
configurations
(1,1,8,8) and (8,8,1,1)
maps
to the same
configuration.
The mapping is a 2-to-1
mapping.
 Another Chess
Problem
A ::= all sequences (r(1),c(1),r(2),c(2)) with r(1) ≠ r(2) and c(1)
≠ c(2)
B::= all valid rook
configurations

The mapping is a 2-to-1

mapping.

Using the generalized product rule to count

|A|,
there are 8 choices of r(1) and c(1),
there are 7 choices of r(2) and c(2),
and so |A| = 8x8x7x7 = 3136.

Thus, total number of

configurations
|B| = |A|/2 = 3136/2 = 1568.
 Round
Table
How many ways can we seat n different people at a round
table?

Two seatings are considered equivalent if

one can be obtained from the other by
rotation.

equivale
nt
 Round
Table
A ::= all the permutations of the
people
B::= all possible seating arrangements at the round
table

Map each permutation in set A to a circular seating

arrangement in set B by following the natural order in the
permutation.
 Round
Table
A ::= all the permutations of the n
people
!
B::= all possible seating arrangements at the round
table

This mapping is an n-to-1

mapping.

Thus, total number of seating

arrangements
|B| = |A|/n = n!/n = (n-1)!
 Counting
Subsets

How many size 4 subsets of {1,2,…,13} are

there?

Let A::= permutations of {1,2,…,13}

B::= size 4 subsets

map a1 a2 a3 a4 a5… a12 a13 to

{a1,a2 ,a3, a4}

How many permutations are mapped to the same

subset??
 Counting
Subsets

map a1 a2 a3 a4 a5… a12 a13

to

{a1,a2 ,a3 , a4}

a2 a4 a3 a1 a5 … a12 a13 also maps
to

{a1,a2 ,a3, a4}

as does

a2 a4 a3 a1 a13 a12 … a5
4 9
! !

So this mapping 4!×9!-to-

is
1
 Counting
Subsets
Let A::= permutations of {1,2,…,13}

B::= size 4 subsets

So number of 4 element
subsets is

Number of m element subsets of an n element

set is
 MISSISSIPPI

How many ways to rearrange the letters in the word

“MISSISSIPPI”?

Let A be the set of all permutations of n letters.

B be the set of all different words by rearranging
“MISSISSIPPI”.
How many permutations are mapped to the same
word?
4! possible ways to rearrange the S giving the same
word
MISSISSIPPI 4! possible ways to rearrange the I giving the same
word
2! possible ways to rearrange the P giving the same
word

The mapping is 4!4!2!-to-1, and so there are 11!/4!4!2! different

words.
 Example: 20 Mile
Walk
I’m planning a 20-mile walk, which should include 5 northward miles,
5 eastward miles, 5 southward miles, and 5 westward miles.

How many different walks are possible?

There is a bijection between such walks and sequences with 5 N’s, 5

E’s, 5 S’s, and 5 W’s.

The number of such sequences is equal to the number of

rearrangements:
20!
5!5!5!5!
This
Lecture

• Bijection
rule

• Division
rule

• More
mapping
 Parenthe
sis
How many valid ways to add n pairs of
parentheses?

E.g. There are 5 valid ways to add 3 pairs of

parentheses.
((())) (()()) (())() ()(()) ()
()()

Let rn be the number of ways to add n pairs of

parentheses.

A pairing is valid if and only if there are at least as

many
open parentheses than close parentheses from the
left.
 Monotone
Path
A monotone path from (0,0) to (n,n) is a path consisting of
“right" moves (x-coordinate increase by 1) and “up" moves
(y-coordinate increase by 1), starting at (0,0) and ending at
(n,n).
We say such a path “lower-right" monotone path if all of
the points (xi,yi) on the path has xi >= yi.

lower-right NOT lower-right

monotone monotone
 Mountain
Ranges
How many “mountain ranges” can you form with n
upstrokes
and n downstrokes that all stay above the original line?

/\
/\ /\ /\/\ / \
/\/\/\, /\/ \, / \/\, / \, / \

We do not know how to solve these three problems yet, but

we can show that all these three problems have the same
answer,
by showing that there are bijections between these sets.
 Parenthesis and Monotone
Paths
A pairing is valid if and only if there are at least as
many
open parentheses than close parentheses from the
A monotone
left. path is “lower-right” if and only if there are at
least as many right moves than up moves from the starting
point.
(()()()) ()() ())(()
()() ()

So there is a bijection between these two sets by each open

parenthesis with a right move and a close parenthesis by an up
 Monotone Paths and Mountain
Ranges

By “rotating” the images, we see that a path not crossing the

diagonal
is just the same as a mountain not crossing the horizontal line.
So there is a bijection between them by mapping “right” to “up” and “up”
to “down”
Parenthesis, Monotone Paths and
Mountain Ranges

Now we know that these three sets are of equal size,

although we don’t know the size.

It turns out that the answer is exactly

This is called the nth Catalan number,

and has applications in many other places as well.

We will not compute it in the lecture. This is FYI for

now.
 Quick
Summary

Counting by mapping is a very useful technique.

It is also a powerful technique to solve more complicated problems.

The basic examples usually map a set into a properly defined binary
strings.

Then we see how to generalize this approach by considering k-to-1

functions.

Finally we see the mapping between more complicated sets.