text:
Permutation

In mathematics, a permutation of a set can mean one of two different things:
 * an arrangement of its members in a sequence or linear order, or
 * the act or process of changing the linear order of an ordered set.

An example of the first meaning, is the six permutations (orderings) of the set {1, 2, 3}: written as tuples, they are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). Anagrams of a word whose letters are all different are also permutations: the letters are already ordered in the original word, and the anagram reorders them. The study of permutations of finite sets is an important topic in combinatorics and group theory.

Permutations are used in almost every branch of mathematics and in many other fields of science. In computer science, they are used for analyzing sorting algorithms; in quantum physics, for describing states of particles; and in biology, for describing RNA sequences.

The number of permutations of $n$ distinct objects is $n$ factorial, usually written as $n!$, which means the product of all positive integers less than or equal to $n$.

According to the second meaning, a permutation of a set $S$ is defined as a bijection from $S$ to itself. That is, it is a function from $S$ to $S$ for which every element occurs exactly once as an image value. Such a function $$\sigma : S \to S$$ is equivalent to the rearrangement of the elements of $S$ in which each element i is replaced by the corresponding $$\sigma(i)$$. For example, the permutation (3, 1, 2) is described by the function $$\sigma$$ defined as

 * $$\sigma(1) = 3, \quad \sigma(2) = 1, \quad \sigma(3) = 2$$.

The collection of all permutations of a set form a group called the symmetric group of the set. The group operation is the composition of functions (performing one rearrangement after the other), which results in another function (rearrangement). The properties of permutations do not depend on the nature of the elements being permuted, only on their number, so one often considers the standard set $$S=\{1, 2, \ldots, n\}$$.

In elementary combinatorics, the $k$-permutations, or partial permutations, are the ordered arrangements of $k$ distinct elements selected from a set. When $k$ is equal to the size of the set, these are the permutations in the previous sense.

History
Permutations called hexagrams were used in China in the I Ching (Pinyin: Yi Jing) as early as 1000 BC.

In Greece, Plutarch wrote that Xenocrates of Chalcedon (396–314 BC) discovered the number of different syllables possible in the Greek language. This would have been the first attempt on record to solve a difficult problem in permutations and combinations.

Al-Khalil (717–786), an Arab mathematician and cryptographer, wrote the Book of Cryptographic Messages. It contains the first use of permutations and combinations, to list all possible Arabic words with and without vowels.

The rule to determine the number of permutations of n objects was known in Indian culture around 1150 AD. The Lilavati by the Indian mathematician Bhāskara II contains a passage that translates as follows: The product of multiplication of the arithmetical series beginning and increasing by unity and continued to the number of places, will be the variations of number with specific figures.

In 1677, Fabian Stedman described factorials when explaining the number of permutations of bells in change ringing. Starting from two bells: "first, two must be admitted to be varied in two ways", which he illustrates by showing 1 2 and 2 1. He then explains that with three bells there are "three times two figures to be produced out of three" which again is illustrated. His explanation involves "cast away 3, and 1.2 will remain; cast away 2, and 1.3 will remain; cast away 1, and 2.3 will remain". He then moves on to four bells and repeats the casting away argument showing that there will be four different sets of three. Effectively, this is a recursive process. He continues with five bells using the "casting away" method and tabulates the resulting 120 combinations. At this point he gives up and remarks: Now the nature of these methods is such, that the changes on one number comprehends the changes on all lesser numbers, ... insomuch that a compleat Peal of changes on one number seemeth to be formed by uniting of the compleat Peals on all lesser numbers into one entire body; Stedman widens the consideration of permutations; he goes on to consider the number of permutations of the letters of the alphabet and of horses from a stable of 20.

A first case in which seemingly unrelated mathematical questions were studied with the help of permutations occurred around 1770, when Joseph Louis Lagrange, in the study of polynomial equations, observed that properties of the permutations of the roots of an equation are related to the possibilities to solve it. This line of work ultimately resulted, through the work of Évariste Galois, in Galois theory, which gives a complete description of what is possible and impossible with respect to solving polynomial equations (in one unknown) by radicals. In modern mathematics, there are many similar situations in which understanding a problem requires studying certain permutations related to it.

Permutations played an important role in the cryptanalysis of the Enigma machine, a cipher device used by Nazi Germany during World War II. In particular, one important property of permutations, namely, that two permutations are conjugate exactly when they have the same cycle type, was used by cryptologist Marian Rejewski to break the German Enigma cipher in turn of years 1932-1933.

Definition
In mathematics texts it is customary to denote permutations using lowercase Greek letters. Commonly, either $$\alpha,\beta,\gamma$$ or $$\sigma, \tau,\rho,\pi$$ are used.

A permutation can be defined as a bijection (an invertible mapping, a one-to-one and onto function) from a set $S$ to itself: "$\sigma : S\ \stackrel{\sim}{\longrightarrow}\ S.$"The identity permutation is defined by $$\sigma(x) = x $$ for all elements $$x\in S  $$, and can be denoted by the number $$1$$, by $$\text{id}= \text{id}_S   $$, or by a single 1-cycle (x).

The set of all permutations of a set with n elements forms the symmetric group $$S_n$$, where the group operation is composition of functions. Thus for two permutations $$\sigma$$ and $$\tau$$ in the group $$S_n$$, their product $$\pi = \sigma\tau$$ is defined by: "$\pi(i)=\sigma(\tau(i)).$"Composition is usually written without a dot or other sign. In general, composition of two permutations is not commutative: $$\tau\sigma \neq \sigma\tau.$$

As a bijection from a set to itself, a permutation is a function that performs a rearrangement of a set, termed an active permutation or substitution. An older viewpoint sees a permutation as an ordered arrangement or list of all the elements of S, called a passive permutation (see below).

A permutation $$\sigma$$ can be decomposed into one or more disjoint cycles which are the orbits of the cyclic group $$\langle\sigma\rangle = \{1, \sigma, \sigma^2,\ldots\} $$ acting on the set S. A cycle is found by repeatedly applying the permutation to an element: $$x, \sigma(x),\sigma(\sigma(x)),\ldots, \sigma^{k-1}(x)$$, where we assume $$\sigma^k(x)=x$$. A cycle consisting of k elements is called a k-cycle. (See below.)

A fixed point of a permutation $$\sigma$$ is an element x which is taken to itself, that is $$\sigma(x)=x $$, forming a 1-cycle $$(\,x\,)$$. A permutation with no fixed points is called a derangement. A permutation exchanging two elements (a single 2-cycle) and leaving the others fixed is called a transposition.

Notations
Several notations are widely used to represent permutations conveniently. Cycle notation is a popular choice, as it is compact and shows the permutation's structure clearly. This article will use cycle notation unless otherwise specified.

Two-line notation
Cauchy's two-line notation lists the elements of S in the first row, and the image of each element below it in the second row. For example, the permutation of S = {1, 2, 3, 4, 5, 6} given by the function"$\sigma(1) = 2, \ \ \sigma(2) = 6, \ \ \sigma(3) = 5, \ \ \sigma(4) = 4, \ \ \sigma(5) = 3, \ \ \sigma(6) = 1 $"can be written as
 * $$\sigma = \begin{pmatrix}

1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 6 & 5 & 4 & 3 & 1 \end{pmatrix}.$$ The elements of S may appear in any order in the first row, so this permutation could also be written:
 * $$\sigma = \begin{pmatrix}

2 & 3 & 4 & 5 & 6 & 1 \\ 6 & 5 & 4 & 3 & 1 & 2 \end{pmatrix} = \begin{pmatrix} 6 & 5 & 4 & 3 & 2 & 1 \\ 1 & 3 & 4 & 5 & 6 & 2 \end{pmatrix}.$$

One-line notation
If there is a "natural" order for the elements of S, say $$x_1, x_2, \ldots, x_n$$, then one uses this for the first row of the two-line notation:
 * $$\sigma = \begin{pmatrix}

x_1        & x_2         & x_3         & \cdots & x_n \\ \sigma(x_1) & \sigma(x_2) & \sigma(x_3) & \cdots & \sigma(x_n) \end{pmatrix}.$$

Under this assumption, one may omit the first row and write the permutation in one-line notation as
 * $$\sigma = \sigma(x_1) \; \sigma(x_2) \; \sigma(x_3) \; \cdots \; \sigma(x_n) $$,

that is, as an ordered arrangement of the elements of S. Care must be taken to distinguish one-line notation from the cycle notation described below: a common usage is to omit parentheses or other enclosing marks for one-line notation, while using parentheses for cycle notation. The one-line notation is also called the word representation.

The example above would then be: $$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 6 & 5 & 4 & 3 & 1 \end{pmatrix} = 2 6  5  4  3  1.$$ (It is typical to use commas to separate these entries only if some have two or more digits.)

This compact form is common in elementary combinatorics and computer science. It is especially useful in applications where the permutations are to be compared as larger or smaller using lexicographic order.

Cycle notation
Cycle notation describes the effect of repeatedly applying the permutation on the elements of the set S, with an orbit being called a cycle. The permutation is written as a list of cycles; since distinct cycles involve disjoint sets of elements, this is referred to as "decomposition into disjoint cycles".

To write down the permutation $$\sigma$$ in cycle notation, one proceeds as follows:

 * 1) Write an opening bracket followed by an arbitrary element x of $$S$$:  $$(\,x$$
 * 2) Trace the orbit of x, writing down the values under successive applications of $$\sigma$$: $$(\,x,\sigma(x),\sigma(\sigma(x)),\ldots$$
 * 3) Repeat until the value returns to x, and close the parenthesis without repeating x: $$(\,x\,\sigma(x)\,\sigma(\sigma(x))\,\ldots\,)$$
 * 4) Continue with an element y of S which was not yet written, and repeat the above process: $$(\,x\,\sigma(x)\,\sigma(\sigma(x))\,\ldots\,)(\,y\,\ldots\,)$$
 * 5) Repeat until all elements of S are written in cycles.

Also, it is common to omit 1-cycles, since these can be inferred: for any element x in S not appearing in any cycle, one implicitly assumes $$\sigma(x) = x$$.

Following the convention of omitting 1-cycles, one may interpret an individual cycle as a permutation which fixes all the elements not in the cycle (a cyclic permutation having only one cycle of length greater than 1). Then the list of disjoint cycles can be seen as the composition of these cyclic permutations. For example, the one-line permutation $$\sigma = 2 6 5 4 3 1 $$ can be written in cycle notation as:"$\sigma = (126)(35)(4) = (126)(35). $"This may be seen as the composition $$\sigma = \kappa_1 \kappa_2  $$ of cyclic permutations:"$\kappa_1 = (126) = (126)(3)(4)(5),\quad \kappa_2 = (35)= (35)(1)(2)(6). $"While permutations in general do not commute, disjoint cycles do; for example:"$\sigma = (126)(35) = (35)(126). $"Also, each cycle can be rewritten from a different starting point; for example,"$\sigma = (126)(35) = (261)(53). $"Thus one may write the disjoint cycles of a given permutation in many different ways.

A convenient feature of cycle notation is that inverting the permutation is given by reversing the order of the elements in each cycle. For example, "$\sigma^{-1} = \left(\vphantom{A^2}(126)(35)\right)^{-1} = (621)(53). $"

Canonical cycle notation
In some combinatorial contexts it is useful to fix a certain order for the elements in the cycles and of the (disjoint) cycles themselves. Miklós Bóna calls the following ordering choices the canonical cycle notation:
 * in each cycle the largest element is listed first
 * the cycles are sorted in increasing order of their first element, not omitting 1-cycles

For example, "(513)(6)(827)(94)"is a permutation of S = {1, 2,. . ., 9} in canonical cycle notation.

Richard Stanley calls this the "standard representation" of a permutation, and Martin Aigner uses "standard form". Sergey Kitaev also uses the "standard form" terminology, but reverses both choices; that is, each cycle lists its minimal element first, and the cycles are sorted in decreasing order of their minimal elements.

Composition of permutations
There are two ways to denote the composition of two permutations. In the most common notation, $$\sigma\cdot \tau$$ is the function that maps any element x to $$\sigma(\tau(x))$$. The rightmost permutation is applied to the argument first, because the argument is written to the right of the function.

A different rule for multiplying permutations comes from writing the argument to the left of the function, so that the leftmost permutation acts first. In this notation, the permutation is often written as an exponent, so σ acting on x is written xσ; then the product is defined by $$x^{\sigma\cdot\tau} = (x^\sigma)^\tau$$. This article uses the first definition, where the rightmost permutation is applied first.

The function composition operation satisfies the axioms of a group. It is associative, meaning $$(\rho\sigma)\tau = \rho(\sigma\tau)$$, and products of more than two permutations are usually written without parentheses. The composition operation also has an identity element (the identity permutation $$\text{id}$$), and each permutation $$\sigma$$ has an inverse $$\sigma^{-1}$$ (its inverse function) with $$\sigma^{-1}\sigma = \sigma\sigma^{-1}=\text{id}$$.

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, sequence without repetition, variation, or arrangement) means an ordered arrangement (list) of a k-element subset of an n-set. The number of such k-permutations (k-arrangements) of $$n$$ is denoted variously by such symbols as $$P^n_k$$, $$_nP_k$$, $$^n\!P_k$$, $$P_{n,k}$$, $$P(n,k)$$, or $$A^k_n$$, computed by the formula:
 * $$P(n,k) = \underbrace{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)}_{k\ \mathrm{factors}}$$,

which is 0 when $k > n$, and otherwise is equal to
 * $$\frac{n!}{(n-k)!}.$$

The product is well defined without the assumption that $$n$$ is a non-negative integer, and is of importance outside combinatorics as well; it is known as the Pochhammer symbol $$(n)_k$$ or as the $$k$$-th falling factorial power $$n^{\underline k}$$:"$P(n,k)={_n} P_k =(n)_k = n^{\underline{k}} .$|undefined"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:
 * $$C(n,k) = \frac{P(n,k)}{P(k,k)}= \frac{n^{\underline{k}}}{k!} = \frac{n!}{(n-k)!\,k!}.$$

These numbers are also known as binomial coefficients, usually denoted $$\tbinom{n}{k}$$:"$C(n,k)={_n} C_k =\binom{n}{k} .$"

Permutations with repetition
Ordered arrangements of k elements of a set S, where repetition is allowed, are called 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 words over the alphabet S. If the set S has n elements, the number of k-tuples over S is $$n^k.$$ A formal language is a set of words obeying specified rules.

Permutations of multisets

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. If the multiplicities of the elements of M (taken in some order) are $$m_1$$, $$m_2$$, ..., $$m_l$$ 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,

{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!}}. $$

For example, the number of distinct anagrams of the word MISSISSIPPI is:
 * $$\frac{11!}{1!\, 4!\, 4!\, 2!} = 34650$$.

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
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. 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.

1          4           2           3   4   3       2   1       3   4       1   2     2           3           1           4

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. 1         1   4   3      3   4     2          2

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

Properties
The number of permutations of $n$ distinct objects is $n$!.

The number of $n$-permutations with $k$ disjoint cycles is the signless Stirling number of the first kind, denoted $$c(n,k)$$ or $$[\begin{smallmatrix}n \\ k\end{smallmatrix}]$$.

Cycle type
The cycles (including the fixed points) of a permutation $$\sigma$$ of a set with $n$ elements partition that set; so the lengths of these cycles form an integer partition of $n$, which is called the cycle type (or sometimes cycle structure or cycle shape) of $$\sigma$$. There is a "1" in the cycle type for every fixed point of $$\sigma$$, a "2" for every transposition, and so on. The cycle type of $$\beta = (1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)$$ is $$(3, 2, 2, 1).$$

This may also be written in a more compact form as $[1^{1}2^{2}3^{1}]$. More precisely, the general form is $$[1^{\alpha_1}2^{\alpha_2}\dotsm n^{\alpha_n}]$$, where $$\alpha_1,\ldots,\alpha_n$$ are the numbers of cycles of respective length. The number of permutations of a given cycle type is
 * $$\frac{n!}{1^{\alpha_1}2^{\alpha_2}\dotsm n^{\alpha_n}\alpha_1!\alpha_2!\dotsm \alpha_n!}$$.

The number of cycle types of a set with $n$ elements equals the value of the partition function $$p(n)$$.

Polya's cycle index polynomial is a generating function which counts permutations by their cycle type.

Conjugating permutations
In general, composing permutations written in cycle notation follows no easily described pattern – the cycles of the composition can be different from those being composed. However the cycle type is preserved in the special case of conjugating a permutation $$\sigma$$ by another permutation $$\pi$$, which means forming the product $$\pi\sigma\pi^{-1}$$. Here, $$\pi\sigma\pi^{-1}$$ is the conjugate of $$\sigma$$ by $$\pi$$ and its cycle notation can be obtained by taking the cycle notation for $$\sigma$$ and applying $$\pi$$ to all the entries in it. It follows that two permutations are conjugate exactly when they have the same cycle type.

Order of a permutation
The order of a permutation $$\sigma$$ is the smallest positive integer m so that $$\sigma^m = \mathrm{id}$$. It is the least common multiple of the lengths of its cycles. For example, the order of $$\sigma=(152)(34) $$ is $$\text{lcm}(3,2) = 6$$.

Parity of a permutation
Every permutation of a finite set can be expressed as the product of transpositions. Although many such expressions for a given permutation may exist, either they all contain an even number of transpositions or they all contain an odd number of transpositions. Thus all permutations can be classified as even or odd depending on this number.

This result can be extended so as to assign a sign, written $$\operatorname{sgn}\sigma$$, to each permutation. $$\operatorname{sgn}\sigma = +1$$ if $$\sigma$$ is even and $$\operatorname{sgn}\sigma = -1$$ if $$\sigma$$ is odd. Then for two permutations $$\sigma$$ and $$\pi$$

 * $$\operatorname{sgn}(\sigma\pi) = \operatorname{sgn}\sigma\cdot\operatorname{sgn}\pi.$$

It follows that $$\operatorname{sgn}\left(\sigma\sigma^{-1}\right) = +1.$$

The sign of a permutation is equal to the determinant of its permutation matrix (below).

Matrix representation
A permutation matrix is an n × n matrix that has exactly one entry 1 in each column and in each row, and all other entries are 0. There are several ways to assign a permutation matrix to a permutation of {1, 2, ..., n}. One natural approach is to define $$L_{\sigma}$$ to be the linear transformation of $$\mathbb{R}^n$$ which permutes the standard basis $$\{\mathbf{e}_1,\ldots,\mathbf{e}_n\}$$ by $$L_\sigma(\mathbf{e}_j)=\mathbf{e}_{\sigma(j)}$$, and define $$M_{\sigma}$$ to be its matrix. That is, $$M_{\sigma}$$ has its jth column equal to the n × 1 column vector $$\mathbf{e}_{\sigma(j)}$$: its (i, j) entry is to 1 if i = σ(j), and 0 otherwise. Since composition of linear mappings is described by matrix multiplication, it follows that this construction is compatible with composition of permutations:"$M_\sigma M_\tau = M_{\sigma\tau}$."For example, the one-line permutations $$\sigma=213,\ \tau=231$$ have product $$\sigma\tau = 132$$, and the corresponding matrices are:$$ M_{\sigma} M_{\tau} = \begin{pmatrix} 0&1&0\\1&0&0\\0&0&1\end{pmatrix} \begin{pmatrix} 0&0&1\\1&0&0\\0&1&0\end{pmatrix} = \begin{pmatrix} 1&0&0\\0&0&1\\0&1&0\end{pmatrix} = M_{\sigma\tau}.$$

It is also common in the literature to find the inverse convention, where a permutation σ is associated to the matrix $$P_{\sigma} = (M_{\sigma})^{-1} = (M_{\sigma})^{T}$$ whose (i, j) entry is 1 if j = σ(i) and is 0 otherwise. In this convention, permutation matrices multiply in the opposite order from permutations, that is, $$P_\sigma P_{\tau} = P_{\tau\sigma}$$. In this correspondence, permutation matrices act on the right side of the standard $$1 \times n$$ row vectors $$({\bf e}_i)^T$$: $$({\bf e}_i)^T P_{\sigma} = ({\bf e}_{\sigma(i)})^T$$.

The Cayley table on the right shows these matrices for permutations of 3 elements.

Permutations of totally ordered sets
In some applications, the elements of the set being permuted will be compared with each other. This requires that the set S has a total order so that any two elements can be compared. The set {1, 2, ..., n} with the usual ≤ relation is the most frequently used set in these applications.

A number of properties of a permutation are directly related to the total ordering of S, considering the permutation written in one-line notation as a sequence $$\sigma = \sigma(1)\sigma(2)\cdots\sigma(n)$$.

Ascents, descents, runs, exceedances, records
An ascent of a permutation σ of n is any position i < n where the following value is bigger than the current one. That is, i is an ascent if $$\sigma(i)<\sigma(i{+}1)$$. For example, the permutation 3452167 has ascents (at positions) 1, 2, 5, and 6.

Similarly, a descent is a position i < n with $$\sigma(i)>\sigma(i{+}1)$$, so every i with $$1 \leq i<n$$ is either an ascent or a descent.

An ascending run of a permutation is a nonempty increasing contiguous subsequence that cannot be extended at either end; it corresponds to a maximal sequence of successive ascents (the latter may be empty: between two successive descents there is still an ascending run of length 1). By contrast an increasing subsequence of a permutation is not necessarily contiguous: it is an increasing sequence obtained by omitting some of the values of the one-line notation. For example, the permutation 2453167 has the ascending runs 245, 3, and 167, while it has an increasing subsequence 2367.

If a permutation has k − 1 descents, then it must be the union of k ascending runs.

The number of permutations of n with k ascents is (by definition) the Eulerian number $$\textstyle\left\langle{n\atop k}\right\rangle$$; this is also the number of permutations of n with k descents. Some authors however define the Eulerian number $$\textstyle\left\langle{n\atop k}\right\rangle$$ as the number of permutations with k ascending runs, which corresponds to $k − 1$ descents.

An exceedance of a permutation σ1σ2...σn is an index j such that $σ_{j} > j$. If the inequality is not strict (that is, $σ_{j} ≥ j$), then j is called a weak exceedance. The number of n-permutations with k exceedances coincides with the number of n-permutations with k descents.

A record or left-to-right maximum of a permutation σ is an element i such that σ(j) < σ(i) for all j < i.

Foata's transition lemma
Foata's fundamental bijection transforms a permutation $$\sigma $$ with a given canonical cycle form into the permutation $$f(\sigma) = \hat\sigma   $$ whose one-line notation has the same sequence of elements with parentheses removed. For example: $$\sigma = (513)(6)(827)(94) = \begin{pmatrix} 1&2&3&4&5&6&7&8&9\\ 3&7&5&9&1&6&8&2&4 \end{pmatrix},

$$

$$\hat\sigma = 513682794 = \begin{pmatrix} 1&2&3&4&5&6&7&8&9\\ 5&1&3&6&8&2&7&9&4 \end{pmatrix}.

$$ Here the first element in each canonical cycle of $$\sigma $$ becomes a record (left-to-right maximum) of $$\hat\sigma

$$. Given $$\hat\sigma

$$, one may find its records and insert parentheses to construct the inverse transformation $$\sigma=f^{-1}(\hat\sigma)

$$. Underlining the records in the above example: $$\hat\sigma = \underline{5}\, 1\, 3\, \underline{6}\, \underline{8}\,2\,7\,\underline{9}\,4

$$, which allows the reconstruction of the cycles of $$\sigma $$.

The following table shows $$\hat\sigma $$ and $$\sigma  $$ for the six permutations of S = {1, 2, 3}, with the bold text on each side showing the notation used in the bijection: one-line notation for $$\hat\sigma  $$ and canonical cycle notation for $$\sigma  $$.

As a first corollary, the number of n-permutations with exactly k records is equal to the number of n-permutations with exactly k cycles: this last number is the signless Stirling number of the first kind, $$c(n, k)$$. Furthermore, Foata's mapping takes an n-permutation with k weak exceedances to an n-permutation with $k − 1$ ascents. For example, (2)(31) = 321 has k = 2 weak exceedances (at index 1 and 2), whereas $f(321) = 231$ has $k − 1 = 1$ ascent (at index 1; that is, from 2 to 3).

Inversions

An inversion of a permutation σ is a pair $(i, j)$ of positions where the entries of a permutation are in the opposite order: $$i < j$$ and $$\sigma(i)> \sigma(j)$$. Thus a descent is an inversion at two adjacent positions. For example, $σ = 23154$ has (i, j) = (1, 3), (2, 3), and (4, 5), where (σ(i), σ(j)) = (2, 1), (3, 1), and (5, 4).

Sometimes an inversion is defined as the pair of values (σ(i), σ(j)); this makes no difference for the number of inversions, and the reverse pair (σ(j), σ(i)) is an inversion in the above sense for the inverse permutation σ−1.

The number of inversions is an important measure for the degree to which the entries of a permutation are out of order; it is the same for σ and for σ−1. To bring a permutation with k inversions into order (that is, transform it into the identity permutation), by successively applying (right-multiplication by) adjacent transpositions, is always possible and requires a sequence of k such operations. Moreover, any reasonable choice for the adjacent transpositions will work: it suffices to choose at each step a transposition of i and $i + 1$ where i is a descent of the permutation as modified so far (so that the transposition will remove this particular descent, although it might create other descents). This is so because applying such a transposition reduces the number of inversions by 1; as long as this number is not zero, the permutation is not the identity, so it has at least one descent. Bubble sort and insertion sort can be interpreted as particular instances of this procedure to put a sequence into order. Incidentally this procedure proves that any permutation σ can be written as a product of adjacent transpositions; for this one may simply reverse any sequence of such transpositions that transforms σ into the identity. In fact, by enumerating all sequences of adjacent transpositions that would transform σ into the identity, one obtains (after reversal) a complete list of all expressions of minimal length writing σ as a product of adjacent transpositions.

The number of permutations of n with k inversions is expressed by a Mahonian number. This is the coefficient of $$q^k$$ in the expansion of the product

$$[n]_q! = \prod_{m=1}^n\sum_{i=0}^{m-1}q^i = 1 \left(1 + q\right)\left(1 + q + q^2\right) \cdots \left(1 + q + q^2 + \cdots + q^{n-1}\right),$$

The notation $$[n]_q!$$ denotes the q-factorial. This expansion commonly appears in the study of necklaces.

Let $$\sigma \in S_n, i, j\in \{1, 2, \dots, n\} $$ such that $$i\sigma(j)$$. In this case, say the weight of the inversion $$(i, j)$$ is $$\sigma(i)-\sigma(j)$$. Kobayashi (2011) proved the enumeration formula $$\sum_{i\sigma(j)}(\sigma(i)-\sigma(j)) = |\{\tau \in S_n \mid \tau\le \sigma, \tau \text{ is bigrassmannian}\}$$

where $$\le$$ denotes Bruhat order in the symmetric groups. This graded partial order often appears in the context of Coxeter groups.

Numbering permutations
One way to represent permutations of n things is by an integer N with 0 ≤ N < n!, provided convenient methods are given to convert between the number and the representation of a permutation as an ordered arrangement (sequence). This gives the most compact representation of arbitrary permutations, and in computing is particularly attractive when n is small enough that N can be held in a machine word; for 32-bit words this means n ≤ 12, and for 64-bit words this means n ≤ 20. The conversion can be done via the intermediate form of a sequence of numbers dn, dn−1, ..., d2, d1, where di is a non-negative integer less than i (one may omit d1, as it is always 0, but its presence makes the subsequent conversion to a permutation easier to describe). The first step then is to simply express N in the factorial number system, which is just a particular mixed radix representation, where, for numbers less than n!, the bases (place values or multiplication factors) for successive digits are $(n − 1)!$, $(n − 2)!$, ..., 2!, 1!. The second step interprets this sequence as a Lehmer code or (almost equivalently) as an inversion table.

In the Lehmer code for a permutation σ, the number dn represents the choice made for the first term σ1, the number dn−1 represents the choice made for the second term σ2 among the remaining $n − 1$ elements of the set, and so forth. More precisely, each dn+1−i gives the number of remaining elements strictly less than the term σi. Since those remaining elements are bound to turn up as some later term σj, the digit dn+1−i counts the inversions (i,j) involving i as smaller index (the number of values j for which i < j and σi > σj). The inversion table for σ is quite similar, but here dn+1−k counts the number of inversions (i,j) where k = σj occurs as the smaller of the two values appearing in inverted order.

Both encodings can be visualized by an n by n Rothe diagram (named after Heinrich August Rothe) in which dots at (i,σi) mark the entries of the permutation, and a cross at (i,σj) marks the inversion (i,j); by the definition of inversions a cross appears in any square that comes both before the dot (j,σj) in its column, and before the dot (i,σi) in its row. The Lehmer code lists the numbers of crosses in successive rows, while the inversion table lists the numbers of crosses in successive columns; it is just the Lehmer code for the inverse permutation, and vice versa.

To effectively convert a Lehmer code dn, dn−1, ..., d2, d1 into a permutation of an ordered set S, one can start with a list of the elements of S in increasing order, and for i increasing from 1 to n set σi to the element in the list that is preceded by dn+1−i other ones, and remove that element from the list. To convert an inversion table dn, dn−1, ..., d2, d1 into the corresponding permutation, one can traverse the numbers from d1 to dn while inserting the elements of S from largest to smallest into an initially empty sequence; at the step using the number d from the inversion table, the element from S inserted into the sequence at the point where it is preceded by d elements already present. Alternatively one could process the numbers from the inversion table and the elements of S both in the opposite order, starting with a row of n empty slots, and at each step place the element from S into the empty slot that is preceded by d other empty slots.

Converting successive natural numbers to the factorial number system produces those sequences in lexicographic order (as is the case with any mixed radix number system), and further converting them to permutations preserves the lexicographic ordering, provided the Lehmer code interpretation is used (using inversion tables, one gets a different ordering, where one starts by comparing permutations by the place of their entries 1 rather than by the value of their first entries). The sum of the numbers in the factorial number system representation gives the number of inversions of the permutation, and the parity of that sum gives the signature of the permutation. Moreover, the positions of the zeroes in the inversion table give the values of left-to-right maxima of the permutation (in the example 6, 8, 9) while the positions of the zeroes in the Lehmer code are the positions of the right-to-left minima (in the example positions the 4, 8, 9 of the values 1, 2, 5); this allows computing the distribution of such extrema among all permutations. A permutation with Lehmer code dn, dn−1, ..., d2, d1 has an ascent $n − i$ if and only if $d_{i} ≥ d_{i+1}$.

Algorithms to generate permutations
In computing it may be required to generate permutations of a given sequence of values. The methods best adapted to do this depend on whether one wants some randomly chosen permutations, or all permutations, and in the latter case if a specific ordering is required. Another question is whether possible equality among entries in the given sequence is to be taken into account; if so, one should only generate distinct multiset permutations of the sequence.

An obvious way to generate permutations of n is to generate values for the Lehmer code (possibly using the factorial number system representation of integers up to n!), and convert those into the corresponding permutations. However, the latter step, while straightforward, is hard to implement efficiently, because it requires n operations each of selection from a sequence and deletion from it, at an arbitrary position; of the obvious representations of the sequence as an array or a linked list, both require (for different reasons) about n2/4 operations to perform the conversion. With n likely to be rather small (especially if generation of all permutations is needed) that is not too much of a problem, but it turns out that both for random and for systematic generation there are simple alternatives that do considerably better. For this reason it does not seem useful, although certainly possible, to employ a special data structure that would allow performing the conversion from Lehmer code to permutation in O(n log n) time.

Random generation of permutations
For generating random permutations of a given sequence of n values, it makes no difference whether one applies a randomly selected permutation of n to the sequence, or chooses a random element from the set of distinct (multiset) permutations of the sequence. This is because, even though in case of repeated values there can be many distinct permutations of n that result in the same permuted sequence, the number of such permutations is the same for each possible result. Unlike for systematic generation, which becomes unfeasible for large n due to the growth of the number n!, there is no reason to assume that n will be small for random generation.

The basic idea to generate a random permutation is to generate at random one of the n! sequences of integers d1,d2,...,dn satisfying $0 ≤ d_{i} < i$ (since d1 is always zero it may be omitted) and to convert it to a permutation through a bijective correspondence. For the latter correspondence one could interpret the (reverse) sequence as a Lehmer code, and this gives a generation method first published in 1938 by Ronald Fisher and Frank Yates. While at the time computer implementation was not an issue, this method suffers from the difficulty sketched above to convert from Lehmer code to permutation efficiently. This can be remedied by using a different bijective correspondence: after using di to select an element among i remaining elements of the sequence (for decreasing values of i), rather than removing the element and compacting the sequence by shifting down further elements one place, one swaps the element with the final remaining element. Thus the elements remaining for selection form a consecutive range at each point in time, even though they may not occur in the same order as they did in the original sequence. The mapping from sequence of integers to permutations is somewhat complicated, but it can be seen to produce each permutation in exactly one way, by an immediate induction. When the selected element happens to be the final remaining element, the swap operation can be omitted. This does not occur sufficiently often to warrant testing for the condition, but the final element must be included among the candidates of the selection, to guarantee that all permutations can be generated.

The resulting algorithm for generating a random permutation of  can be described as follows in pseudocode:

for i from n downto 2 do di ← random element of { 0, ..., i − 1 } swap a[di] and a[i − 1]

This can be combined with the initialization of the array  as follows

for i from 0 to n−1 do di+1 ← random element of { 0, ..., i } a[i] ← a[di+1] a[di+1] ← i

If di+1 = i, the first assignment will copy an uninitialized value, but the second will overwrite it with the correct value i.

However, Fisher-Yates is not the fastest algorithm for generating a permutation, because Fisher-Yates is essentially a sequential algorithm and "divide and conquer" procedures can achieve the same result in parallel.

Generation in lexicographic order
There are many ways to systematically generate all permutations of a given sequence. One classic, simple, and flexible algorithm is based upon finding the next permutation in lexicographic ordering, if it exists. It can handle repeated values, for which case it generates each distinct multiset permutation once. Even for ordinary permutations it is significantly more efficient than generating values for the Lehmer code in lexicographic order (possibly using the factorial number system) and converting those to permutations. It begins by sorting the sequence in (weakly) increasing order (which gives its lexicographically minimal permutation), and then repeats advancing to the next permutation as long as one is found. The method goes back to Narayana Pandita in 14th century India, and has been rediscovered frequently.

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

For example, given the sequence [1, 2, 3, 4] (which is in increasing order), and given that the index is zero-based, the steps are as follows: Following this algorithm, the next lexicographic permutation will be [1, 3, 2, 4], and the 24th permutation will be [4, 3, 2, 1] at which point a[k] < a[k + 1] does not exist, indicating that this is the last permutation.
 * 1) Find the largest index k such that $a[k] < a[k + 1]$.  If no such index exists, the permutation is the last permutation.
 * 2) Find the largest index l greater than k such that $a[k] < a[l]$.
 * 3) Swap the value of a[k] with that of a[l].
 * 4) Reverse the sequence from a[k + 1] up to and including the final element a[n].
 * 1) Index k = 2, because 3 is placed at an index that satisfies condition of being the largest index that is still less than a[k + 1] which is 4.
 * 2) Index l = 3, because 4 is the only value in the sequence that is greater than 3 in order to satisfy the condition a[k] < a[l].
 * 3) The values of a[2] and a[3] are swapped to form the new sequence [1, 2, 4, 3].
 * 4) The sequence after k-index a[2] to the final element is reversed. Because only one value lies after this index (the 3), the sequence remains unchanged in this instance. Thus the lexicographic successor of the initial state is permuted: [1, 2, 4, 3].

This method uses about 3 comparisons and 1.5 swaps per permutation, amortized over the whole sequence, not counting the initial sort.

Generation with minimal changes
An alternative to the above algorithm, the Steinhaus–Johnson–Trotter algorithm, generates an ordering on all the permutations of a given sequence with the property that any two consecutive permutations in its output differ by swapping two adjacent values. This ordering on the permutations was known to 17th-century English bell ringers, among whom it was known as "plain changes". One advantage of this method is that the small amount of change from one permutation to the next allows the method to be implemented in constant time per permutation. The same can also easily generate the subset of even permutations, again in constant time per permutation, by skipping every other output permutation.

An alternative to Steinhaus–Johnson–Trotter is Heap's algorithm, said by Robert Sedgewick in 1977 to be the fastest algorithm of generating permutations in applications.

The following figure shows the output of all three aforementioned algorithms for generating all permutations of length $$n=4$$, and of six additional algorithms described in the literature.

 * 1) Lexicographic ordering;
 * 2) Steinhaus–Johnson–Trotter algorithm;
 * 3) Heap's algorithm;
 * 4) Ehrlich's star-transposition algorithm: in each step, the first entry of the permutation is exchanged with a later entry;
 * 5) Zaks' prefix reversal algorithm: in each step, a prefix of the current permutation is reversed to obtain the next permutation;
 * 6) Sawada-Williams' algorithm: each permutation differs from the previous one either by a cyclic left-shift by one position, or an exchange of the first two entries;
 * 7) Corbett's algorithm: each permutation differs from the previous one by a cyclic left-shift of some prefix by one position;
 * 8) Single-track ordering: each column is a cyclic shift of the other columns;
 * 9) Single-track Gray code: each column is a cyclic shift of the other columns, plus any two consecutive permutations differ only in one or two transpositions.
 * 10) Nested swaps generating algorithm in steps connected to the nested subgroups $$S_k\subset S_{k+1}$$. Each permutation is obtained from the previous by a transposition multiplication to the left. Algorithm is connected to the Factorial_number_system of the index.

Generation of permutations in nested swap steps
Explicit sequence of swaps (transpositions, 2-cycles $$(pq)$$), is described here, each swap applied (on the left) to the previous chain providing a new permutation, such that all the permutations can be retrieved, each only once. This counting/generating procedure has an additional structure (call it nested), as it is given in steps: after completely retrieving $$S_{k-1}$$, continue retrieving $$S_{k}\backslash S_{k-1}$$ by cosets $$S_{k-1}\tau_i$$ of $$S_{k-1}$$ in $$S_k$$, by appropriately choosing the coset representatives $$\tau_i$$ to be described below. Note that, since each $$S_m$$ is sequentially generated, there is a last element $$\lambda_m\in S_m$$. So, after generating $$S_{k-1}$$ by swaps, the next permutation in $$S_{k}\backslash S_{k-1}$$ has to be $$\tau_1=(p_1k)\lambda_{k-1}$$ for some $$1\leq p_1<k$$. Then all swaps that generated $$S_{k-1}$$ are repeated, generating the whole coset $$S_{k-1}\tau_1$$, reaching the last permutation in that coset $$\lambda_{k-1}\tau_1$$; the next swap has to move the permutation to representative of another coset $$\tau_2=(p_2k)\lambda_{k-1}\tau_1$$.

Continuing the same way, one gets coset representatives $$\tau_j=(p_{j}k)\lambda_{k-1}\cdots \lambda_{k-1}(p_{i}k)\lambda_{k-1}\cdots\lambda_{k-1}(p_{1}k)\lambda_{k-1}$$ for the cosets of $$S_{k-1}$$ in $$S_k$$; the ordered set $$(p_1,\ldots, p_{k-1})$$ ($$0\leq p_ij>i\geq 1$$, $$(\lambda_{k-1})^{j-i}p_{i}\neq p_j$$ (no repeat condition). In particular, for all generated permutations to be distinct it is not necessary for the $$p_i$$ values to be distinct. In the process, one gets that $$\lambda_k=\lambda_{k-1}(p_{k-1}k)\lambda_{k-1}(p_{k-2}k)\lambda_{k-1}\cdots\lambda_{k-1}(p_{1}k)\lambda_{k-1}$$ and this provides the recursion procedure.

EXAMPLES: obviously, for $$\lambda_2$$ one has $$\lambda_2=(12)$$; to build $$\lambda_3$$ there are only two possibilities for the coset beginnings satisfying the no repeat condition; the choice $$ p_1=p_2=1$$ leads to $$\lambda_3=\lambda_2(13)\lambda_2(13)\lambda_2=(13)$$. To continue generating $$S_4$$ one needs appropriate coset beginnings (satisfying the no repeat condition): there is a convenient choice: $$p_1=1, p_2=2, p_3=3$$, leading to  $$\lambda_4=(13)(1234)(13)=(1432)$$. Then, to build $$\lambda_5$$ a convenient choice for the coset beginnings (satisfying the no repeat condition) is $$ p_1=p_2=p_3=p_4=1$$, leading to $$\lambda_5=(15)$$.

From examples above one can inductively go to higher $$k$$ in a similar way, choosing coset beginnings of $$S_{k}$$ in $$S_{k+1}$$, as follows: for $$k$$ even choosing all coset beginnings equal to 1 and for $$k$$ odd choosing coset beginnings equal to $$(1, 2,\dots, k)$$. With such choices the "last" permutation is $$\lambda_k=(1k)$$ for $$k$$ odd and $$\lambda_k=(1k_-)(12\cdots k)(1k_-)$$ for $$k$$ even ($$k_-=k-1$$). Using these explicit formulae one can easily compute the permutation of certain index in the counting/generation steps with minimum computation. For this, writing the index in factorial base is useful. For example, the permutation for index $$699=5(5!)+4(4!)+1(2!)+1(1!)$$ is: $$\sigma=\lambda_2(13)\lambda_2(15)\lambda_4(15)\lambda_4(15)\lambda_4(15)\lambda_4(56)\lambda_5(46)\lambda_5(36)\lambda_5(26)\lambda_5(16)\lambda_5=$$ $$\lambda_2(13)\lambda_2((15)\lambda_4)^4(\lambda_5)^{-1}\lambda_6=(23)(14325)^{-1}(15)(15)(123456)(15)=$$$$(23)(15234)(123456)(15)$$, yelding finally, $$\sigma=(1653)(24)$$.

Because multiplying by swap permutation takes  short computing time and every new generated permutation requires only one such swap multiplication, this generation procedure is quite efficient. Moreover as there is a simple formula, having the last permutation in each $$S_k$$ can save even more time to go directly to a permutation with certain index in fewer steps than expected as it can be done in blocks of subgroups rather than swap by swap.

Applications
Permutations are used in the interleaver component of the error detection and correction algorithms, such as turbo codes, for example 3GPP Long Term Evolution  mobile telecommunication standard uses these ideas (see 3GPP technical specification 36.212 ). Such applications raise the question of fast generation of permutations satisfying certain desirable properties. One of the methods is based on the permutation polynomials. Also as a base for optimal hashing in Unique Permutation Hashing.

title: Permutation


text:
National Security Advisor (United States)

The Assistant to the President for National Security Affairs (APNSA), commonly referred to as the National Security Advisor (NSA), is a senior aide in the Executive Office of the President, based at the West Wing of the White House. The national security advisor serves as the principal advisor to the President of the United States on all national security issues. The national security advisor participates in meetings of the National Security Council (NSC) and usually chairs meetings of the Principals Committee of the NSC with the Secretary of State and Secretary of Defense (those meetings not attended by the president). The NSA also sits on the Homeland Security Council (HSC). The national security advisor is supported by NSC staff who produce classified research and briefings for the national security advisor to review and present, either to the NSC or the president. The national security advisor is appointed by the president and does not require confirmation by the United States Senate. An appointment of a three- or four-star general to the role requires Senate confirmation to maintain that rank in the new position.

Role
The influence and role of the national security advisor varies from administration to administration and depends not only on the qualities of the person appointed to the position, but also on the style and management philosophy of the incumbent president. Ideally, the national security advisor serves as an honest broker of policy options for the president in the field of national security, rather than as an advocate for his or her own policy agenda.

The national security advisor is a staff position in the Executive Office of the President and does not have line or budget authority over either the Department of State or the Department of Defense, unlike the secretary of state and the secretary of defense, who are Senate-confirmed officials with statutory authority over their departments. The national security advisor is able to offer daily advice (due to the proximity) to the president independently of the vested interests of the large bureaucracies and clientele of those departments.

In times of crisis, the national security advisor is likely to operate from the White House Situation Room or the Presidential Emergency Operations Center (as on September 11, 2001), updating the president on the latest events in a crisis situation.

History
The National Security Council was created at the start of the Cold War under the National Security Act of 1947 to coordinate defense, foreign affairs, international economic policy, and intelligence; this was part of a large reorganization that saw the creation of the Department of Defense and the Central Intelligence Agency. The Act did not create the position of the national security advisor per se, but it did create an executive secretary in charge of the staff. In 1949, the NSC became part of the Executive Office of the President.

Robert Cutler was the first national security advisor in 1953, and held the job twice, both times during the Eisenhower administration. The system has remained largely unchanged since then, particularly since President John Kennedy, with powerful national security advisors and strong staff but a lower importance given to formal NSC meetings. This continuity persists despite the tendency of each new president to replace the advisor and senior NSC staff.

President Richard Nixon's national security advisor, Henry Kissinger, enhanced the importance of the role, controlling the flow of information to the president and meeting with him multiple times per day. Kissinger also holds the distinction of serving as national security advisor and secretary of state at the same time from September 22, 1973, until November 3, 1975. He holds the record for longest term of service (2,478 days); Michael Flynn holds the record for shortest term, at just 24 days.

Brent Scowcroft held the job in two non-consecutive administrations: the Ford administration and the George H. W. Bush administration.

List
{{legend|#E6E6AA|Denotes acting}}

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Executive Office of the President of the United States

The Executive Office of the President of the United States (EOP) comprises the offices and agencies that support the work of the president at the center of the executive branch of the United States federal government. The office consists of several offices and agencies, such as the White House Office (the staff working closest with the president, including West Wing staff), the National Security Council, Homeland Security Council, Office of Management and Budget, council of Economic Advisers, and others. The Eisenhower Executive Office Building houses most staff.

The office is also referred to as a "permanent government", since many policy programs, and the people who are charged with implementing them, continue between presidential administrations.

The civil servants who work in the Executive Office of the President are regarded as nonpartisan and politically neutral, so they are capable of providing objective and impartial advice.

With the increase in technological and global advancement, the size of the White House staff has increased to include an array of policy experts responsible with managing various federal governmental functions and policy areas. As of 2015, it included approximately 1,800 positions, most of which did not require confirmation from the U.S. Senate.

The office is overseen by the White House chief of staff. Since February 8, 2023, that position has been held by Jeff Zients, who was appointed by President Joe Biden.

History
In 1937, the Brownlow Committee, which was a presidentially commissioned panel of political science and public administration experts, recommended sweeping changes to the executive branch of the U.S. federal government, including the creation of the Executive Office of the President. Based on these recommendations, President Franklin D. Roosevelt in 1939 lobbied Congress to approve the Reorganization Act of 1939. The Act led to Reorganization Plan No. 1, which created the office, which reported directly to the president.

The office encompassed two subunits at its outset, the White House Office (WHO) and the Bureau of the Budget, the predecessor to today's Office of Management and Budget, which was created in 1921 and originally located in the Treasury Department. It absorbed most of the functions of the National Emergency Council. Initially, the new staff system appeared more ambitious on paper than in practice; the increase in the size of the staff was quite modest at the start. However, it laid the groundwork for the large and organizationally complex White House staff that emerged during the presidencies of Roosevelt's successors.

Roosevelt's efforts are also notable in contrast to those of his predecessors in office. During the 19th century, presidents had few staff resources. Thomas Jefferson had one messenger and one secretary at his disposal, both of whose salaries were paid by the president personally. It was not until 1857 that Congress appropriated money ($2,500) for the hiring of one clerk.

By Ulysses S. Grant's presidency (1869–1877), the staff had grown to three. By 1900, the White House staff included one "secretary to the president" (then the title of the president's chief aide), two assistant secretaries, two executive clerks, a stenographer, and seven other office personnel. Under Warren G. Harding, there were thirty-one staff, although most were clerical positions.

During Herbert Hoover's presidency, two additional secretaries to the president were added by Congress, one of whom Hoover designated as his press secretary. From 1933 to 1939, as he greatly expanded the scope of the federal government's policies and powers in response to the Great Depression, Roosevelt relied on his "brain trust" of top advisers, who were often appointed to vacant positions in agencies and departments, from which they drew their salaries, since the White House lacked statutory or budgetary authority to create new staff positions.

After World War II, in particular during the Eisenhower presidency, the staff was expanded and reorganized. Eisenhower, a former U.S. Army general, had been Supreme Allied Commander during the war, and reorganized the Executive Office to suit his leadership style.

Today, the staff is much bigger. Estimates indicate some 3,000 to 4,000 persons serve in office staff positions with policy-making responsibilities, with a budget of $300 to $400 million (George W. Bush's budget request for Fiscal Year 2005 was for $341 million in support of 1,850 personnel).

Some observers have noted a problem of control for the president due to the increase in staff and departments, making coordination and cooperation between the various departments of the Executive Office more difficult.

Organization
The president had the power to reorganize the Executive Office due to the 1949 Reorganization Act which gave the president considerable discretion, until 1983 when it was renewed due to President Reagan's administration allegedly encountering "disloyalty and obstruction".

The chief of staff is the head of the Executive Office and can therefore ultimately decide what the president needs to deal with personally and what can be dealt with by other staff.

Senior staff within the Executive Office of the President have the title Assistant to the President, second-level staff have the title Deputy Assistant to the President, and third-level staff have the title Special Assistant to the President.

The core White House staff appointments, and most Executive Office officials generally, are not required to be confirmed by the U.S. Senate, although there are a handful of exceptions (e.g., the director of the Office of Management and Budget, the chair of the Council of Economic Advisers, and the United States Trade Representative).

The information in the following table is current as of January 20, 2021. Only principal executives are listed; for subordinate officers, see individual office pages.

White House offices
The White House Office (including its various offices listed below ) is a sub-unit of the Executive Office of the President (office). The various agencies of the office are listed above.

 * Office of the Chief of Staff
 * Office of the National Security Advisor
 * Domestic Policy Council
 * National Economic Council
 * Office of Cabinet Affairs
 * Office of Digital Strategy
 * White House Office of Communications
 * Office of the First Lady
 * Office of Intergovernmental Affairs
 * Office of Legislative Affairs
 * Office of Management and Administration
 * Office of Political Affairs
 * Office of Public Engagement
 * Office of Presidential Personnel
 * Office of Scheduling and Advance
 * Office of the Staff Secretary
 * Office of White House Counsel
 * Oval Office Operations
 * White House Fellows
 * White House Military Office

Congress
Congress as well as the president has some control over the Executive Office of the President. Some of this authority stems from its appropriation powers given by the Constitution, such as the "power of the purse", which affects the Office of Management and Budget and the funding of the rest of federal departments and agencies. Congress also has the right to investigate the operation of the Executive Office, normally holding hearings bringing forward individual personnel to testify before a congressional committee.

The Executive Office often helps with legislation by filling in specific points understood and written by experts, as Congressional legislation sometimes starts in broad terms.

Budget history
This table specifies the budget of the Executive Office for the years 2008–2017, and the actual outlays for the years 1993–2007.


text:
Office of Management and Budget

The Office of Management and Budget (OMB) is the largest office within the Executive Office of the President of the United States (EOP). OMB's most prominent function is to produce the president's budget, but it also examines agency programs, policies, and procedures to see whether they comply with the president's policies and coordinates inter-agency policy initiatives.

Shalanda Young became OMB's acting director in March 2021, and was confirmed by the Senate in March 2022.

History
The Bureau of the Budget, OMB's predecessor, was established in 1921 as a part of the Department of the Treasury by the Budget and Accounting Act of 1921, which President Warren G. Harding signed into law. The Bureau of the Budget was moved to the Executive Office of the President in 1939 and was run by Harold D. Smith during the government's rapid expansion of spending during World War II. James L. Sundquist, a staffer at the Bureau of the Budget, called the relationship between the president and the bureau extremely close and subsequent bureau directors politicians, not public administrators.

The bureau was reorganized into the Office of Management and Budget in 1970 during the Nixon administration. The first OMB included Roy Ash (head), Paul O'Neill (assistant director), Fred Malek (deputy director), Frank Zarb (associate director) and two dozen others.

In the 1990s, OMB was reorganized to remove the distinction between management staff and budgetary staff by combining the dual roles into each given program examiner within the Resource Management Offices.

Purpose
OMB prepares the president's budget proposal to Congress and supervises the administration of the executive branch agencies. It evaluates the effectiveness of agency programs, policies, and procedures, assesses competing funding demands among agencies, and sets funding priorities. OMB ensures that agency reports, rules, testimony, and proposed legislation are consistent with the president's budget and administration policies.

OMB also oversees and coordinates the administration's procurement, financial management, information, and regulatory policies. In each of these areas, OMB's role is to help improve administrative management, develop better performance measures and coordinating mechanisms, and reduce unnecessary burdens on the public.

OMB's critical missions are:

 * 1) Budget development and execution, a prominent government-wide process managed from the Executive Office of the President (EOP) and a device by which a president implements their policies, priorities, and actions in everything from the Department of Defense to NASA.
 * 2) Managing other agencies' financials, paperwork, and IT.

Overview
OMB is made up mainly of career appointed staff who provide continuity across changes of party and administration in the White House. Six positions within OMB – the Director, the Deputy Director, the Deputy Director for Management, and the administrators of the Office of Information and Regulatory Affairs, the Office of Federal Procurement Policy, and the Office of Federal Financial Management – are presidentially appointed and Senate-confirmed positions.

OMB's largest components are the five Resource Management Offices, which are organized along functional lines mirroring the federal government, each led by an OMB associate director. Approximately half of all OMB staff are assigned to these offices, the majority of whom are designated as program examiners. Program examiners can be assigned to monitor one or more federal agencies or may be deployed by a topical area, such as monitoring issues relating to U.S. Navy warships. These staff have dual responsibility for both management and budgetary issues, as well as for giving expert advice on all aspects relating to their programs. Each year they review federal agency budget requests and help decide what resource requests will be sent to Congress as part of the president's budget. They perform in-depth program evaluations with the Program Assessment Rating Tool, review proposed regulations and agency testimony, analyze pending legislation, and oversee the aspects of the president's management agenda including agency management scorecards. They are often called upon to provide analysis information to EOP staff. They also provide important information to those assigned to the statutory offices within OMB: the Office of Information and Regulatory Affairs, the Office of Federal Procurement Policy, the Office of Federal Financial Management, and the Office of E-Government & Information Technology, which specializes in issues such as federal regulations and procurement policy and law.

Other components are OMB-wide support offices, including the Office of General Counsel, the Office of Legislative Affairs, the Budget Review Division (BRD), and the Legislative Reference Division. The BRD performs government-wide budget coordination and is largely responsible for the technical aspects relating to the release of the president's budget each February. With respect to the estimation of spending for the executive branch, the BRD serves a purpose parallel to that of the Congressional Budget Office (which was created in response to the OMB) for estimating Congressional spending, the Department of the Treasury for estimating executive branch revenue, and the Joint Committee on Taxation for estimating Congressional revenue.

The Legislative Reference Division is the federal government's central clearing house for proposed legislation or testimony by federal officials. It distributes proposed legislation and testimony to all relevant federal reviewers and distills the comments into a consensus opinion of the administration about the proposal. It is also responsible for writing an Enrolled Bill Memorandum to the president once a bill is presented by both chambers of Congress for the president's signature. The Enrolled Bill Memorandum details the bill's particulars, opinions on the bill from relevant federal departments, and an overall opinion about whether it should be signed into law or vetoed. It also issues Statements of Administration Policy that let Congress know the White House's official position on proposed legislation.

Role in the executive budget process
In practice, the president has assigned the OMB certain responsibilities when it comes to the budget and hiring authorities who play key roles in developing it. OMB coordinates the development of the president's budget proposal by issuing circulars, memoranda, and guidance documents to the heads of executive agencies. The OMB works very closely with executive agencies in making sure the budget process and proposal is smooth.

The development of the budget within the executive branch has many steps and takes nearly a year to complete. The first step is the OMB informing the president of the country's economic situation. The next step is known as the Spring Guidance: the OMB gives executive agencies instructions on policy guidance to use when coming up with their budget requests along with due dates for them to submit their requests. The OMB then works with the agencies to discuss issues in the upcoming budget. In July, the OMB issues circular A-11 to all agencies, which outlines instructions for submitting the budget proposals, which the agencies submit by September. The fiscal year begins October   1 and OMB staff meet with senior agency representatives to find out whether their proposals are in line with the president's priorities and policies and identify constraints within the budget proposal until late November. The OMB director then meets with the president and EOP advisors to discuss the agencies' budget proposals and recommends a federal budget proposal, and the agencies are notified of the decisions about their requests. They can appeal to OMB and the president in December if they are dissatisfied with the decisions. After working together to resolve issues, agencies and OMB prepare a budget justification document to present to relevant congressional committees, especially the Appropriations Committee. Finally, by the first Monday in February, the president must review and submit the final budget to Congress to approve.

OMB is also responsible for the preparation of Statements of Administrative Policy (SAPs) with the president. These statements allow the OMB to communicate the president's and agencies' policies to the government as a whole and set forth policymakers' agendas. During the review of the federal budget, interest groups can lobby for policy change and affect the budget for the new year. OMB plays a key role in policy conflicts by making sure legislation and agencies' actions are consistent with the executive branch's. OMB has a powerful and influential role in the government, basically making sure its day-to-day operations run. Without a budget, federal employees could not be paid, federal buildings could not open and federal programs would come to a halt in a government shutdown. Shutdowns can occur when Congress refuses to pass a budget.

Suspension and debarment
The Interagency Suspension and Debarment Committee (ISDC) was created as an OMB committee by President Ronald Reagan's Executive Order 12549 in 1986, for the purpose of monitoring the implementation of the order. This order mandates executive departments and agencies to:
 * participate in a government-wide suspension and debarment system,
 * issue regulations with government-wide criteria and minimum due process procedures when debarring or suspending participants, and
 * send debarred and suspended participants' identifying information to the General Services Administration for inclusion on a list of excluded persons, now known as the System for Award Management (SAM).

Circulars
Circulars are instructions or information the OMB issues to federal agencies that are indexed by major category: Budget, State and Local Governments, Educational and Non-Profit Institutions, Federal Procurement, Federal Financial Management, Federal Information Resources / Data Collection and Other Special Purpose.

Circular NO. A-119 Circular A-119 is for federal participation in the development and use of voluntary consensus standards and in conformity assessment activities. A-119 instructs its agencies to adopt voluntary consensus standards before relying upon industry standards and reducing to a minimum the reliance by agencies on government standards. Adoption of international standards is widely followed by U.S. agencies. This includes:
 * Environmental Protection Agency referencing ISO 14001 supporting public policy in environmental management
 * Department of Energy referencing ISO 50001 supporting public policy for energy performance aligned with the International Energy Agency
 * Department of Labor referencing ISO 45001 supporting public policy in occupational health and safety
 * Food and Drug Administration referencing ISO 13485 supporting public policy in medical devices
 * Food and Drug Administration referencing ISO 22000 supporting public policy in food products

Organization

 * Director of the Office of Management and Budget
 * Deputy Director, OMB
 * Executive Associate Director of OMB
 * Office of General Counsel
 * Office of Legislative Affairs
 * Office of Communications
 * Office of Economic Policy (EP)
 * Management and Operations Division
 * Legislative Reference Division
 * Budget Review Division (BRD)
 * Resource Management Offices
 * Natural Resource Programs
 * Education, Income Maintenance, and Labor Programs
 * Health Programs
 * General Government Programs
 * National Security Programs
 * Deputy Director for Management (Chief Performance Officer of the United States)
 * Office of Performance and Personnel Management (OPPM)
 * Office of Federal Financial Management (OFFM)
 * Office of Federal Procurement Policy (OFPP)
 * Office of E-Government & Information Technology (administrator: Federal Chief Information Officer of the United States)
 * Cyber and National Security Unit
 * United States Digital Service (USDS)
 * Office of Information and Regulatory Affairs (OIRA)
 * Office of the Intellectual Property Enforcement Coordinator (IPEC)

Current appointees

 * Director: Shalanda Young
 * Deputy Director: Nani Coloretti
 * Chief of Staff for OMB: Rachel Wallace
 * General Counsel: Daniel Jacobson
 * Deputy Director for Management (Chief Performance Officer of the United States): Jason Miller
 * Controller of the Office of Federal Financial Management: John Pasquantino (Acting)
 * Administrator of the Office of Federal Procurement Policy: Lesley Field (Acting)
 * Administrator of the Office of E-Government and Information Technology (Federal Chief Information Officer of the United States): Clare Martorana
 * Made in America Director: Livia Shmavonian
 * Administrator of the Office of Information and Regulatory Affairs: Ricky Revesz
 * Chief Statistician of the United States: Karin Orvis

List of directors
List of OMB directors.

title: Office of Management and Budget


text:
Perfect matching

In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph $G = (V, E)$, a perfect matching in $G$ is a subset $M$ of edge set $E$, such that every vertex in the vertex set $V$ is adjacent to exactly one edge in $M$.

A perfect matching is also called a 1-factor; see Graph factorization for an explanation of this term. In some literature, the term complete matching is used.

Every perfect matching is a maximum-cardinality matching, but the opposite is not true. For example, consider the following graphs:

 * [[File:Maximum-matching-labels.svg]]

In graph (b) there is a perfect matching (of size 3) since all 6 vertices are matched; in graphs (a) and (c) there is a maximum-cardinality matching (of size 2) which is not perfect, since some vertices are unmatched.

A perfect matching is also a minimum-size edge cover. If there is a perfect matching, then both the matching number and the edge cover number equal $|V| / 2$.

A perfect matching can only occur when the graph has an even number of vertices. A near-perfect matching is one in which exactly one vertex is unmatched. This can only occur when the graph has an odd number of vertices, and such a matching must be maximum. In the above figure, part (c) shows a near-perfect matching. If, for every vertex in a graph, there is a near-perfect matching that omits only that vertex, the graph is also called factor-critical.

Characterizations
Hall's marriage theorem provides a characterization of bipartite graphs which have a perfect matching.

The Tutte theorem provides a characterization for arbitrary graphs.

A perfect matching is a spanning 1-regular subgraph, a.k.a. a 1-factor. In general, a spanning k-regular subgraph is a k-factor.

A spectral characterization for a graph to have a perfect matching is given by Hassani Monfared and Mallik as follows: Let $$G$$ be a graph on even $$n$$ vertices and $$\lambda_1 > \lambda_2 > \ldots > \lambda_{\frac{n}{2}}>0$$ be $$\frac{n}{2}$$ distinct nonzero purely imaginary numbers. Then $$G$$ has a perfect matching if and only if there is a real skew-symmetric matrix $$A$$ with graph $$G$$ and eigenvalues $$\pm \lambda_1, \pm\lambda_2,\ldots,\pm\lambda_{\frac{n}{2}}$$. Note that the (simple) graph of a real symmetric or skew-symmetric matrix $$A$$ of order $$n$$ has $$n$$ vertices and edges given by the nonzero off-diagonal entries of $$A$$.

Computation
Deciding whether a graph admits a perfect matching can be done in polynomial time, using any algorithm for finding a maximum cardinality matching.

However, counting the number of perfect matchings, even in bipartite graphs, is #P-complete. This is because computing the permanent of an arbitrary 0–1 matrix (another #P-complete problem) is the same as computing the number of perfect matchings in the bipartite graph having the given matrix as its biadjacency matrix.

A remarkable theorem of Kasteleyn states that the number of perfect matchings in a planar graph can be computed exactly in polynomial time via the FKT algorithm.

The number of perfect matchings in a complete graph Kn (with n even) is given by the double factorial: $$(n-1)!!$$

Connection to Graph Coloring
An edge-colored graph can induce a number of (not necessarily proper) vertex colorings equal to the number of perfect matchings, as every vertex is covered exactly once in each matching. This property has been investigated in quantum physics and computational complexity theory.

Perfect matching polytope
The perfect matching polytope of a graph is a polytope in Rundefined in which each corner is an incidence vector of a perfect matching.

title: Perfect matching


text:
Corporation for Public Broadcasting

The Corporation for Public Broadcasting (CPB) is an American publicly funded non-profit corporation, created in 1967 to promote and help support public broadcasting. The corporation's mission is to ensure universal access to non-commercial, high-quality content and telecommunications services. It does so by distributing more than 70 percent of its funding to more than 1,400 locally owned public radio and television stations.

History
The Corporation for Public Broadcasting was created on November 7, 1967, when U.S. president Lyndon B. Johnson signed the Public Broadcasting Act of 1967. The new organization initially collaborated with the National Educational Television network—which would be replaced by the Public Broadcasting Service (PBS). Ward Chamberlin Jr. was the first operating officer. On March 27, 1968, it was registered as a nonprofit corporation in the District of Columbia. In 1969, the CPB talked to private groups to start PBS, an entity intended by the CPB to circumvent controversies engendered by certain NET public affairs programs that aired in the late 1960s and engendered opposition by politically conservative public figures, potentially threatening the medium's future viability.

On February 26, 1970, the CPB formed National Public Radio (NPR), a network of public-radio stations that began operating the following year. Unlike PBS, NPR produces and distributes programming. On May 31, 2002, the CPB, through special appropriation funding, helped public television stations making the transition to digital broadcasting; this was complete by 2009.

Funding of and by the corporation
The CPB's annual budget is composed almost entirely of an annual appropriation from Congress plus interest on those funds. CPB has claimed that 95% of its appropriation goes directly to content development, community services, and other local station and system needs.

For fiscal year 2014, its appropriation was US$445.5 million, including $500,000 in interest earned. The distribution of these funds was as follows:

 * $222.78M for direct grants to local public television stations;
 * $74.63M for television programming grants;
 * $69.31M for direct grants to local public radio stations;
 * $26.67M for PBS support;
 * $22.84M for grants for radio programming and national program production and acquisition;
 * $22.25M for CPB administrative costs;
 * $7.00M for the Radio Program Fund.

Public broadcasting stations are funded by a combination of private donations from listeners and viewers, foundations and corporations. Funding for public television comes in roughly equal parts from government (at all levels) and the private sector.

Stations that receive CPB funds must meet certain requirements, such as the maintenance or provision of open meetings, open financial records, a community advisory board, equal employment opportunity, and lists of donors and political activities.

Efforts to defund CPB in the US Congress
The CPB has had its congressional funding threatened a number of times, mostly by Republicans who think PBS had a left-wing bias. President Nixon was well known for his dislike of PBS and the CPB and wanted to kill the congressional funding for it. In July 2023, the appropriations bill for FY 2024 included zero money for CPB when it passed out of the US House Appropriations Subcommittee on Labor, Health and Human Services, Education, and Related Agencies However, the corresponding bill considered by the Senate Appropriations Committee plans to continue funding for the CPB, though at 7 percent less than what President Biden requested.

Board composition
The CPB is governed by a nine-member board of directors selected by the president of the United States and confirmed by the Senate; they serve six-year terms, and are allowed to continue serving until the end of the calendar year that their term ends or until their successor is seated on the board. , the board has nine members, with Laura Ross as the chair. Under the terms of the Public Broadcasting Act of 1967, the president cannot appoint persons of the same political party to more than five of the nine CPB board seats.

The Board of Directors governs CPB, sets policy, and establishes programming priorities. The Board appoints the president and chief executive officer, who then names the other corporate officers.

Political concerns
In 2004 and 2005, people from PBS and NPR complained that the CPB was starting to push a conservative agenda. Board members replied that they were merely seeking balance.

The charge of a conservative agenda came to a head in 2005. Kenneth Tomlinson, chair of the CPB board from September 2003 until September 2005, angered PBS and NPR supporters by unilaterally commissioning a conservative colleague to conduct a study of alleged bias in the PBS show NOW with Bill Moyers, and by appointing two conservatives as CPB Ombudsmen. On November 3, 2005, Tomlinson resigned from the board, prompted by a report of his tenure by the CPB Inspector General, Kenneth Konz, requested by Democrats in the U.S. House of Representatives. The report was made public on November 15. It states:

"We found evidence that the Corporation for Public Broadcasting (CPB) former Chairman violated statutory provisions and the Director's Code of Ethics by dealing directly with one of the creators of a new public affairs program during negotiations with the Public Broadcasting Service (PBS) and the CPB over creating the show. Our review also found evidence that suggests 'political tests' were a major criteria [sic] used by the former Chairman in recruiting a President/Chief Executive Officer (CEO) for CPB, which violated statutory prohibitions against such practices."

Objectivity and balance requirements
The Public Broadcasting Act of 1967 requires the CPB to operate with a "strict adherence to objectivity and balance in all programs or series of programs of a controversial nature". It also requires it to regularly review national programming for objectivity and balance, and to report on "its efforts to address concerns about objectivity and balance".

title: Corporation for Public Broadcasting