Relations
Document also available in PDF, Postscript, DVI, Text, LaTeX, LyX.

Combinatorics

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 ?

=5+3=8

Théorème 1 (Addition principle) Let A and B be disjoint sets (e.g. Aintersect B=Ø). Then:

Aunion 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

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,

Aintersect B

(

A-B

Aintersect B

)+(

B-A

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

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₁,s₂,...,s_n) of elements of S.

lambda:=() is the empty string.

The set of all strings of length n is Sⁿ=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 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₁,...,A_n be n sets. Then,

A₁union···union A_n

A₁

+···+

A_n

A₁intersect A₂

-···-

A_n-1intersect A_n

A₁intersect A₂intersect A₃

+···

A_n-2intersect A_n-1intersect A_n

+(-1)ⁿ⁺¹

A₁intersect···intersect A_n

--
\
/
--

Iincluded in{1,···,n}

(-1)

|
|
|
|

intersect

iin I

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 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.

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+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\|\|A₁union···union A_n\|=···
Multiplication principle	\|A× B\|=\|A\|·\|B\|\|A^k\|=\|A\|^k
Sequences of k elements of S (\|S\|=n)	n^k
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	2ⁿ
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.

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(n-1,k)+C(n-1,k-1)

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ⁿ

Proof.

Algebraic proof ?
Combinatorial proof

1.3.1 The binomial theorem

Problem 2 Compute (x+y)ⁿ .

Théorème 12 There is a formula for expanding (x+y)ⁿ:

(x+y)ⁿ

k=n

--
\
/
--

k=0

C(n,k)x^n-ky^k

C(n,0)xⁿ+C(n,1)x^n-1y+C(n,2)x^n-2y²+···+C(n,n)yⁿ

1.4 Conclusion

Sets

Class notes

Relations
Combinatorics / CSM MACS-358 / Nicolas M. Thiéry
Last modified: Fri Jan 19 13:12:17 2007

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

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

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