COMBINATORICS

By: JAGNYASWINI KATUAL

INSTITUTE OF MATHEMATICS

AND APPLICATION

1

Combinatorics

• Count the number of ways to put things together into various combinations.

e.g. If a password is 6-8 letters and/or digits, how many passwords can there be?

• Two main rules:
• Sum rule
• Product rule

2

Sum Rule

• Let us consider two tasks:
• m is the number of ways to do task 1
• n is the number of ways to do task 2
• Tasks are independent of each other, i.e.,
• Performing task 1 does not accomplish task 2 and vice versa.
• Sum rule: If one problem can be solved in a sequence of two steps of which first step can be solved in m ways and the second step can be solved in n ways, then the total number of ways for solving the problems is m + n ways.

3

Product Rule

• Let us consider two tasks:
• m is the number of ways to do task 1
• n is the number of ways to do task 2
• Tasks are independent of each other, i.e.,
• Performing task 1does not accomplish task 2 and vice versa.
• Product rule: If one problem can be solved in a sequence of two steps of which first step can be solved in m ways and the second step can be solved in n ways, after solving the first step then the total number of ways for solving the problems is mn ways.

4

Inclusion-Exclusion Principle�(relates to the “sum rule”)

• Suppose that k≤m of the ways of doing task 1 also simultaneously accomplishes task 2. (And thus are also ways of doing task 2.)
• Then the number of ways to accomplish “Do either task 1 or task 2” is m+n−k.

5

Pigeonhole Principle

• If k+1 objects are assigned to k places, then at least 1 place must be assigned ≥2 objects.
• In terms of the assignment function:

If f:A→B and |A|≥|B|+1, then some element of B has ≥2 pre-images under f.

i.e., f is not one-to-one.

6

Generalized Pigeonhole Principle

• If N≥k+1 objects are assigned to k places, then at least one place must be assigned at least ⎡N/k⎤ objects.
• e.g., there are N=280 students in this class. There are k=52 weeks in the year.
• Therefore, there must be at least 1 week during which at least ⎡280/52⎤= ⎡5.38⎤=6 students in the class have a birthday.

7

Proof of G.P.P.

• By contradiction. Suppose every place has < ⎡N/k⎤ objects, thus ≤ ⎡N/k⎤−1.
• Then the total number of objects is at most

​

​

• So, there are less than N objects, which contradicts our assumption of N objects!

8

G.P.P. Example

• Given: There are 280 students in the class. Without knowing anybody’s birthday, what is the largest value of n for which we can prove that at least n students must have been born in the same month?
• Answer:

9

⎡280/12⎤ = ⎡23.3⎤ = 24

Permutations

• A permutation of a set S of objects is an ordered arrangement of the elements of S where each element appears only once:

e.g., 1 2 3, 2 1 3, 3 1 2

• An ordered arrangement of r distinct elements of S is called an r-permutation.
• The number of r-permutations of a set S with n=|S| elements is

P(n,r) = n(n−1)…(n−r+1) = n!/(n−r)!

10

Combinations

• The number of ways of choosing r elements from S (order does not matter).

S={1,2,3}

e.g., 1 2 , 1 3, 2 3

• The number of r-combinations C(n,r) of a set with n=|S| elements is

​

​

11

Combinations vs Permutations

• Essentially unordered permutations …

​

​

​

​

​

• Note that C(n,r) = C(n, n−r)

12

13

THANK YOU