Sets
Class notes
Relations
Document also available in PDF, Postscript, DVI, Text, LaTeX, LyX.
Chapter 1 Combinatorics (section 3.2...3.5)
1.1 Introduction
Goal: answer ``How many ?'' questions:

How many ways to climb a stair ?
 How many rows in a truth table ?
 How many trees ?
Applications:

Analysis of algorithms
 Statistics
 Size of a database
1.2 Counting
1.2.1 Preliminaries
Définition 1
The size of a finite set is the number of elements in this
set.
The size of S is denoted by S (or, often in the
literature, # S).
Note 1
In the sequel, we only consider finite sets !
A``how many ?'' question is usually formalized as follow:

Define the set S of the objects to be counted
 What is the size of S ?
Techniques to answer this question:

breakup S as some combination of simpler sets
 transform S into a set, the size of which is already known
1.2.2 The addition principle
Exemple 1
A small company wants to know how many computers it owns, given that
it owns 5 Mac's, and 3 UNIX stations.
Let:

C be the sets of computers,
 M be the set of Mac's (M=5),
 U be the set of UNIX stations (U=3).
Then, C=Munion U.
What is the size of C ?

 
C 
 
= 
 
M 
 
+ 
 
U 
 
=5+3=8 
Théorème 1
(Addition principle) Let A and B be disjoint sets (e.g. Aintersect B=Ø).
Then:

 
Aunion B 
 
= 
 
A 
 
+ 
 
B 
 
. 
Exemple 2
Imagine 2 of the 5 Mac's are actually running Linux.
What is the size of C ?
Well, C=6<8.
So, the disjoint hypothesis is important !
What to do when the sets are not disjoint ?
Théorème 2
Let A and B be two sets. Then:

 
Aunion B 
 
= 
 
A 
 
+ 
 
B 
 
 
 
Aintersect B 
 
. 
Proof.
We just have to split A, B, and Aunion B into unions of disjoint
subsets:
A=(AB)union(Aintersect B)
B=(BA)union(Aintersect B)
Aunion B=(AB)union(Aintersect B)union(BA).
(Practice: draw and prove those set identities!).
Then,
 
A 
 
+ 
 
B 
 
 
 
Aintersect B 
 

= 
( 
 
AB 
 
+ 
 
Aintersect B 
 
)+( 
 
BA 
 
+ 
 
Aintersect B 
 
) 
 
Aintersect B 
 


= 
 
AB 
 
+ 
 
Aintersect B 
 
+ 
 
BA 
 


= 

Exemple 3
In the example above, C=M+UMintersect U=5+32=6.
Exercice 1
There are 24 students in a class, all of them are math majors or
computer science major. 10 are math majors, and 20 are computer
science majors. How many doublemajor are there in this class ?
1.2.3 The multiplication principle
Exemple 4
You are a car dealer. For each car you sell, you propose several options
(color, 2WD/4WD, airbag, ABS, radio, ...). Of course, you would
like to always have all possible combinations of options in stock.
On the other hand, you cannot afford to store too many cars in your
parking lot. So you need to know how many possible combinations of
options there are.

2WD / 4WD
 Black / Yellow / Green
How many combinations are there ?
First solution: draw a decision tree
.
The choices are independent!
The number of subbranches at each level is constant.
Therefore, we have 2·3=6 choices.
Let's formalize this.
Let C be the set of all choices. Each choice can be represented
by a couple.
For example a yellow 2WD car with black seats can be represented as:
(2,Y)
So, C can be viewed as the cross product:
{2,4}×{ B,Y,G}.
Théorème 3
Let A and B be two sets. Then,

 
A× B 
 
= 
 
A 
 
· 
 
B 
 
. 
Exemple 5
In the example above, C={2,4}×{ B,Y,G}={2,4}·{ B,Y,G}=2·3=6.
Exercice 2
How many possible different phone numbers are there ?
Strings
Strings are commonly used objects in computer science.
``how many'' questions often be translate into questions about
sets of strings.
Définition 2
Let S be a set, that we call alphabet.
Elements of S are called letters.
A string over S is a sequence (s_{1},s_{2},...,s_{n})
of elements of S.
lambda:=() is the empty string.
The set of all strings of length n is S^{n}=S×···× S.
The set of all finite strings over S is denoted S^{*}.
A language is a set of strings.
Exemple 6
Let S:={0,1}. A string over S, like 001001 is called
a binary string.
Let S:={ a,b,...,z}. Then bonjour is a string over
S of length 7.
A phone number 3032733462 is a string over {0,1,2,3,4,5,6,7,8,9}.
The set of all English words is a language.
Exemple 7
Count the following:

binary strings of length 4?
 strings of length n over an alphabet containing p letters ?
1.2.4 Decision trees
Exemple 8
A kid is allowed to pick 3 candies (one after another), out of
one jelly bean, one lollipop and 2 gummy bears (one blue, one yellow).
In how many ways can he do this ?
Draw a decision tree.
The choices are not independent
The multiplication principle does not apply.
However, the number of choices at each step does not change!
So the answer is: 5·4·3=60.
Exercice 3
Count the following:

Strings of length 4 over {1,2,3,4,5} with no repetitions.
 Strings of length n over {1,...,n} with no repetitions.
Exercice 4
How many ways to toss a coin five times without two heads in a row
?
Note: the decision tree is irregular.
1.2.5 Combining those principles together
Exemple 9
Count the following:
Exercise 1819 p. 195

Strings of length n over {1,...,n} with repetitions.
 Strings of length n over {0,1} with two consecutive 1.
 How many fourdigits numbers begin with 4 or 5?
 How many ways to toss a coin seven times with two heads in a row ?
1.2.6 Principle of Inclusion and Exclusion
Exemple 10
All the guests at a dinner party drink coffee, chocolate or tea; 11drink
coffee, 9 drink tea, 10 drink chocolate; 3 drink coffee and
tea, 5 drink tea and chocolate; 6 drink coffee and chocolate
Formalization: what is the size of Aunion Bunion C?
Generalization ?
Théorème 4
(Principle of Inclusion and exclusion)
Let A_{1},...,A_{n} be n sets. Then,
 
A_{1}union···union A_{n} 
 

= 
 
A_{1} 
 
+···+ 
 
A_{n} 
 



 
 
A_{1}intersect A_{2} 
 
··· 
 
A_{n1}intersect A_{n} 
 



+ 
 
A_{1}intersect A_{2}intersect A_{3} 
 
+··· 
 
A_{n2}intersect A_{n1}intersect A_{n} 
 



+(1)^{n+1} 
 
A_{1}intersect···intersect A_{n} 
 


= 


\
/
 
Iincluded in{1,···,n} 

(1) 




 

A_{i} 



 

Proof.
Induction.
1.2.7 Pigeon Hole principle
Exercice 5
It's early in the morning, and you don't want to wake up your significant
whatever by turning on the light. You know you only have black and
white socks in your drawer. Is it possible to exit the room with at
least two socks with the same color ?
Théorème 5
(Pigeon hole principle)
If more than k items are placed in k bins, then at least one
bin has more than one item inside.
Exemple 11
How many people do you need to have in a room to ensure at least two
of them have the same birthday ?
1.2.8 Permutations: sequences without repetitions
Exemple 12
How many ways to choose a committee with 1 president and 1 vicepresident
out of a group of n persons.
This amount to find the number of strings of length 2 over a set
of size n, without repetitions. This is n(n1).
Définition 3
We denote by P(n,k) the number of strings of length k over a
set of size n without repetitions.
Exemple 13
P(n,0)= , P(n,1)= , P(n,n)= ,
P(1,2)= .
Théorème 6
P(n,k)=n(n1)···(nk+1)=n!/(nk)!.
1.2.9 Combinations
Exemple 14
How many ways to choose 3 voluntaries out of a group of 5 persons?
Définition 4
We denote by C(n,k) the number of subsets of size k of a set
of size n.
Exemple 15
C(n,0)= , C(n,1)= , C(n,n)= ,
C(1,2)= .
Théorème 7
C(n,k)=n(n1)···(nk+1)/k(k1)···1=n!/k!(nk)!.
Exemple 16
Ex. 51 p. 210:
A committee of 8 students is to be selected from a class consisting
of 19 freshmen and 34 sophomores.

In how many ways can 3 freshmen and 5 sophomores be selected?
 In how many ways can a committee with exactly 1 freshman be selected?
 In how many ways can a committee with at most 1 freshman be selected?
 In how many ways can a committee with at least 1 freshman be selected?
Exemple 17
What is the total number of subsets of S ?
Exemple 18
What is the number of paths between Stratton Hall and Golden Tourism
Information center ?
1.2.10 Combinations with repetitions
Exemple 19
In how many ways can you distribute 10 lollipops between 4 kids.
Théorème 8
The number of combinations with repetitions of k elements of a
set S of size n is C(n+k1,n).
Exemple 20
In how many ways can you distribute 10 lollipops between 4 kids,
so that every kid get at least one lollipop ?
Addition principle (A and B disjoint) 
Aunion B=A+B 
Principle of InclusionExclusion 
Aunion B=A+BAintersect BA_{1}union···union A_{n}=··· 
Multiplication principle 
A× B=A·BA^{k}=A^{k} 
Sequences of k elements of S (S=n) 
n^{k} 
Permutations: 
P(n,k)=n!/(nk)! 
Sequences of k elements of S, w/o repetitions 

Sequences of k elements of {0,1}, w/o successive 1 
Fibonacci: F(k) 
Combinations: subsets of size k of S 
C(n,k)=n!/k!(nk)! 
All subsets of S 
2^{n} 
Combinations with repetitions 
C(n+k1,k) 
1.3 Properties of binomial coefficients; Combinatorial proofs
Exemple 21
How many subsets of size 14 of a set of size 15 ?
Théorème 9
C(n,k)=C(n,nk)
Proof.

Algebraic proof
 Combinatorial proof
Définition 5
Combinatorial proof:
Goal: prove that two quantities a and b are equal
Technique:

construct a set A of size a;
 construct a set B of size b;
 construct a bijection between A and B
Problem 1
Recursive computation of C(n,k) ?
Théorème 10
C(n,k)=C(n1,k)+C(n1,k1)
Proof.

Algebraic proof
 Combinatorial proof
Exemple 22
Compute C(7,4), without calculator.
Définition 6
Pascal triangle:
nk 
0 
1 
2 
3 
4 
5 
6 
7 
0 
1 







1 
1 
1 






2 
1 
2 
1 





3 
1 
3 
3 
1 




4 
1 
4 
6 
4 
1 



5 
1 
5 
10 
10 
5 
1 


6 
1 
6 
15 
20 
15 
6 
1 

7 
1 
7 
21 
35 
35 
21 
7 
1 
Théorème 11
C(n,0)+···+C(n,n)=2^{n}
Proof.

Algebraic proof ?
 Combinatorial proof
1.3.1 The binomial theorem
Problem 2
Compute (x+y)^{n} .
Théorème 12
There is a formula for expanding (x+y)^{n}:
(x+y)^{n} 
= 


= 
C(n,0)x^{n}+C(n,1)x^{n1}y+C(n,2)x^{n2}y^{2}+···+C(n,n)y^{n} 
1.4 Conclusion
Sets
Class notes
Relations
Combinatorics /
CSM MACS358 /
Nicolas M. Thiéry
Last modified: Fri Jan 19 13:12:17 2007