Permutations and Combinations


   
 
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  nCr.
 
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.
 
  
     
   
Get unlimited online Math tutoring, Algebra tutoring, Trigonometry Help and Tutoring in English, Physics, Chemistry, Biology, Geometry and all other subjects at $99.99 per month!