# Counting Techniques

## Fundamental Principle of Counting

If event *E*_{1} can have *n*_{1} different outcomes, event *E*_{2} can have *n*_{2} different outcomes, ..., and event *E _{m}* can have

*n*different outcomes, then it follows that the number of possible outcomes in which composite events

_{m}*E*

_{1},

*E*

_{2}, ...,

*E*can have is

_{m}*n*

_{1}×

*n*

_{2}× ... ×

*n*

_{m}We call this *The Multiplication Principle*.

## Permutation

**Permutation** is the *ordered* arrangement of *n* different objects in *k* slots in a line.

The permutation of *n* objects taken *k* at a time is:

The permutation of *n* objects taken all at a time is

Note: $0! = 1$

The number of permutations of *n* objects taken all at a time in which *k*_{1} of the objects are alike, *k*_{2} are alike, *k*_{3} are alike, and so on...

**Cyclic Permutation**

The permutation of *n* objects in a circle is

## Combination

**Combination** is the number of *unordered* selections. The combination of *n* objects taken *k* at a time is:

Note: ${^n}C_n = {^n}C_0 = 1$

The number of combinations of *n* objects taken 1 at a time, 2 at a time, 3 at a time, and so on until *n* at a time is

## Partitioning

The number of ways of partitioning *n* objects into *m* groups with *k*_{1} objects in the first group, *k*_{2} objects in the second group, and so on.

If *k*_{1} + *k*_{2} + *k*_{3} + ... + *k _{m}* =

*n*:

If *k*_{1} + *k*_{2} + *k*_{3} + ... + *k _{m}* <

*n*: