Combinatorics
Combinatorics is an area of [1]math that's basically concerned with
counting possibilities. As such it is very related to [2]probability
theory (as probability is typically defined in terms of ratios of possible
outcomes). It explores things such as [3]permutations and [4]combinations,
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.
The two basic quantities we define in combinatorics are [5]permutations
and [6]combinations.
Permutation (in a simple form) of a [7]set 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 [8]factorial of n, i.e. P(n) = n!.
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
/ n \
| |
\ k /
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).
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 [9]multisubsets 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).
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).
To sum up:
quantity order matters? repetition allowed? formula
permutation (simple) yes P(n) = n!
permutation without yes no P(n,k) = n!/(n -
rep. k)!
permutation with rep. yes yes Pr(n,k) = n^k
combination without no no C(n,k) = n! / (k!
rep. * (n - k)!)
combination with rep. no yes Cr(n,k) = C(n + k
- 1,k)
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):
quantity possibilities (for set ABC) count
P(3) ABC ACB BAC BCA CAB CBA 3! = 6
P(3,0) 3!/(3 - 0)! = 1
P(3,1) A B C 3!/(3 - 1)! = 3
P(3,2) AB AC BA BC CA CB 3!/(3 - 2)! = 6
P(3,3) ABC ACB BAC BCA CAB CBA 3!/(3 - 3)! = 6
Pr(3,0) 3^0 = 1
Pr(3,1) A B C 3^1 = 3
Pr(3,2) AA AB AC BA BB BC CA CB CC 3^2 = 9
Pr(3,3) AAA AAB AAC ABA ABB ABC ACA ACB ACC ... 3^3 = 27
C(3,0) 3!/(0! * (3 - 0)!) = 1
C(3,1) A B C 3!/(1! * (3 - 1)!) = 3
C(3,2) AB AC BC 3!/(2! * (3 - 2)!) = 3
C(3,3) ABC 3!/(3! * (3 - 3)!) = 1
Cr(3,0) C(3 + 0 - 1,0) = 1
Cr(3,1) A B C C(3 + 1 - 1,1) = 3
Cr(3,2) AA AB AC BB BC CC C(3 + 2 - 1,2) = 6
Cr(3,3) AAA AAB AAC ABB ABC ACC BBB BBC BCC CCC C(3 + 3 - 1,3) = 10
Links:
1. math.md
2. probability.md
3. permutation.md
4. combination.md
5. permutation.md
6. combination.md
7. set.md
8. factorial.md
9. multiset.md