The Foata bijection for compositions.
The Foata bijection $\phi$ is a bijection on the set of words whose letters are positive integers. It can be defined by induction on the size of the word:
Given a word $w_1 w_2 ... w_n$, compute the image inductively by starting with $\phi(w_1) = w_1$.
At the $i$-th step, if $\phi(w_1 w_2 ... w_i) = v_1 v_2 ... v_i$, define $\phi(w_1 w_2 ... w_i w_{i+1})$ by placing $w_{i+1}$ on the end of the word $v_1 v_2 ... v_i$ and breaking the word up into blocks as follows.

• If $w_{i+1} \geq v_i$, place a vertical line to the right of each $v_k$ for which $w_{i+1} \geq v_k$.
• If $w_{i+1} < v_i$, place a vertical line to the right of each $v_k$ for which $w_{i+1} < v_k$.

In either case, place a vertical line at the start of the word as well. Now, within each block between vertical lines, cyclically shift the entries one place to the right.
To compute $\phi([1,4,2,5,3])$, the sequence of words is

• $1$
• $|1|4 \to 14$
• $|14|2 \to 412$
• $|4|1|2|5 \to 4125$
• $|4|125|3 \to 45123.$

In total, this gives $\phi([1,4,2,5,3]) = [4,5,1,2,3]$.
This bijection sends the major index St000769The major index of a composition regarded as a word. to the number of inversions St000766The number of inversions of an integer composition..

The threshold graph corresponding to the composition.
A threshold graph is a graph that can be obtained from the empty graph by adding successively isolated and dominating vertices.
A threshold graph is uniquely determined by its degree sequence.
The Laplacian spectrum of a threshold graph is integral. Interpreting it as an integer partition, it is the conjugate of the partition given by its degree sequence.

Return the partition of the sizes of the connected components of the graph.