Permutations and Arrangements

Permutations and arrangements are common concepts in various types of problems.

This article does not discuss the number of permutations

The topic of this article is permutations (bijections), not the permutation count in combinatorics. For content related to permutation counts, please refer to Permutations and Combinations.

Convention

Unless otherwise specified, this article always discusses finite sets.

Definition

A bijection (i.e., a one-to-one correspondence) \(\sigma\) from a set \(X\) to itself is called a permutation of \(X\). If the set \(X\) also has a total order, then a permutation of \(X\) is often called an arrangement (or full permutation). This total order is called the natural order on the set.

「Permutation」 vs. 「Arrangement」

In the Chinese context, "permutation" (置换) usually refers to changing the order of elements, while "arrangement" (排列) usually refers to lining up elements in a sequence. When there is a natural order among the elements, these two concepts are the same: an "arrangement" can be seen as the result of a "permutation"; compared to the natural order of the elements, the order of elements in an "arrangement" specifies a "permutation". Since this article uses the term "arrangement" assuming the existence of a natural order on the set, it does not deliberately distinguish between these two concepts.

Of course, elements without a natural order can also be "arranged". Such "arrangements" often appear in combinatorial counting problems, which is beyond the scope of this article.

Let the size of set \(X\) be \(n\). Then the total number of permutations on \(X\) is \(n!\). In particular, \(0!=1\), meaning the empty set has exactly one permutation, the empty permutation.

Notation

Permutations discuss the correspondence between elements and do not care about what the elements actually are. Therefore, when discussing a set of size \(n\), it is usually assumed that the set is \(\{1,2,\cdots,n\}\); when a natural order is needed on the set, it is usually assumed to be the natural order on natural numbers.

Representation Methods

Permutations can be represented in several ways. Here, using the following permutation as an example, different representation methods are discussed.

\[ \sigma(1) = 2,\ \sigma(2) = 6,\ \sigma(3) = 5,\ \sigma(4) = 4,\ \sigma(5) = 3,\ \sigma(6) = 1. \]

Two-line Notation

A permutation on set \(X=\{x_1,x_2,\cdots,x_n\}\) can be represented as

\[ \sigma=\begin{pmatrix}x_1&x_2&\cdots&x_n\\ x_{p_1}&x_{p_2}&\cdots&x_{p_n} \end{pmatrix}. \]

It indicates that permutation \(\sigma\) maps element \(x_i\) to \(x_{p_i}\). Here, of course, \(X=\{x_{p_1},x_{p_2},\cdots,x_{p_n}\}\) must hold. In the two-line notation, the order of elements in the first row is not important; what matters is the correspondence between the two rows.

For example, the previous example can be written in two-line notation as

\[ \sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 6 & 5 & 4 & 3 & 1 \end{pmatrix}, \]

or, of course, as

\[ \sigma= \begin{pmatrix} 6 & 5 & 4 & 3 & 2 & 1 \\ 1 & 3 & 4 & 5 & 6 & 2 \end{pmatrix}. \]

One-line Notation

Often, the set \(X\) has a natural order. If in the two-line notation the first row is written in natural order by default and omitted, then the permutation can be represented as

\[ \sigma=\sigma(1)\sigma(2)\cdots\sigma(n). \]

This is more like the concept of arrangement in natural language. Therefore, sometimes "arrangement" is used to refer to this ordered tuple.

The previous example in one-line notation can be written as

\[ \sigma=265431. \]

This one-line notation is often used to compare the sizes of different arrangements.

Cycle Notation

Permutations have another more compact representation called cycle notation. It expresses a permutation as a product of disjoint cycles. The steps to write a given permutation in cycle notation are described below.

Given a permutation \(\sigma\), it can be written in cycle notation through the following steps:

If there are elements in \(X\) that have not been written down, write a left parenthesis and write down any such element;
When the previously written element is \(x\),
- If \(\sigma(x)\) has already been written before, write a right parenthesis and return to step 1;
- If \(\sigma(x)\) has not been written down, write down \(\sigma(x)\) and continue with step 2;
Until all elements of \(X\) have been written down, end.

Each pair of parentheses encloses a cycle. The number of elements within the parentheses is called the length of the corresponding cycle. In practice, cycles of length one are often omitted.

The previous example in cycle notation can be written as

\[ \sigma=(126)(35)(4)=(126)(35). \]

In the identity permutation, all cycles are of length one, often denoted as \((1)\) rather than omitting them all.

Composition

The composition of permutations is the composition of mappings. The composition of permutations is also often called the multiplication of permutations.

Given two permutations

\[ \sigma=\begin{pmatrix}x_1&x_2&\cdots&x_n\\ x_{p_1}&x_{p_2}&\cdots&x_{p_n}\end{pmatrix},\ \pi=\begin{pmatrix}x_{p_1}&x_{p_2}&\cdots&x_{p_n}\\ x_{q_1}&x_{q_2}&\cdots&x_{q_n}\end{pmatrix}, \]

then their product \(\pi\circ\sigma\) is

\[ \pi\circ\sigma=\begin{pmatrix}x_1&x_2&\cdots&x_n\\ x_{q_1}&x_{q_2}&\cdots&x_{q_n}\end{pmatrix}. \]

Simply put, it means applying mapping \(\sigma\) first, then mapping \(\pi\). Note that in the two-line notation above, the order of the second row of the inner mapping \(\sigma\) matches the order of the first row of the outer mapping \(\pi\).

Since permutations \(\sigma\) and \(\pi\) are essentially two mappings, \((\pi\circ\sigma)(x)=\pi(\sigma(x))\). The operation order for permutation composition is from right to left. Permutation multiplication is not commutative, so using the wrong order may lead to incorrect results.

The product of multiple consecutive permutations is called the power of a permutation, which can be accelerated using fast exponentiation.

Inverse Permutation

Since permutations are bijections, they always have corresponding inverse permutations.

Given a permutation

\[ \sigma=\begin{pmatrix}x_1&x_2&\cdots&x_n\\ x_{p_1}&x_{p_2}&\cdots&x_{p_n}\end{pmatrix}, \]

its inverse permutation is

\[ \sigma^{-1}=\begin{pmatrix}x_{p_1}&x_{p_2}&\cdots&x_{p_n}\\x_1&x_2&\cdots&x_n\end{pmatrix}. \]

In cycle notation, taking the inverse of each cycle yields the inverse of the original permutation; taking the inverse of a cycle simply reverses the writing order of its elements. For example, the cycle notation of the inverse of \(\sigma\) from the earlier example is

\[ \sigma^{-1} = (621)(53) = (162)(35). \]

Given an arrangement of \(1\sim n\) and the sequence of ranks of its elements, they are inverse permutations of each other.

Cycles

A cycle itself is a special permutation. The characteristic of a cycle is that starting from any point \(x\) in the cycle, any other point \(y\) in the cycle can be obtained by repeatedly applying permutation \(\sigma\). A cycle of length \(k\) is also called a \(k\)-cycle. Applying a \(k\)-cycle \(k\) times yields the identity permutation, meaning each element returns to its starting position.

The cycle notation of a permutation can be seen as writing the permutation as a product of these special permutations (cycles), so the cycle notation can also be regarded as the cycle decomposition of the permutation. For each permutation, its decomposition into a product of cycles is unique up to the order of cycles. Cycles can be seen as the basic building blocks of permutations.

The cycle decomposition of a permutation has a clear geometric interpretation. If each ordered pair \((x,\sigma(x))\) in a permutation on set \(S\) is considered as an edge of a directed graph with vertices \(S\), then these cycles are the loops in this graph. If permutation \(\sigma\) can be decomposed into \(m\) cycles, it means the corresponding directed graph has a total of \(m\) loops (including self-loops). These loops are naturally disjoint.

Fixed Points

A \(1\)-cycle is a fixed point of the permutation. For a permutation \(\sigma\) on set \(X\), \(X^\sigma\) usually denotes the set of fixed points of \(\sigma\), i.e., \(X^\sigma=\{x\in X:\sigma(x)=x\}\).

Transpositions

A \(2\)-cycle is also called a transposition. That is, a transposition is a permutation that only swaps the positions of a pair of elements. Its cycle notation is \((x_ix_j)\), indicating it swaps the positions of \(x_i\) and \(x_j\).

Any permutation can be written as a product of transpositions. This is equivalent to saying that any ordered arrangement can be restored to a specified sorted order through a series of operations swapping two elements. This is exactly what sorting algorithms based on swaps do.

Furthermore, the correctness of the Bubble Sort algorithm actually shows that any permutation can be written as a product of adjacent transpositions. Here, an adjacent transposition refers to a transposition that only swaps adjacent elements.

Properties

In applications, it is often necessary to focus on the properties of individual permutations.

Parity

The way to decompose a cycle into transpositions is not unique. For example,

\[ (123)=(13)(12)=(12)(23)=(12)(13)(12)(13). \]

However, when a permutation is decomposed into a series of transpositions, the parity of the number of transpositions required is fixed. The parity of the number of transpositions in a decomposition of a permutation is also called the parity of the permutation.

A permutation that can be decomposed into an even number of transpositions is called an even permutation; one that can be decomposed into an odd number of transpositions is called an odd permutation. When \(n\ge2\), the number of odd permutations and even permutations of size \(n\) are equal.

Sign

Based on the parity of a permutation, the sign of a permutation can also be defined, denoted as \(\operatorname{sgn}\sigma\). The sign of an even permutation is defined as \(+1\), and the sign of an odd permutation is defined as \(-1\).

The sign of the product of permutations equals the product of their signs, i.e.,

\[ \operatorname{sgn}(\pi\circ\sigma)=\operatorname{sgn} \pi\cdot\operatorname{sgn}\sigma. \]

That is, the composition of two permutations with the same parity is even, and the composition of two permutations with different parity is odd. This conclusion is obvious from the perspective of transposition decomposition.

In particular, a single transposition necessarily changes the parity of a permutation. This also explains why, although the decomposition into transpositions is not unique, the parity of the required number of transpositions is fixed.

The sign of a permutation appears in the Leibniz expansion of the determinant.

Order of a Permutation

The order of a permutation is the smallest positive integer \(a\) such that applying the permutation \(a\) times returns all elements to their original positions. That is,

\[ \operatorname{ord}\sigma=\min\{a\in\mathbf N_+:\sigma^a=(1)\}. \]

On a finite set, the order of every permutation is finite. This means that starting from the initial order, as long as the sequence is shuffled repeatedly according to a fixed pattern, the arrangement can be restored to its original state in finite time.

Cycle Type

When decomposing a permutation of \(n\) elements into cycles, the cycle type of the permutation is the multiset of cycle lengths in the decomposition. These cycle lengths form an integer partition of \(n\). If the decomposition has \(\alpha_k\) cycles of length \(k\), then the cycle type is often denoted as

\[ 1^{\alpha_1}2^{\alpha_2}\cdots n^{\alpha_n}, \]

and these coefficients satisfy \(\sum_{k=1}^nk\alpha_k=n\).

Given a cycle type, the number of different permutations is

\[ \frac{n!}{1^{\alpha_1}2^{\alpha_2}\cdots n^{\alpha_n}\alpha_1!\alpha_2!\cdots\alpha_n!}. \]

Analysis

This is because, given any arrangement of \(1\sim n\), it can be partitioned into a cycle decomposition according to the cycle type. However, the order among cycles of the same length does not affect the permutation, so the total count needs to be divided by \(\prod_k\alpha_k!\). Additionally, within the same cycle, it is essentially a circular permutation, and the choice of starting point does not affect the permutation, so it needs to be divided by \(\prod_kk^{\alpha_k}\). This yields the above formula.

If only the number of cycles \(c(\sigma)\) in the decomposition is given, then the number of different permutations is the Stirling number of the first kind \(\begin{bmatrix}n\\ k\end{bmatrix}\). The number of different cycle types is the partition number \(p_n\) of \(n\).

From the cycle type, properties such as the order and parity of the permutation can be easily determined.

Since the order of a \(k\)-cycle is \(k\), and different cycles are disjoint, the order of permutation \(\sigma\) is

\[ \operatorname{lcm}\{k:\alpha_k>0\}. \]

Similarly, since the parity of a \(k\)-cycle is opposite to the parity of \(k\), the parity of permutation \(\sigma\) is the parity of

\[ \sum_k(k-1)\alpha_k=\sum_{k}k\alpha_k-\sum_{k}\alpha_k=n-c(\sigma) \]

Here, \(c(\sigma)\) is the number of cycles (including \(1\)-cycles, i.e., fixed points).

Cycle type plays an important role in Pólya counting.

If the set \(X\) itself has a natural order, then permutation \(\sigma\) is often called an arrangement and represented using one-line notation

\[ \sigma(1)\sigma(2)\cdots\sigma(n) \]

Be careful not to confuse this with cycle notation.

Inversion Number

In an arrangement, if a larger number appears before a smaller number, these two numbers are said to form an inversion. The comparison here is based on the natural order.

The total number of inversions appearing in an arrangement is called the inversion number of the permutation. The inversion number of an arrangement is the minimum number of adjacent transpositions required to restore it to sorted order. Therefore, the parity of the inversion number of an arrangement matches the parity of the corresponding permutation. This can serve as an equivalent definition of the parity of a permutation.

Algorithms for computing the inversion number can use Merge Sort or Binary Indexed Tree (Fenwick Tree), both with time complexity \(O(n\log n)\). Explanations of these algorithms are detailed in their respective sections; reference implementations are provided here.

Reference Implementation

Merge SortBinary Indexed Tree

#include <iostream>
#include <vector>

// Merge sort and count inversions.
long long merge_sort(std::vector<int>& nums, int b, int e) {
  // Return 0 when length <= 1.
  if (e - b <= 1) return 0;
  long long res = 0;
  int m = (b + e) / 2;
  // Merge_sort two halves.
  res += merge_sort(nums, b, m);
  res += merge_sort(nums, m, e);
  // Temporary vector to store sorted array.
  std::vector<int> tmp(e - b);
  int i = b, j = m, k = 0;
  while (i < m && j < e) {
    if (nums[j] < nums[i]) {
      tmp[k] = nums[j++];
      // In this case, all elements in [i,m) are larger than element j.
      res += m - i;
    } else {
      tmp[k] = nums[i++];
    }
    ++k;
  }
  // Deal with remaining elements.
  for (; i < m; ++i, ++k) {
    tmp[k] = nums[i];
  }
  for (; j < e; ++j, ++k) {
    tmp[k] = nums[j];
  }
  // Copy back to original vector.
  for (i = b, k = 0; i < e; ++i, ++k) {
    nums[i] = tmp[k];
  }
  return res;
}

int main() {
  int n;
  std::cin >> n;
  std::vector<int> nums(n);
  for (int& num : nums) {
    std::cin >> num;
  }
  std::cout << merge_sort(nums, 0, n);
  return 0;
}

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

// A simple BIT implementation.
class BIT {
  int n;
  std::vector<int> su;

 public:
  BIT(int n) : n(n), su(n + 1) {}

  // Add v to the x-th number.
  void add(int x, int v) {
    for (; x <= n; x += x & (-x)) {
      su[x] += v;
    }
  }

  // Get the cumulative sum till the x-th number.
  int query(int x) {
    int res = 0;
    for (; x; x &= x - 1) {
      res += su[x];
    }
    return res;
  }
};

// Count inversions.
long long solve(const std::vector<int>& nums) {
  // Discretization.
  std::vector<int> sorted(nums);
  std::sort(sorted.begin(), sorted.end());
  sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
  std::unordered_map<int, int> ids;
  int m = sorted.size();
  for (int i = 0; i < m; ++i) {
    // Reverse the order.
    // Now a smaller id means a larger element.
    ids[sorted[i]] = m - i;
  }
  // Main part.
  BIT bit(m);
  long long res = 0;
  for (int num : nums) {
    int id = ids[num];
    // Get inversion pair (i,j) with j the current element.
    // Namely, count the number of elements larger than
    //     the current one but located before it.
    res += bit.query(id - 1);
    // Insert the current element to the BIT.
    bit.add(id, 1);
  }
  return res;
}

int main() {
  int n;
  std::cin >> n;
  std::vector<int> nums(n);
  for (int& num : nums) {
    std::cin >> num;
  }
  std::cout << solve(nums);
  return 0;
}

Order

Arrangements can be compared. Since each one-line notation is a string, the order of arrangements is the lexicographical order on these strings.

In C++ STL library <algorithm>, prev_permutation and next_permutation can be used to find the previous and next permutations in lexicographical order, respectively.

Rank

When listing all permutations of \(n\) elements in lexicographical order from smallest to largest, the position of a particular permutation in this sequence is its rank. It establishes a one-to-one correspondence between permutations and positive integers, often used for state compression in permutation-related problems.

In the Chinese competitive programming community, this rank is often called the "Cantor expansion" of the permutation, but this name is not standard. A more rigorous statement is that the Cantor expansion of a permutation's rank corresponds to the Lehmer code of that permutation.

About 「Cantor Expansion」

As the name suggests, Cantor expansion refers to a method of expanding natural numbers into sequences. It can be seen as a special numeral system, also called the factorial number system. In this system, different digits have different radices. For example, the decimal number \(463_{10}\) can be expressed in factorial number system as

\[ 463_{10}=341010_{!}. \]

It means

\[ 463=3\times 5!+4\times 4!+1\times 3!+0\times 2!+1\times 1!+0\times 0!. \]

Cantor studied such mixed-radix numeral systems, so the digit representation of natural numbers in this system is often called the Cantor expansion of natural numbers.

Example

Readers unfamiliar with the method of computing rank can understand the basic idea of the algorithm below through this simple example.

To compute the rank of arrangement \(\sigma=452631\), we need to compute the number of arrangements lexicographically smaller than \(\sigma\), then add one. The idea here is similar to Digit DP, discussing digit by digit.

The choice for the 1^st digit must be smaller than \(\sigma\), can only be from \(\{1,2,3\}\), the following 5 digits can be chosen arbitrarily, giving \(3\times 5!\) possible arrangements;
If the 1^st digit is also chosen as \(4\), then the choice for the 2^nd digit must be smaller than \(\sigma\), can only be from \(\{1,2,3\}\) (here, \(4\) is already chosen), the following 4 digits can be chosen arbitrarily, giving \(3\times 4!\) possible arrangements;
Similarly, when the first 2 digits are the same as \(\sigma\), the choice for the 3^rd digit must be smaller than \(\sigma\), can only be from \(\{1\}\), the following 3 digits can be chosen arbitrarily, giving \(1\times 3!\) possible arrangements;
When the first 3 digits are the same as \(\sigma\), the choice for the 4^th digit must be smaller than \(\sigma\), can only be from \(\{1,3\}\), the following 2 digits can be chosen arbitrarily, giving \(2\times 2!\) possible arrangements;
When the first 4 digits are the same as \(\sigma\), the choice for the 5^th digit must be smaller than \(\sigma\), can only be from \(\{1\}\), the following 1 digit can be chosen arbitrarily, giving \(1\times 1!\) possible arrangements;
When the first 5 digits are the same as \(\sigma\), the choice for the 6^th digit cannot yield an arrangement smaller than \(\sigma\), so there are \(0\times 0!\) possible arrangements.

Therefore, the rank of arrangement \(\sigma\) is

\[ 1+3\times 5!+3\times 4!+1\times 3!+2\times 2!+1\times 1!+0\times 0!=444. \]

For different arrangements, the key point is to determine the coefficients before the factorials. In fact, these coefficients are exactly the number of elements that appear after the current position but are smaller than the element at that position.

From the example, we can see that the algorithm to compute the rank of a given arrangement can be divided into two steps:

Convert the given arrangement of length \(n\) into its Lehmer code, i.e., a sequence \(L_\sigma\) of length \(n\), where the \(i\)-th entry is

\[ L_\sigma(i)=\#\{j>i:\sigma(j)<\sigma(i)\}, \]

which is the number of elements that appear after position \(i\) but are smaller than \(\sigma(i)\). It equals the rank (minus one) of the given element among the unused elements.
Treat the Lehmer code as the Cantor expansion of a natural number, find the original natural number, and add one. That is, the final rank is

\[ \operatorname{rank}\sigma=1+L_\sigma(1)(n-1)!+L_\sigma(2)(n-2)!+\cdots+L_\sigma(n)0!. \]

To solve the inverse problem, i.e., given a rank find the corresponding arrangement, simply reverse the above process. The sum of the numbers in the Lehmer code obtained during this process is the inversion number of the arrangement.

When implementing in programming, the key is to quickly compute "the rank of a given element among unused elements" (when computing rank) and "the element with a given rank among unused elements" (when computing arrangement). These can be maintained using data structures like Binary Indexed Tree or Segment Tree. Both forward and inverse operations have time complexity \(O(n\log n)\).