Combinations

Combinations

A combination is an arrangement of objects without repetition where order is not important.
Note: The difference between a permutation and a combination is not whether there is repetition or not -- there must not be repetition with either, and if there is repetition, you can not use the formulas for permutations or combinations. The only difference in the definition of a permutation and a combination is whether order is important.
A combination of n objects, arranged in groups of size r, without repetition, and order being important is:

   nCr = C(n,r) = n! / ( (n-r)! * r! )

Another way to write a combination of n things, r at a time is using the binomial notation:
Example: Find all two-letter combinations of the letters "ABC"

   AB = BA   AC = CA   BC = CB

There are only three two-letter combinations.

Shortcut formula for finding a combination

Assuming that you start a n and count down to 1 in your factorials ...
C(n,r) = first r factors of n factorial divided by the last r factors of n factorial

Pascal's Triangle

Combinations are used in the binomial expansion theorem from algebra to give the coefficients of the expansion (a+b)^n. They also form a pattern known as Pascal's Triangle.

                           1
                         1   1
                       1   2   1
                     1   3   3   1
                   1   4   6   4   1
                 1   5  10   10  5   1
               1   6  15  20  15   6   1
             1   7  21  35  35  21   7   1

Each element in the table is the sum of the two elements directly above it. Each element is also a combination. The n value is the number of the row (start counting at zero) and the r value is the element in the row (start counting at zero). That would make the 20 in the next to last row C(6,3) -- it's in the row #6 (7^th row) and position #3 (4^th element).