permutations. Formally:
$\sum_! F(x[1], \dots, x[n]) \equiv \sum_{\sigma \in S_n} F(x[\sigma[1]], \dots, x[\sigma[n]])$

We write
$[a[1], \dots a[n]] \equiv 1/n! \sum_! x_1^{a[1]} \dots x[n]^{a[n]} = \sum_{\sigma \in S_n} \prod_{j} x[\sigma[j]]^{a[j]}$

For example,we have:
- $[1, 1] = 1/2! (xy + yx) = xy$
- $[1, 1, 1] = xyz$
- $[2, 1, 0] = 1/3! (x^2y + x^2z + y^2z + y^2x + z^2x + z^2 y)$
- $[1, 0, 0] = 1/3! (x^{[1, 0, 0']} + x^{[1, 0', 0]} + x^{[0, 1, 0']} + x^{[0', 1, 0]} + x^{[0, 0', 1]} + x^{[0', 0, 1]})$.This is equal to $2!(x + y + z)/3! = (x + y + z)/3$.
- In general, $[1, 0, 0, 0, \dots, 0]$ ($n$ zeroes) is $(n-1)!/n!(\sum_i x_i)$ which is the AM.
- Also, $[1/2, 1/2] = 1/2!(x^{1/2}y^{1/2} + y^{1/2}x^{1/2}) = \sqrt{xy}$.
- In general, $[1/n, 1/n, \dots, 1/n]$ is the GM $\sqrt{n}{x[1] x[2] \dots x[n]}$.

#### § Majorization

Let $(a), (b) \in \mathbb R^n$ be two non-decreasing sequences: $a[1] \geq a[2] \dots \geq a[n]$,
and $b[1] \geq b[2] \dots \geq b[n]$. We will say that $(b)$ is majorized by
$(a)$ (written as $(b) \prec (a)$) when we have that:
- $a[1] \geq a[2] \geq \dots a[n]$, $b[1] \geq b[2] \geq \dots b[n]$.
- $\sum_i b[i] = \sum_i a[i]$.
- $\sum_{i=1}^u b[i] \leq \sum_{i=1}^u a[i]$ for $1 \leq i \leq n$.

It is clear that this is a partial order. The below figure shows majorization
in terms of partitions. For two sequences $f, g$, define $F$ to be their "integral"
(partial sums) and $f', g'$ to be their "derivatives" (finite differences).
Then the condition that $f \prec g$ states that $F$ is upper bounded by $G$,
and that $F, G$ are concave functions.
The other lens of viewing majorization is to think of a number as some sort
of fixed length $l$, and we are allowed to make some progress to reach the goal
($f(x) > 0$) as long as we progress less at each each timestep ($f''(x) < 0$).
In this viewpoint, the majorization condition asserts that $f \prec g$ is that
$g$ will always be ahead of/not fall behind $f$.
#### § Majorization and step

We can show that if $(b) \prec (a)$ , then we can get from $(b)$ to $(a)$
in a finite number of discrete steps, that "borrow" from higherlocations in $b$
and "give" to lower locations. Formally, define a step operator $S(l, r)$ where
$l < r$ such that:
$S(l, r)(b)[k] =
\begin{cases}
b[l]+1 & k = l \\
b[r]-1 & k = r \\
b[k] & \texttt{otherwise}
\end{cases}$

That is, this borrows a single value from $b[j]$ and gives it to $b[i]$. We can see
that $(b) \prec S(l, r)(b)$.
For a given $(b) \prec (a)$, we can find a sequence of step operations
$S(l[i], r[i])$ such that we transform $(b)$ into $(a)$; That is, it is possible
to "single-step" the translation from $(b)$ to $(a)$.
#### § Muirhead's theorem statement

for non negative numbers $x[]$, we have:
$[b] \leq [a] \iff (b) \prec (a)$

Expanding it out, this means that:
$1/n! \sum_! x^{[b]} \leq 1/n! \sum_! x^{[a]} \iff (b) \prec (a) \\
\sum_! x^{[b]} \leq \sum_! x^{[a]} \iff (b) \prec (a) \\$