---
# System prepended metadata

title: Permutations and combinatorics
tags: [math]

---

---
tags: math
---

# 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 experiement was done selecting numbers that get replaced from the original population.


|      | With replacement<br>(allow duplicates) | Without replacement <br> (no duplicates) |
|---|---|---|
| |  $$n^k$$ | $$ n! $$|
|Select k  **PERMUTATIONS:** <br>order matters (many unique) |  $$n^k$$ | $$\frac{n!}{(n-k)!}$$|
| Select k **COMBINATIONS:** <br> 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)!}$$<div class='note'> *"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 states. A permutation is defined by a [ bijective mapping](https://en.wikipedia.org/wiki/Bijection).

# Links to related ideas
    
- [Combinations and permutations](https://www.mathsisfun.com/combinatorics/combinations-permutations.html): step by step summary at Math is Fun.
    
- [Group action](https://en.wikipedia.org/wiki/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](https://www.johndcook.com/TwelvefoldWay.pdf): 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](https://dlmf.nist.gov/26.17).
    
- [Gowers on Permutations](https://gowers.wordpress.com/2011/10/16/permutations/): Mathematician [Tim Gowers](https://en.wikipedia.org/wiki/Timothy_Gowers) discussing the interpretation of Permutations. Comments on blog post by Terry Tao.

- [Permutations at Rosetta Code](https://rosettacode.org/wiki/Permutations) permutation generation of a set, written in many languages. Also: [Permutations in OCaml by chess960](https://www2.lib.uchicago.edu/keith/chess960/permutations.html).
