Combinatorics is an area of mathematics primarily concerned with counting, as well as properties of finite structures (such as graphs).

For the purposes of STAT410, we will only be addressing simple counting in combinatorics, for use in probability functions later.

Permutations and Combinations

A permutation of a set of $n$ elements is a rearrangement of the elements in a specific order. A k-permutation is an arrangement of $k$ elements from the $n$ -element set.

By definition of a set, elements must be distinct.

The total number of $k$ -permutations of an $n$ -element set is given by the formula

P (n, k) = \frac{n !}{( n - k )!} = n (n - 1) \dots (n - k + 1)

Example: Basic Permutations

Problem: How many ways can we seat 10 people in a row?
Solution: We are performing a $k$ -permutation where $k = 10$ on our set of 10 people.
$P (10, 10) = 10!$

The total ways to create a $k$ -size subset from an $n$ -element set, known as a combination, is given by

C (n, k) = (k n) = \frac{n !}{k ! ( n - k )!} = \frac{P ( n , k )}{k !}

Note that by definition of a subset, there is no element order.

Theorem: Binomial Theorem

For any positive integer $n$ ,
$(x + y)^{n} = k = 0 \sum n (k n) x^{k} y^{n - k}$

Proof

We begin with $(x + y)^{n}$ .
$(x + y)^{n} = (x + y) (x + y) \dots (x + y) = c_{1} x^{n} + c_{2} x^{1} y^{n - 1} + c_{3} x^{2} y^{n - 2} + \dots$
The product of the $n$ terms means that when we expand the binomial expression, we are “choosing” either the $x$ or $y$ term to multiply.

Thus, to find the coefficient of $x^{k} y^{n - k}$ , the product of the $n$ terms requires that when we multiply each binomial together, we multiply (“choose”) the $x$ -term $k$ times. After this, the rest of the product’s terms are forced to be $y$ (and there’s only one way to pick $y$ ).

This gives us $C (n, k)$ different ways to obtain the coefficient.
$C (n, k) x^{k} y^{n - k} = (k n) x^{k} y^{n - k}$

We give some more counting examples below.

Example: Basic Counting

There are 10 cows, 9 pigs, 8 horses. The

Total ways to pick 5 animals at once:

Because order does not matter, we are simply choosing 5 animals from our total of 27.
$C (27, 5)$

Total ways to get 5 animals where we get 3 cows, 2 pigs or 2 cows, 3 pigs:

We choose 3 cows and 2 pigs from our animal total to obtain
$(3 10) (2 9)$
We choose 2 cows and 3 pigs from our animal total to obtain
$(2 10) (3 9)$

Because these two groups of outcomes are distinct from one another, we add them together to find our total.
$(3 10) (2 9) + (2 10) (3 9)$

Example: Basic Counting (2)

There are 10 kids and 3 types of candy. How many ways can we distribute this candy such that exactly 3 children get type 1, 2 children get type 2, and 5 children get type 3?

We can think of our children as the distinct elements, and choose who gets what candy. So, we first select 3 children to get type 1, 2 children to get type 2, and 5 children to get type 3.
$(3 10) (2 7) (5 5)$
We can think about this another way as well. Say we have 10 children numbered 1-10, and we assign each a candy type of 1, 2, or 3 (for the total we’re looking for). We want to find the number of different ways we can order these candy types!

However, because there are repeated elements, we need to count some cases as one. We do this by dividing by the total number of possible cases that we want to count as one case.
$\frac{P ( 10 , 10 )}{3 ! \cdot 2 ! \cdot 3 !}$
In fact, this is called the multinomial coefficient, described below.

Theorem: Multinomial Coefficient (Permutations with Repetition)

Suppose there are $k$ distinct objects, and object $i$ occurs $a_{i}$ times.

Assume $a_{1} + a_{2} + \dots + a_{k} = n$ .

Then, the total number of rearrangements of the $n$ objects is
$\frac{n !}{a _{1} ! \cdot a _{2} ! \dots a _{k} !} = (a _{1} a _{2} \dots a _{k} n)$
called the multinomial coefficient.

We can use the multinomial coefficient to generalize our previous binomial theorem.

Theorem: Multinomial Theorem

$(x_{1} + x_{2} + \dots + x_{k})^{n} = a_{1} + a_{2} + \dots + a_{k} = n \sum (a _{1} a _{2} \dots a _{k} n) x_{1}^{a_{1}} x_{2}^{a_{2}} \dots x_{k}^{a_{k}}$

Example: Multinomial Coefficient

Find the coefficient of $x_{1}^{3} x_{2} x_{4}^{2}$ in $(x_{1} + x_{2} + x_{3} + x_{4})^{6}$ .

To find the coefficient, we need to find the number of times we obtain $x_{1}^{3} x_{2} x_{4}^{2}$ in the product.

In other words, if we select 6 positions, where each represents the $x_{i}$ term we “selected” to multiply out, then we want to choose 3 positions to have $x_{1}$ , 1 position to have $x_{2}$ , and 2 positions to have $x_{4}$ .

This comes out to be
$C (6, 3) * C (3, 1) * C (2, 2) = (3 1 2 6)$

Example: Permutations and Combinations

How many arrangements of $AAA B B C C$ are there?

Suppose we have 7 positions. We want to choose 3 to fill with $A$ , 2 to fill with $B$ , and 2 to fill with $C$ . This comes out to be
$C (7, 3) * C (4, 2) * C (2, 2)$

What if the $B$ ‘s must all be together, but none of the $C$ ‘s can be together?

If the $B$ ‘s must be together, we block them together as one term $X = B B$ to find arrangements of $AAA X C C$ . Then, to find permutations where the $C$ ‘s are not together, we first will find the number of arrangements of $AAA X$ (without the $C$ ‘s’).
$C (4, 3)$
Then, between every term $AAA X$ , we can place $C$ ‘s suchthat they are not next to each other. This comes out to 5 positions, and we have 2 $C$ ‘s to place to give us
$C (5, 2)$
different ways to place our $C$ ‘s. Thus, our final result is
$C (4, 3) * C (5, 2)$

Quartz 5

Explorer

Combinatorics

Permutations and Combinations

Graph View

Backlinks