38.2. COMBINATIONS 771

38.2 CombinationsThe fundamental problem is to find the number of ways of selecting a subset of k ≤ nelements from a set having n elements. For example, consider the set S = {1,2,3} . Howmany subsets having two elements are there? In this case, you can simply list them. Herethey are

{1,2} ,{1,3} ,{2,3}

This seems easy enough, but what if you had a set of 52 things like a deck of cards and youwanted the number of ways of picking a set of 5 things from it. Then it would be a littleharder. Here is some standard notation.

Definition 38.2.1 Let 0 ≤ k ≤ n. Then

(nk

)denotes the number of subsets of a set

having n elements which have k elements.

Here are some obvious assertions.(n0

)=

(nn

)= 1,

(n1

)= n (38.1)

The first says there is one subset which has no elements in it. Of course it is the emptyset. The next says there is one subset of a set having n things which has n things in it. Ofcourse, this would be the whole set itself. The last says there are n subsets which have a

single element of the set in them. Now to get a formula for

(nk

), here is a lemma.

Lemma 38.2.2 Let n be a positive integer and let 1≤ k ≤ n. Then(n+1

k

)=

(nk

)+

(n

k−1

)

Proof: Letting 1≤ k ≤ n, suppose your set of n+1 things is

{a1, · · · ,an,an+1}

Here ai denotes the ith element of the set and this is just a list of the elements of the set.Then there are two ways to select a set of k things from this set depending on whether an+1

is in the set of k things. If it is, there are exactly

(n

k−1

)ways to obtain such a set of

k things because it must be the number of ways of selecting the remaining k−1 elementsfrom the first n elements in the set. The other case is where all k elements are selected from

the first n elements of the set. By definition, there are

(nk

)ways to do this. Thus

(n+1

k

)=

(n

k−1

)+

(nk

)■