Revision Points - Permutations and Combinations-4

Each of the different selections made by taking some or all of a number of objects, irrespective of their arrangement is called a combination.


Difference between Combinations and Permutations

In a combination, the ordering of the selected objects is immaterial whereas in a permutation, the ordering is essential. For example AB and BA are same as combinations, but different as permutations.

Associate the word selection for combinations and arrangement for permuations.


Notation

The number of all combinations of n objects, taken r at a time is denoted by C(n,r) or ⁿC_r.

ⁿC_r is defined when n and r are non-negative numbers.

Theorem

The number of all combinations of n distinct objects, taken r at a time is given by

ⁿC_r = n!/(n-r)!r!

Results from the theorem

ⁿC_r = [n(n-1)(n-2)...(n-r+1)]/(1.2.3...r)

ⁿC_n =1

ⁿC₀ = 1


ⁿC_r = ⁿP_r/r!


Properties of ⁿC_r and C(n,r)

1. ⁿC_r = ⁿC_n-r

Note: If x=y = n

ⁿC_x = ⁿC_y

2. Let n and r be non-negative integers such that r≤n. Then

ⁿC_r + ⁿC_r-1 = ⁿ⁺¹C_r

3. Let n and r be non-negative integers such that 1≤ r≤n. Then
ⁿC_r = (n/r) ^n-1C_r-1

4. If 1≤ r≤n, then

n.^n-1C_r-1 = (n-r+1)ⁿC_r-1

5. ⁿC_x = ⁿC_y implies x+y = n

6. If n is even, then the greatest value of ⁿC_r [0≤ r≤n] is ⁿC_n/2.

7. If n is odd, then the greatest value of ⁿC_r [0≤ r≤n] is ⁿC_(n+1)/2 or ⁿC_(n-1)/2.



Selection of one or more items

Selection from different items

The number of ways of selecting one or more items from a group of n distinct items is 2ⁿ - 1.

Selection from identical items

1. The number of ways of selecting r items out of n identical items is 1.
2. The total number of ways of selecting zero or more i.e. at least one item from a group of n identical items is (n+1).
3. The total number of selections of some or all out of p+q+r items where p are alike of one kind, q are alike of second kind, and rest are alike of third kind is {(p+1)(q+1)(r+1)}-1.

Selection of items from a group containing both identical and different items

1. the total number of ways of selecting one or more items from p identical items of one kind; q identical items of second kind, r identical items of third kind and n different items is

[(p+1)(q+1)(r+1) 2ⁿ]-1


Join Orkut community

Join Orkut community IIT-JEE-Academy for interaction regarding various issues and doubts
http://www.orkut.co.in/Community.aspx?cmm=39291603