Permutations and combinatorics
Permutations (order matters, more unique states) and combinatorics (order does not matter, less unique states) involve the tally and interpretation of repeated measurements.
In addition to considering if order matters (permutations) or does not (combinations), we also have to consider if repeated events are allowed. For example, [1,2,2,3] implies an experiment was done selecting numbers that get replaced from the original population.
| With replacement (allow duplicates) |
Without replacement (no duplicates) |
|
|---|---|---|
| $$n^k$$ | $$ n! $$ | |
| Select k PERMUTATIONS: order matters (many unique) |
$$n^k$$ | $$\frac{n!}{(n-k)!}$$ |
| Select k COMBINATIONS: Order does not matter (fewer unique) |
$$\left(\frac{k+n-1}{r}\right) = \frac{(k+n+1)!}{r!(n-1)!}$$ | $$\frac{n!}{k!(n-k)!}$$ "n-choose-k" |
In other words, one may think of the permutations as the number of distinct states of a system and the combinatorics as the equivalence relations between these states. A permutation is defined by a bijective mapping.
Links to related ideas
Combinations and permutations: step by step summary at Math is Fun.
Group action: It is said that the group acts on the space or structure. If a group acts on a structure, it also acts on everything that is built on the structure.
Twelve Fold Way Summary: John Cook's summary of Richard Stanley's Twelve Fold Way which describes the 12 domains of combinatorics and permutations. Also: 12 fold way table at NIST.
Gowers on Permutations: Mathematician Tim Gowers discussing the interpretation of Permutations. Comments on blog post by Terry Tao.
Permutations at Rosetta Code permutation generation of a set, written in many languages. Also: Permutations in OCaml by chess960.
Written by:
