Editing Permutation (section)

==Other uses of the term ''permutation''==
The concept of a permutation as an ordered arrangement admits several generalizations that have been called ''permutations'', especially in older literature.

===''k''-permutations of ''n''===
In older literature and elementary textbooks, a '''''k''-permutation of ''n''''' (sometimes called a '''[[Partial permutation#Restricted partial permutations|partial permutation]]''', '''sequence without repetition''', '''variation''', or '''arrangement''') means an ordered arrangement (list) of a ''k''-element subset of an ''n''-set.{{efn|More precisely, ''variations without repetition''. The term is still common in other languages and appears in modern English most often in translation.}}<ref>{{Cite web |title=Combinations and Permutations |url=https://www.mathsisfun.com/combinatorics/combinations-permutations.html |access-date=2020-09-10 |website=www.mathsisfun.com}}</ref><ref>{{Cite web |last=Weisstein |first=Eric W. |title=Permutation |url=https://mathworld.wolfram.com/Permutation.html |access-date=2020-09-10 |website=mathworld.wolfram.com |language=en}}</ref> The number of such ''k''-permutations (''k''-arrangements) of <math>n</math> is denoted variously by such symbols as <math>P^n_k</math>,  <math>_nP_k</math>, <math>^n\!P_k</math>, <math>P_{n,k}</math>, <math>P(n,k)</math>, or <math>A^k_n</math>,<ref>{{harvnb|Uspensky|1937|p=18}}</ref> computed by the formula:<ref>{{cite book|author=Charalambides, Ch A.|title=Enumerative Combinatorics|publisher=CRC Press|year=2002|isbn=978-1-58488-290-9|page=42|url=https://books.google.com/books?id=PDMGA-v5G54C&pg=PA42}}</ref>
: <math>P(n,k) = \underbrace{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)}_{k\ \mathrm{factors}}</math>,

which is 0 when {{math|''k'' &gt; ''n''}}, and otherwise is equal to
: <math>\frac{n!}{(n-k)!}.</math>

The product is well defined without the assumption that <math>n</math> is a non-negative integer, and is of importance outside combinatorics as well; it is known as the [[Pochhammer symbol]] <math>(n)_k</math> or as the <math>k</math>-th falling factorial power <math>n^{\underline k}</math>:<blockquote><math>P(n,k)={_n} P_k =(n)_k = n^{\underline{k}} .</math></blockquote>This usage of the term ''permutation'' is closely associated with the term ''[[combination]]'' to mean a subset. A ''k-combination'' of a set ''S'' is a ''k-''element subset of ''S'': the elements of a combination are not ordered. Ordering the ''k''-combinations of ''S'' in all possible ways produces the ''k''-permutations of ''S''. The number of ''k''-combinations of an ''n''-set, ''C''(''n'',''k''), is therefore related to the number of ''k''-permutations of ''n'' by:
: <math>C(n,k) = \frac{P(n,k)}{P(k,k)}= \frac{n^{\underline{k}}}{k!} =  \frac{n!}{(n-k)!\,k!}.</math>

These numbers are also known as [[binomial coefficient]]s, usually denoted <math>\tbinom{n}{k}</math>:<blockquote><math>C(n,k)={_n} C_k =\binom{n}{k} .</math></blockquote>

===Permutations with repetition===
Ordered arrangements of ''k'' elements of a set ''S'', where repetition is allowed, are called [[Tuple|''k''-tuples]].  They have sometimes been referred to as '''permutations with repetition''', although they are not permutations in the usual sense. They are also called [[word (mathematics)|words]] or [[String (computer science)|strings]] over the alphabet ''S''. If the set ''S'' has ''n'' elements, the number of ''k''-tuples over ''S'' is <math>n^k.</math>

===Permutations of multisets===
[[File:Permutations with repetition cropped.svg|thumb|Permutations without repetition on the left, with repetition to their right]]

If ''M'' is a finite [[multiset]], then a '''multiset permutation''' is an ordered arrangement of elements of ''M'' in which each element appears a number of times equal exactly to its multiplicity in ''M''. An [[anagram]] of a word having some repeated letters is an example of a multiset permutation.{{efn|The natural order in this example is the order of the letters in the original word.}} If the multiplicities of the elements of ''M'' (taken in some order) are <math>m_1</math>, <math>m_2</math>, ..., <math>m_l</math> and their sum (that is, the size of ''M'') is ''n'', then the number of multiset permutations of ''M'' is given by the [[Multinomial coefficient#Multinomial coefficients|multinomial coefficient]],<ref>{{harvnb|Brualdi|2010|loc=p. 46, Theorem 2.4.2}}</ref>
:<math>
  {n \choose m_1, m_2, \ldots, m_l} =
  \frac{n!}{m_1!\, m_2!\, \cdots\, m_l!} =
  \frac{\left(\sum_{i=1}^l{m_i}\right)!}{\prod_{i=1}^l{m_i!}}.
</math>

For example, the number of distinct anagrams of the word MISSISSIPPI is:<ref>{{harvnb|Brualdi|2010|p=47}}</ref>
:<math>\frac{11!}{1!\, 4!\, 4!\, 2!} = 34650</math>.

A '''''k''-permutation''' of a multiset ''M'' is a sequence of ''k'' elements of ''M'' in which each element appears ''a number of times less than or equal to'' its multiplicity in ''M'' (an element's ''repetition number'').

===Circular permutations===
{{see also|Cyclic order#Finite cycles}}
Permutations, when considered as arrangements, are sometimes referred to as ''linearly ordered'' arrangements. If, however, the objects are arranged in a circular manner this distinguished ordering is weakened: there is no "first element" in the arrangement, as any element can be considered as the start. An arrangement of distinct objects in a circular manner is called a '''circular permutation'''.<ref>{{harvnb|Brualdi|2010|p=39}}</ref>{{efn|In older texts ''circular permutation'' was sometimes used as a synonym for [[cyclic permutation]], but this is no longer done. See {{harvtxt|Carmichael|1956|p=7}}}} These can be formally defined as [[equivalence classes]] of ordinary permutations of these objects, for the [[equivalence relation]] generated by moving the final element of the linear arrangement to its front.

Two circular permutations are equivalent if one can be rotated into the other. The following four circular permutations on four letters are considered to be the same.

<pre>
     1           4           2           3
   4   3       2   1       3   4       1   2
     2           3           1           4
</pre>

The circular arrangements are to be read counter-clockwise, so the following two are not equivalent since no rotation can bring one to the other.
<pre>
     1          1
   4   3      3   4
     2          2</pre>

There are (''n''&thinsp;–&thinsp;1)! circular permutations of a set with ''n'' elements.