combinatorics.md

   1 # Combinatorics
   2
   3 Combinatorics is an area of [math](math.md) that's basically concerned with counting possibilities. As such it is very related to [probability theory](probability.md) (as probability is typically defined in terms of ratios of possible outcomes). It explores things such as [permutations](permutation.md) and [combinations](combination.md), i.e. question such as how many ways are there to order *N* objects or how many ways are there to choose *k* objects from a set of *N* objects.
   4
   5 The two basic quantities we define in combinatorics are **[permutations](permutation.md)** and **[combinations](combination.md)**.
   6
   7 Permutation (in a simple form) of a [set](set.md) of objects (lets say A, B and C) is one possible ordering of such set (i.e. ABC, ACB, BAC etc.). I.e. here by permutation of a number *n*, which we'll write as *P(n)*, we mean the number of possible orderings of a set of size *n*. So for example *P(1) = 1* because there is only one way to order a set containing one item. Similarly *P(3) = 6* because there are six ways to order a set of three objects (ABC, ACB, BAC, BCA, CAB, CBA). *P(n)* is computed very simply, it is [factorial](factorial.md) of *n*, i.e. *P(n) = n!*.
   8
   9 Combination (without repetition) of a set of objects says in how many ways we can select given number of objects from that set (e.g. if there are 4 shirts in a drawer and we want to choose 2, how many possibilities are there?). I.e. given a set of certain size a combination tells us the number of possible subsets of certain size. I.e. there are two parameters of a combination, one is the size of the set, *n*, and the other is the number of items (the size of the subset) we want to select from that set, *k*. This is written as *nCk*, *C(n,k)* or
  10
  11 ```
  12  / n \
  13 |     |
  14  \ k /
  15 ```
  16
  17 A combination is computed as *C(n,k) = n! / (k! * (n - k)!)*. E.g. having a drawer with 4 shirts (A, B, C and D) and wanting to select 2 gives us *C(4,2) = 4! / (2! * (4 - 2)!) = 6* possibilities (AB, AC, AD, BC, BD, CD).
  18
  19 Furthermore we can define combinations with repetitions in which we allow ourselves to select the same item from the set more than once (note that the selection order still doesn't matter). I.e. while combinations without repetition give us the number of possible subsets, a combinations WITH repetitions gives us the number of possible [multisubsets](multiset.md) of a given set. Combinations with repetition is computed as *Cr(n,k) = C(n + k - 1,k)*. E.g. having a drawer with 4 shirts and wanting to select 2 WITH the possibility to choose one shirt multiple times gives us *Cr(4,2) = C(5,2) = 5! / (2! * (5 - 2)!) = 10* possibilities (AA, AB, AC, AD, BB, BC, BD, CC, CD, DD).
  20
  21 Furthermore if we take combinations and say that order matters, we get generalized permutations that also take two parameters, *n* and *k*, and there are two kinds: without and with repetitions. I.e. permutations without repetitions tell us in how many ways we can choose *k* items from *n* items when ORDER MATTERS, and is computed as *P(n,k) = n!/(n - k)!* (e.g. *P(4,2) = 4!/(4 - 2)! = 12*, AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC). Permutations with repetitions tell us the same thing but we are allowed to select the same thing multiple times, it is computed as *Pr(n,k) = n^k* (e.g. *P(4,2) = 4^2 = 16*, AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC, CD, DA, DB, DC, DD).
  22
  23 To sum up:
  24
  25 |quantity                |order matters?|repetition allowed?|formula                      |
  26 |------------------------|--------------|-------------------|-----------------------------|
  27 |permutation (simple)    | yes          |                   |P(n) = n!                    |
  28 |permutation without rep.| yes          | no                |P(n,k) = n!/(n - k)!         |
  29 |permutation with rep.   | yes          | yes               |Pr(n,k) = n^k                |
  30 |combination without rep.| no           | no                |C(n,k) = n! / (k! * (n - k)!)|
  31 |combination with rep.   | no           | yes               |Cr(n,k) = C(n + k - 1,k)     |
  32
  33 Here is an example of applying all the measures to a three item set ABC (note that selecting nothing from a set counts as 1 possibility, NOT 0):
  34
  35 |quantity|possibilities (for set ABC)             |count                 |
  36 |--------|----------------------------------------|----------------------|
  37 |P(3)    |ABC ACB BAC BCA CAB CBA                 | 3! = 6               |
  38 |P(3,0)  |                                        | 3!/(3 - 0)! = 1      |
  39 |P(3,1)  |A B C                                   | 3!/(3 - 1)! = 3      |
  40 |P(3,2)  |AB AC BA BC CA CB                       | 3!/(3 - 2)! = 6      |
  41 |P(3,3)  |ABC ACB BAC BCA CAB CBA                 | 3!/(3 - 3)! = 6      |
  42 |Pr(3,0) |                                        | 3^0 = 1              |
  43 |Pr(3,1) |A B C                                   | 3^1 = 3              |
  44 |Pr(3,2) |AA AB AC BA BB BC CA CB CC              | 3^2 = 9              |
  45 |Pr(3,3) |AAA AAB AAC ABA ABB ABC ACA ACB ACC ... | 3^3 = 27             |
  46 |C(3,0)  |                                        |3!/(0! * (3 - 0)!) = 1|
  47 |C(3,1)  |A B C                                   |3!/(1! * (3 - 1)!) = 3|
  48 |C(3,2)  |AB AC BC                                |3!/(2! * (3 - 2)!) = 3|
  49 |C(3,3)  |ABC                                     |3!/(3! * (3 - 3)!) = 1|
  50 |Cr(3,0) |                                        | C(3 + 0 - 1,0) = 1   |
  51 |Cr(3,1) |A B C                                   | C(3 + 1 - 1,1) = 3   |
  52 |Cr(3,2) |AA AB AC BB BC CC                       | C(3 + 2 - 1,2) = 6   |
  53 |Cr(3,3) |AAA AAB AAC ABB ABC ACC BBB BBC BCC CCC | C(3 + 3 - 1,3) = 10  |