Combinatorics • Topic 9

Combinations

Combinations count the number of ways to choose items where order does not matter. This is the fundamental object of combinatorics.

Definition

Definition (Combination)

The number of ways to choose

k

distinct items from a set of

n

distinct items is denoted by

(k n)

(read "

n

choose

k

").

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

We start with permutations

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

. Since order doesn't matter, every set of

k

items has been counted

k!

times (once for each arrangement). We divide by

k!

to correct this.

(k n) = (n - k n)

Choosing

k

items to keep is the same as choosing

n - k

items to discard.

(k n) = (k - 1 n - 1) + (k n - 1)

Case 1: $x$ is included. We need to choose $k - 1$ more from the remaining $n - 1$ . ( $(k - 1 n - 1)$ )

Case 2: $x$ is excluded. We need to choose all $k$ from the remaining $n - 1$ . ( $(k n - 1)$ )

Exercise (Problem 1)

In a lottery, you must choose 6 numbers from 49. How many possible tickets are there?

Exercise (Problem 2)

How many ways can a committee of 3 men and 2 women be formed from a group of 10 men and 8 women?

Exercise (Problem 3)

Solve for

n

(2 n) = 55