## Week 19 - Combinatorics A

## Lesson 10.1 The basics of Combinatorics

- Combinatorics
- The math topic that studies "finite" countable discrete structures: collections or arrangements of objects.
- Involves counting objects and studying the mathematical properties of different arrangement of objects.
- Applications include programming, physics, economics and other fields like prob theory.

## Lesson 10.103 The basics of counting

- Product Rule
- To determine the number of different possible outcomes in a complex process, we can break the problem into a sequence of two independent tasks:
- if there are $n$ ways of doing the first task
- for each of these ways of doing the first task, there are $m$ ways of doing the 2nd task.
- then there are n * m different ways of doing the whole process.

- Example
- Problem
- Consider a restaurant offering a combination meal where a person can order from each of the following categories:
- 2 salads
- 3 main dishes
- 4 side dishes
- 3 desserts

- How many combinations meals are there to choose from?

- Consider a restaurant offering a combination meal where a person can order from each of the following categories:
- Solution
- The problem can be broken down into 4 independent events:
- selecting a salad
- selecting a main dish
- selecting a side dish
- selecting a dessert

- For each event, the number of available options is:
- 2 for the first event
- 3 for the 2nd event
- 4 for the third event
- 3 for the fourth event

- Thus, there are 2 * 3 * 4 * 3 = 72 combination meals.

- The problem can be broken down into 4 independent events:

- Problem
- Product rule in terms of sets
- Let A be the set of ways to do the first task and B the set of ways to do 2nd task.
- If A and B are disjoint, then:
- The number ways to do both task 1 and 2 can be represented as: $|AxB| = |A| \cdot |B|$
- The cardinality of the cross product of A and B.

- In other words: the num elements in the Cartesian product of these sets is the product of number of elements in each set.

- The number ways to do both task 1 and 2 can be represented as: $|AxB| = |A| \cdot |B|$

- To determine the number of different possible outcomes in a complex process, we can break the problem into a sequence of two independent tasks:
- Addition Rule
- Suppose a task 1 can be done n ways and a task 2 can be done in m ways.
- Assume that both tasks are independent, that is, performing task 1 doesn't mean performing task 2 and vice versa.
- In this case, the number of ways of executing task 1 or task 2 is equal to n + m.
- Example
- The computing department must choose either a student or a member of academic staff as a representative for university committee.
- How many ways of choose this representative are there if there are 10 academic staff and 77 math students, and no one is both a member of academic staff and a student?

- Solution
- By the addition rule, there are 10 + 77 ways of choosing this representative.

- The sum rule in terms of sets
- Let A be the set of ways to do task 1 and B the set of ways to do task 2, where A and B are disjoint sets.
- The sum rule can be phrased in terms of sets:
- $|A \cup B| = |A| + |B|$ as long as $A$ and $B$ are disjoint sets.

- The sum rule can be phrased in terms of sets:

- Let A be the set of ways to do task 1 and B the set of ways to do task 2, where A and B are disjoint sets.
- Combining the sum and product rules
- We can combine the sum and product rules to solve more complex problems.
- Example:
- Suppose a letter in a programming language can be either a single letter or a letter followed by 2 digits.
- What is the number of possible labels?

- Suppose a letter in a programming language can be either a single letter or a letter followed by 2 digits.
- Solution:
- The number of labels with one letter only is 26
- Using the product rule the number of labels with a letter folowed by 2 digits is 26 x 10 x10
- Using the sum rule the total number of labels is 26 + 26>10.10 = 2,626.

- Subtraction Rule
- Suppose a task can be done either in one of $n_1$ ways or in one of $n_2$ ways.
- Then the total number of ways to do the task is $n_1 + n_2$ minus the number of ways common to the two different ways.
- Also known as the principle of inclusion-exclusion.
- $|A \cup B| = |A| + |B| - |A \cap B|$

- Example
- How many binary bit strings of length eigth either start with a 1 bit or end with the 2 bits 00?
- Solution:
- Number of bit strings of length eight that start with a 1 bit: $2.2.2.2.2.2.2 = 2^7 = 128$
- Number of bit strings of length eight that end with the 2 bits 00: $2^6 = 64$
- Number of bit trings of length 8 that start with a 1 bit and end with bits 00 is 2^5 = 32
- Using substraction rule:
- the number of bit strings either starting with a 1 or ending with 00 is 128 + 64 - 32 = 160.

- Division Rule
- Suppose a tak can be done using a procedure that can be carried out in n ways, for every way w, exactly d of the n ways correspond to w.
- Then this task can be done $n/d$ ways

- In terms of sets: if the finite set A is the union of n pair-wise disjoint subsets each with d elements, the $n = |A| / d$
- In terms of functions: if f is a function from A to B, where both are finite sts, and for every value y \in B there are exactly d values x \in A such that $f(x) = y$, then $|B| = |A|/d$
- Example:
- In how many ways can we seat 4 people around a table, where 2 seating arrangements are considered the same when each person has the same left and right neighbour
- Solution:
- Let's first number the seats around the table from 1 to 4 proceeeding clockwise:
- There are 4 ways to select the person for seat 1, three for seat 2, two for seat 3 and one for seat 4
- Thus there are $4.3.2.1 = 24$ ways to order the four people.
- Since 2 seating arrangments are the same when each person has the same left and right neighbour, for every choice for seat 1, we get the same seating.
- Therefore, by using the division rule, there are $24/4 = 6$ different seating arrangements.

- Let's first number the seats around the table from 1 to 4 proceeeding clockwise:

- Suppose a tak can be done using a procedure that can be carried out in n ways, for every way w, exactly d of the n ways correspond to w.

## Lesson 10.105 The pigeonhole principal

- Pigeonhole principal
- One of simplest and most useful ideas in maths
- Let K be a positive integer:
- If k is a positive integer and k+1 objects are placed into k boxes, then at least one box contains 2 or more objects.
- Proof by contrapositive:
- Suppose none of the k boxes has more than 1 object.
- The total number of objects would be at most k.
- Which contradicts the statement that we have k+1 objects.

- Example:
- If a flock of 10 pigeons roosts in a set of 9 pigeonholes, 1 of the pigeon holes must have more than 1 pigeon.

- Exercise
- Prove that a function f from a set with k + 1 elements to a set with k elements is not a one-to-one.
- Solution: We can prove this using the peigonhole principle:
- Create a $box_y$, for each element y in the co-domain of f
- Put all elements x from the domain in the box for y such that f(x) = y
- Because there are k + 1 elements and only k boxes, at least one box has two or more elements.
- Therefore, f is not one-to-one.

- The generalised pigeonhole principle
- If N objects are placed into k boxes, then there is at least one box containing at least ceil(N/k) objects, where ceil(x) is called the ceiling function, which represents the round-up value of x
- Let's prove it by contrapositive:
- Suppose none of the boxes contains more than $\lceil N/k \rceil - 1$ objects.
- Then the total number of objects is at most: $k(\lceil\frac{N}{k}\rceil - 1) < k((\frac{N}{k} + 1) - 1) = N$
- This is a contradiction because there is a total of N objects.

- Example:
- How many cards must be selected from a standard deck of 52 cards to guarantee that at least four cards of the same suit are chosen?
- Solution:
- Assume 4 boxes, one for each suit.
- Using the generalised pigeonhole principle, at least one box contains at least $\lceil \frac{N}{4}\rceil$, where N is the number of cards selected.
- At least 4 cards of one suit are selected if $\lceil \frac{N}{4} \rceil \geq 4$
- The smallest integer N such that $\lceil \frac{N}{4} \rceil \geq 4$ is equal to 13.

## Video: 10.107 Permutations and combinations

- Many counting problems can be solved by finding the number of ways to arrange a specified number of distinct elements of a set of particular size, where the order of this element matters, and in some cases doesn't.
- This lecture discusses permutations and combinations, which are used to solve this counting problem.
- Permutation
- A permutation of a set of distinct objects is an
**ordered arrangement**of these objects. - An ordered arrangement of r elements of a set is called an r-permutation.
- The number of r-permutations of a set with n elements is denoted by $P(n,r)$
- Example:
- Let $S = \{1, 2, 3\}$
- The ordered arrangement 3,1,2 is a 3-permutation of S.
- The ordered arrangement 3,2 is a 2-permutation of S
- The 2-permutations of S = {1, 2, 3} are 1,2; 1,3; 2,1; 2,3; 3,1 and 3,2
- Hence, P(3,2) = 6

- Number of permutations
- If n is a positive integer and r is an integer with $r \leq n$, then there are $P(n, r) = n(n - 1)(n - 2) ... (n - (r-1))$ r-permutations of a set with n distinct elements.
- We can formulate this as:
- $P(n, r) = \frac{n!}{(n - r)!}$

- Proof:
- By product rule:
- there are n different ways for choosing the 1st element.
- n-1 ways for choosing the 2nd element.
- n -3 ways for choosing the 3rd element, etc.
- there are $(n - (r - 1))$ ways to choose the last element.
- hence, $P(n, r) = n(n - 1)(n - 2) ... (n - (r - 1))$
- $P(n, 0) = 1$, since there is only one way to order zero.

- Example
- How many possible ways are there of selecting a first prize winner, a 2nd price winner and third-prize winner from 50 different people?
- Solution:
- P(50, 3) = 50 * 49 * 48 = 117,600

- By product rule:

- A permutation of a set of distinct objects is an
- Combination
- An r-combination of elements of a set is an unordered selection of r elements from the set.
- An r-combination is a subset of the set with r elements.
- The number of r-combinations of a set with n distinct elements is denoted by $C(n, r) = \binom{n}{r}$
- The notation used is called
**binomical coefficient**

- Number of combinations
- The number of r-combinations of a set with n distinct elements can be formulated as:
- $C(n, r) = \frac{n!}{(n-r)!r!} = \frac{P(n, r)}{r!}$

- $C(n, r)$ can be referred to as n choose r
- It follows that $C(n, r) = C(n, n - r)$
- Example
- How many ways are there of selecting six players from a 20-member tennis team to make a trip to an intenational competition?
- $C(20, 6) = \frac{20!}{6!14!} = \frac{20 . 19 . 18 . 17 . 16 . 15}{6 . 5 . 4 . 3 . 2} = 38,760$

- The number of r-combinations of a set with n distinct elements can be formulated as: