Discrete Mathematics - Permutations and Combinations

Permutations and Combinations

• Fundamental principle of counting

• Factorial n

• (n!) Permutations and combinations

• Derivation of formulae and their connections

• Simple applications.

SUMMARY

1. Fundamental principle of counting If an event can occur in m different ways, following which another event can occur in n different ways, then the total number of occurrence of the events in the given order is m × n.

2. The number of permutations of n different things taken r at a time, where repetition is not allowed, is denoted by nPr and is given by nPr = n! / (n - r)!, where 0 ≤ r ≤ n.

3. n! = 1 × 2 × 3 × ...×n

4. n! = n × (n – 1) !

5. The number of permutations of n different things, taken r at a time, where repeatition is allowed, is nr .

6. The number of permutations of n objects taken all at a time, where p1 objects are of first kind, p2 objects are of the second kind, ..., pk objects are of the kth kind and rest, if any, are all different is n! / p1! p2! ...pk! .

7. The number of combinations of n different things taken r at a time, denoted by nCr , is given by nCr = n! / r! (n - r)!, 0 ≤ r ≤ n.

8. A permutation is an arrangement in a definite order of a number of objects taken some or all at a time.

9. Factorial notation The notation n! represents the product of first n natural numbers.