Combinations

The selection of a number of things taking some or all of them at a time are called combinations.

The number of ways of selecting r things out of n dissimilar things is denoted by C(n, r) or  ⁿC_r.

Example:

From a class of 32 students, 4 are to be chosen for a competition. In how many ways can this be done?

Suggested answer:

We are to select 4 students from 32. This selection can done in

Theorem:

The number of combinations of n dissimilar things, taken r at a time is

Proof:

C(n,r) is the required combination by definition. Each of these combinations consists of a group of r dissimilar things, which can be arranged among themselves in P(r,r) = r! ways. But the number of permutations of n different things taken r at a time is P(n,r).

Corollary 1:

C(n,r) = C(n,n-r)

Proof:

Corollary 2:

C(n,0) = C(n,n) = 1

Proof:

Corollary 3:

Proof:

If r = s, there is nothing to prove.

Now,

If r < s, then n - r > n - s, then the above equation becomes

Since both sides are products of (s-r), consecutive integers in

Similarly it can be proved that n = r + s if r > s.

Corollary 4:

Proof:

Prove the following statements

Proof:

Difference between a Permutation and a Combination

i. In a combination, only selection is made. In a permutation, not only a selection is made, but also there is an arrangement of a definite order.

ii. There is no order of selection in combinations. In permutation, order is a must.

iii. Usually (i.e., except in special cases or trivial cases), the number of permutations exceeds the number of combinations.