CS 207 Discrete Mathematics – 2012-2013

(1)

CS 207 Discrete Mathematics – 2012-2013

Nutan Limaye

Indian Institute of Technology, Bombay nutan@cse.iitb.ac.in

Combinatorics Lecture 8: Double counting

August 14, 2012

Nutan (IITB) CS 207 Discrete Mathematics – 2012-2013 May 2011 1 / 1

(2)

Course Outline

Mathematical reasoning and mathematical objects Combinatorics

Elements of graph theory Elements of abstract algebra

(3)

Course Outline

Mathematical reasoning and mathematical objects

I What is a proof? Types of proof methods

I Induction

I Sets, relations, functions, partial orders, graphs Combinatorics

(4)

Course Outline

Mathematical reasoning and mathematical objects

I What is a proof? Types of proof methods

I Induction

I Sets, relations, functions, partial orders, graphs

Text: Discrete Mathematics and its applictions, by Kenneth Rosen Chapter 2 : 2.1,2.2,2.3, Chapter 8 : 8.1,8.5,8.6

Class notes: uploaded on Moodle Combinatorics

(5)

Course Outline

I Double counting

I Approximating sums and products

I Pigeonhole principle

I Recurrence relations and generating functions

I Inclusion-exclusion principle

I Elements of discrete probability Elements of graph theory

Elements of abstract algebra

(6)

Course Outline

I Double counting

I Approximating sums and products

I Pigeonhole principle

I Recurrence relations and generating functions

I Inclusion-exclusion principle

I Elements of discrete probability

Text: Discrete Mathematics and its applictions, by Kenneth Rosen Chapter 5, Chapter 6 : 6.1,6.4, Chapter 7

Class notes: uploaded on Moodle Elements of graph theory

Elements of abstract algebra

(7)

Let us count

Warm up exercises:

How many reflexive relations are there on a set, sayA, of size n? Prove that

n

X

k=0

n k

= 2ⁿ

I Of course, one could give an inductive proof. However, here is another proof.

(8)

Let us count

Warm up exercises:

How many reflexive relations are there on a set, sayA, of size n?

Prove that

n

X

k=0

n k

= 2ⁿ

(9)

Let us count

Warm up exercises:

I There aren²ordered pairs of elements if the set is of sizen.

I We are required to put a pair of the form (x,x) in a reflexive relation for eachx∈A.

I The rest of pairs,n²−nof them, may or may not be put.

I Therefore, there are 2ⁿ²⁻ⁿ different reflexive relations. Prove that

n

X

k=0

n k

= 2ⁿ

(10)

Let us count

Warm up exercises:

n

X

k=0

n k

= 2ⁿ

(11)

Let us count

Warm up exercises:

n

X

k=0

n k

= 2ⁿ

(12)

Let us count

Warm up exercises:

I Therefore, there are 2ⁿ²⁻ⁿ different reflexive relations.

Prove that

n

X

k=0

n k

= 2ⁿ

(13)

Let us count

Warm up exercises:

Prove that

n

X

k=0

n k

= 2ⁿ

(14)

Let us count

Warm up exercises:

Prove that

n

X

k=0

n k

= 2ⁿ

I On LHS, fix ak. Then ⁿ_k

is basically the number of ways of choosing k people from npeople. By summing overk, we are essentially counting the total number of ways of forming a committee from a set ofnpeople.

(15)

Let us count

Warm up exercises:

Prove that

n

X

k=0

n k

= 2ⁿ

I However, that is the same as counting all possible subsets of a set of sizen,which we know is 2ⁿ.

(16)

Let us count

Warm up exercises:

Prove that

n

X

k=0

n k

= 2ⁿ

I However, that is the same as counting all possible subsets of a set of sizen,which we know is 2ⁿ.

I As LHS and RHS are counting the same quantity they must be equal.

(17)

Let us count

Slightly hard exercises: (Gauss Pertubations) Prove thatPn

i=1i = ⁿ⁽ⁿ⁺¹⁾₂

I Of course, one could give an inductive proof. But here is a cool way to prove the same:

Prove that 1 +x+. . .+xⁿ= ^1−x_1−xⁿ⁺¹

(18)

Let us count

i=1i = ⁿ⁽ⁿ⁺¹⁾₂

I LetS =Pn i=1i

(19)

Let us count

i=1i = ⁿ⁽ⁿ⁺¹⁾₂

I LetS =Pn i=1i

I

S =1+ 2+. . .+ n

n+ (n−1)+. . .+ 1

2S =(n+ 1)+ (n+ 1)+. . .+ (n+ 1)

(20)

Let us count

i=1i = ⁿ⁽ⁿ⁺¹⁾₂

I LetS =Pn i=1i

I

S =1+ 2+. . .+ n

n+ (n−1)+. . .+ 1

2S =(n+ 1)+ (n+ 1)+. . .+ (n+ 1)

(21)

Let us count

i=1i = ⁿ⁽ⁿ⁺¹⁾₂

I Therefore,S= ⁿ⁽ⁿ⁺¹⁾₂ .

(22)

Let us count

i=1i = ⁿ⁽ⁿ⁺¹⁾₂

(23)

Let us count

i=1i = ⁿ⁽ⁿ⁺¹⁾₂

I LetS =Pn i=0xⁱ

(24)

Let us count

i=1i = ⁿ⁽ⁿ⁺¹⁾₂

I LetS =Pn i=0xⁱ

I

S =1+ x+. . .+ xⁿ (1)

xS =x+ x²+. . .+ xⁿ⁺¹ (2)

(25)

Let us count

i=1i = ⁿ⁽ⁿ⁺¹⁾₂

I LetS =Pn i=0xⁱ

I

S =1+ x+. . .+ xⁿ (1)

xS =x+ x²+. . .+ xⁿ⁺¹ (2)

(1)-(2) gives us: (1−x)S = 1−xⁿ⁺¹

I Therefore,S= ^1−x_1−xⁿ⁺¹.

(26)

Let us count

i=1i = ⁿ⁽ⁿ⁺¹⁾₂

(27)

Let us count

Slightly harder exercises:

Given n envelopes with addresses and n letters, how many are there to arrange them so that no letter goes to its correct address?

I The total number of ways of puttingndistinct letters intondistinct envelopes isn!

I We will see that the fraction ofn! which is addressed wrongly is almost 1/e, where e is the base of the natural logarithm.

A two-player game. I need any two of you to come to the board:

I I will draw 6 points on the board.

I Each round: player 1 draws a line using ared pen and then player 2 draws a line using abluepen.

I Who loses?: The first person to draw a triangle of his/her colour.

I Can this game ever end in a draw?

I Ramsey proved that a draw is impossible!

(28)

Let us count

(29)

Let us count

I The total number of ways of puttingndistinct letters intondistinct envelopes is

n!

(30)

Let us count

(31)

Let us count

I We will see that the fraction ofn! which is addressed wrongly is almost 1/e, where eis the base of the natural logarithm.

(32)

Let us count

(33)

Let us count

(34)

Let us count

I Each round: player 1 draws a line using aredpen and then player 2 draws a line using abluepen.

(35)

Let us count

(36)

Let us count

(37)

Let us count

(38)

Why and how to count?

On various occasions different quantities may become interesting. Some may be easy to count directly. Some may require more thought.

[CW] Count the number of arrangements of wrongly addresses letters for n = 4.

In this module, we will build some technqiues that will help in counting some quantities which are hard to count.

(39)

Why and how to count?

On various occasions different quantities may become interesting. Some may be easy to count directly. Some may require more thought.

[CW] Count the number of arrangements of wrongly addresses letters for n = 4.

In this module, we will build some technqiues that will help in counting some quantities which are hard to count.

(40)

Today

We will spend this lecture to learn counting one object in two different ways.

Often to count a certain object, we will count some totally different object!

(41)

Today

We will spend this lecture to learn counting one object in two different ways.

Often to count a certain object, we will count some totally different object!

(42)

An example of double counting

Lemma k ⁿ_k

=n ⁿ⁻¹_k−1

Proof.

Given n players, how many ways are there to pick a team of sizek and one leader among them?

Either you can choosek members of a team first and then pick one among them as a leader to get k ⁿ_k

Or you can first choose a leader and then choose the rest of the k−1 team members from the remaining n−1 players to getn ⁿ⁻¹_k−1

(43)

An example of double counting

Lemma k ⁿ_k

=n ⁿ⁻¹_k−1

Proof.

Recall ⁿ_k

= _k_!(n−k)!^n!

Givenn players, how many ways are there to pick a team of size k and one leader among them?

(44)

An example of double counting

Lemma k ⁿ_k

=n ⁿ⁻¹_k−1

Proof.

(45)

An example of double counting

Lemma k ⁿ_k

=n ⁿ⁻¹_k−1

Proof.

Either you can choosek members of a team first and then pick one among them as a leader

to getk ⁿ_k

(46)

An example of double counting

Lemma k ⁿ_k

=n ⁿ⁻¹_k−1

Proof.

Either you can choosek members of a team first in ⁿ_k

ways and then pick one among them as a leader

to getk ⁿ_k

(47)

An example of double counting

Lemma k ⁿ_k

=n ⁿ⁻¹_k−1

Proof.

ways and then pick one among them as a leader in k ways

to getk _kⁿ Or you can first choose a leader and then choose the rest of the k−1 team members from the remaining n−1 players to getn ⁿ⁻¹_k−1

(48)

An example of double counting

Lemma k ⁿ_k

=n ⁿ⁻¹_k−1

Proof.

ways and then pick one among them as a leader in k ways to getk _kⁿ Or you can first choose a leader and then choose the rest of the k−1 team members from the remaining n−1 players

to getn ⁿ⁻¹_k−1

(49)

An example of double counting

Lemma k ⁿ_k

=n ⁿ⁻¹_k−1

Proof.

ways and then pick one among them as a leader in k ways to getk _kⁿ

Or you can first choose a leader inn ways and then choose the rest of thek−1 team members from the remainingn−1 players

to get n _kⁿ⁻¹₋₁

(50)

An example of double counting

Lemma k ⁿ_k

=n ⁿ⁻¹_k−1

Proof.

Or you can first choose a leader inn ways and then choose the rest of thek−1 team members from the remainingn−1 players in ⁿ⁻¹_k−1 ways

to getn ⁿ⁻¹_k−1

(51)

An example of double counting

Lemma k ⁿ_k

=n ⁿ⁻¹_k−1

Proof.

Or you can first choose a leader inn ways and then choose the rest of thek−1 team members from the remainingn−1 players in ⁿ⁻¹_k−1 ways to get n ⁿ⁻¹_k−1

(52)

Another example of double counting

Lemma [CW] ⁿ⁺¹_k

= _k₋₁ⁿ + ⁿ_k

Proof.

Quantity to double count: Given a collection ofn apples and 1 mango, the number of ways of choosing a basket of k fruit.

Note that, LHS equals this quantity. For the RHS, note that

Either choose the mango in the basket and select k−1 apples fromn apples in _k−1ⁿ

ways.

Or leave out the mango from the basket and selectk apples from n apples in ⁿ_k

ways.

(53)

Another example of double counting

= _k₋₁ⁿ + ⁿ_k

Proof.

Note that, LHS equals this quantity.

For the RHS, note that

ways.

(54)

Another example of double counting

= _k₋₁ⁿ + ⁿ_k

Proof.

Note that, LHS equals this quantity.

For the RHS, note that

ways.

(55)

The number of handshakes

Lemma (The handshake lemma)

At a party with n people, the number of people who shake hands an odd number of times is even.

Proof.

Let us construct a graph with n people as vertices. We draw directed edges (u,v) and (v,u) ifu and v shake hands.

Let m_i be the number of times person i shakes hands. We will count the number of directed edges in the graph.

∴ 2X =Pn i=1mi.

This tells us that the sum of n numbers is even. Therefore, only even many of them can have odd value!

Take back message: Counting the same quantity the number of directed edges in two different ways can be helpful!

(56)

The number of handshakes

Proof.

∴ 2X =Pn i=1mi.

(57)

The number of handshakes

Proof.

[CW] Check that what we want to prove is the same as:

∴ 2X =Pn i=1mi.

(58)

The number of handshakes

Proof.

the number of vertices with odd degree is even.

Degree(v) := |{u |(u,v)∈E}|Let m_i be the number of times personi shakes hands. We will count the number of directed edges in the graph.

∴ 2X =P_n

i=1m_i.

(59)

The number of handshakes

Proof.

the number of vertices with odd degree is even.

Degree(v) := |{u |(u,v)∈E}|

Let m_i be the number of times personi shakes hands. We will count the number of directed edges in the graph.

∴ 2X =P_n

i=1m_i.

(60)

The number of handshakes

Proof.

Let mi be the number of times person i shakes hands. We will count the number of directed edges in the graph.

On the one hand this number is Pn i=1m_i.

On the other hand each handshake gives rise to two edges. So if X is the number of handshakes, then the number of edges is 2X.

∴ 2X =Pn i=1mi.

(61)

The number of handshakes

Proof.

Let mi be the number of times person i shakes hands. We will count the number of directed edges in the graph.

On the one hand this number is Pn i=1m_i.

On the other hand each handshake gives rise to two edges. So if X is the number of handshakes, then the number of edges is 2X.

∴ 2X =Pn i=1mi.

(62)

The number of handshakes

Proof.

∴ 2X =Pn i=1mi.

(63)

The number of handshakes

Proof.

∴ 2X =Pn i=1mi.

(64)

The number of handshakes

Proof.

∴ 2X =Pn i=1mi.

(65)

The number of handshakes

Proof.

∴ 2X =Pn i=1mi.

(66)

Counting the same quantity in different ways

Lemma

Cosnider a class of m students. Every day after class 3 students stay back to clean the classes. At the end of the course, they realise that each pair of students stayed back exactly once. For how many days did the course run?

Proof.

Say the course ran for n days.

[CW] In a class of mstudents, how many distinct pairs of students are there?

Let P be the total number of distinct pairs of students.

∴ P = ^m₂ .

On the other hand, each day 3 pairs of students stay back together. As there are n days, P = 3n.

∴n= ^m(m−1)₆ .

(67)

Counting the same quantity in different ways

Lemma

Proof.

∴ P = ^m₂ .

∴n= ^m(m−1)₆ .

(68)

Counting the same quantity in different ways

Lemma

Proof.

∴ P = ^m₂ .

∴n= ^m(m−1)₆ .

(69)

Counting the same quantity in different ways

Lemma

Proof.

∴ P = ^m₂ .

∴n= ^m(m−1)₆ .

(70)

Counting the same quantity in different ways

Lemma

Proof.

∴ P = ^m₂ .

∴n= ^m(m−1)₆ .

(71)

Counting the same quantity in different ways

Lemma

Proof.

∴ P = ^m₂ .

∴n= ^m(m−1)₆ .

(72)

Counting the same quantity in different ways

Lemma

Proof.

∴ P = ^m₂ .

∴n= ^m(m−1)₆ .