Unter einer Permutation versteht man allgemein das Vertauschen von in einer bestimmten Reihenfolge angeordneten Zahlen, Elementen oder Ähnlichem. So sind z. B. die geordneten Tripel (1; 3; 5), (3; 1; 5) und (5; 3; 1) jeweils Permutationen voneinander. (Man kann übrigens Permutationen auch als Variationen für den Fall k = n ansehen.)
In der Kombinatorik möchte man wissen, wie viele Permutationen es für n Elemente einer Menge gibt. Dabei unterscheidet man, ob alle n Elemente verschieden und unterscheidbar sind oder ob es identische, ununterscheidbare Elemente gibt. Man sagt im ersten Fall auch, es gebe „keine Wiederholungen“, und im zweiten Fall, dass „Wiederholungen erlaubt“ seien.
Beispielsweise sind bei der Menge {1; 3; 5} alle Elemente verschieden („keine Wiederholungen“) und man hat zunächst drei Möglichkeiten, die 1 anzuordnen: (1; x; x), (x; 1; x) und (x; x; 1). Ist diese festgelegt, gibt es für die 3 noch zwei Möglichkeiten und schließlich noch eine Möglichkeit für die 5. Insgesamt erhält man \(3 \cdot 2 \cdot 1 = 3! = 6\) Möglichkeiten und allgemein für n Elemente n!. Das Symbol „!“ steht für das Rechenzeichen (den Operator) Fakultät.
Die Menge {a; b; b; c; c; c; d} enthält einmal zwei und einmal drei gleiche Elemente. Es liegt also der zweite Fall „Wiederholungen erlaubt“ vor. Die Anzahl der Permutationen mit Wiederholungen erhält man, wenn man die 7! Permutationen aller sieben Elemente ohne Wiederholungen durch die 2! Permutationen der zwei „b“ und durch die 3! Permutationen der drei „c“ teilt – denn diese sind ja nicht zu unterscheiden. Es gibt somit im Beispiel mit Permutationen \(\displaystyle \frac{7!}{2!\cdot3!}=420\) Permutationen. Die allgemeine Formel lautet \(\displaystyle \frac{n!}{k_1!\cdot k_2! \cdot \ldots}\), wenn von n Elementen jeweils k1, k2, … untereinander gleich sind.