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:
1. Define the set S of the objects to be counted
2. What is the size of S ?
• breakup S as some combination of simpler sets
• transform S into a set, the size of which is already known

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=(A-B)union(Aintersect B)

B=(B-A)union(Aintersect B)

Aunion B=(A-B)union(Aintersect B)union(B-A).

(Practice: draw and prove those set identities!).

Then,
 | A | + | B | - | Aintersect B |
=
 ( | A-B | + | Aintersect B | )+( | B-A | + | Aintersect B | )- | Aintersect B |
=
 | A-B | + | Aintersect B | + | B-A |
=
 | Aunion B |

Exemple 3   In the example above, |C|=|M|+|U|-|Mintersect U|=5+3-2=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 double-major 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 sub-branches 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 (s1,s2,...,sn) 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:
1. binary strings of length 4?
2. 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!

Exercice 3   Count the following:
1. Strings of length 4 over {1,2,3,4,5} with no repetitions.
2. 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 18-19 p. 195
• Strings of length n over {1,...,n} with repetitions.
• Strings of length n over {0,1} with two consecutive 1.
• How many four-digits 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,...,An be n sets. Then,
 | A1union···union An |
=
 | A1 | +···+ | An |

 - | A1intersect A2 | -···- | An-1intersect An |

 + | A1intersect A2intersect A3 | +··· | An-2intersect An-1intersect An |

 +(-1)n+1 | A1intersect···intersect An |
=
 -- \ / -- Iincluded in{1,···,n}
(-1)
 | I | +1

|
|
|
|
 intersect iin I
Ai |
|
|
|

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 vice-president 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(n-1).
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(n-1)···(n-k+1)=n!/(n-k)!.

### 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(n-1)···(n-k+1)/k(k-1)···1=n!/k!(n-k)!.
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.
1. In how many ways can 3 freshmen and 5 sophomores be selected?
2. In how many ways can a committee with exactly 1 freshman be selected?
3. In how many ways can a committee with at most 1 freshman be selected?
4. 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+k-1,n).
Exemple 20   In how many ways can you distribute 10 lollipops between 4 kids, so that every kid get at least one lollipop ?

### 1.2.11  Summary

 Addition principle (A and B disjoint) |Aunion B|=|A|+|B| Principle of Inclusion-Exclusion |Aunion B|=|A|+|B|-|Aintersect B||A1union···union An|=··· Multiplication principle |A× B|=|A|·|B||Ak|=|A|k Sequences of k elements of S (|S|=n) nk Permutations: P(n,k)=n!/(n-k)! 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!(n-k)! All subsets of S 2n Combinations with repetitions C(n+k-1,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,n-k)

Proof.

1. Algebraic proof
2. Combinatorial proof
Définition 5   Combinatorial proof:

Goal: prove that two quantities a and b are equal

Technique:
1. construct a set A of size a;
2. construct a set B of size b;
3. construct a bijection between A and B
Problem 1   Recursive computation of C(n,k) ?

Théorème 10   C(n,k)=C(n-1,k)+C(n-1,k-1)

Proof.

1. Algebraic proof
2. 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)=2n

Proof.

1. Algebraic proof ?
2. 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 =
 k=n -- \ / -- k=0
C(n,k)xn-kyk
= C(n,0)xn+C(n,1)xn-1y+C(n,2)xn-2y2+···+C(n,n)yn

## 1.4  Conclusion

Sets Class notes Relations
Combinatorics / CSM MACS-358 / Nicolas M. Thiéry