## Saturday, September 6, 2008

### Combinations - July- Dec Revision

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 nCr.

nCr 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

nCr = n!/(n-r)!r!

Results from the theorem

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

nCn =1

nC0 = 1

nCr = nPr/r!

Properties of nCr and C(n,r)

1. nCr = nCn-r

Note: If x=y = n

nCx = nCy

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

nCr + nCr-1 = n+1Cr

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

4. If 1≤ r≤n, then

n.n-1Cr-1 = (n-r+1)nCr-1

5. nCx = nCy implies x+y = n

6. If n is even, then the greatest value of nCr [0≤ r≤n] is nCn/2.

7. If n is odd, then the greatest value of nCr [0≤ r≤n] is nC(n+1)/2 or nC(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