Basic Combinatorics

Table of contents

Permutation

A permutation is an arrangement of objects in a specific order.

If repetition is not allowed, then the number of permutations of $n$ objects taken $r$ at a time is

$$ _nP_r = \frac{n!}{(n-r)!} $$

If repetition is allowed, then the number of permutations of $n$ objects taken $r$ at a time is $n^r$.

A combination is a selection of objects where order does not matter.

If repetition is not allowed, then the number of combinations of $n$ objects taken $r$ at a time is

$$ _nC_r = \frac{n!}{r!(n-r)!} $$

If repetition is allowed, then the number of combinations of $n$ objects taken $r$ at a time is

$$ _{r+n-1}C_r = \frac{(r+n-1)!}{r!(n-1)!} $$