\section{Introduction}

The earth mover's distance (also known as the first Wasserstein distance) is a metric on a probability space.  Equivalently, and more historically, it can be regarded as the solution to a specialization of the Hitchcock transportation problem: what is the cheapest way to transport supplies among $n$ locations in order to meet each location's demand?  Both in a continuous setting (probability distributions on $\{1,\ldots,n\}$) and in a discrete setting (histograms with $n$ bins), the earth mover's distance has found an enormous range of modern applications, especially in image retrieval \cite{rubner}, physics \cite{komiske}, and even political science \cite{lupu}. 

In the discrete setting, we interpret this statistical metric in a purely combinatorial fashion: our main result (Theorem \ref{mainthm}) expresses the earth mover's distance as the symmetric difference of Young diagrams.  As a preview, consider the histograms $(2,0,2,4,0,0,0,1)$ and $(0,5,1,0,2,1,0,0)$; we claim that their earth mover's distance can be calculated as follows.  Encode each histogram's entries as tallies of ascending row-lengths in a Young diagram; then superimpose the two diagrams and count the size of their symmetric difference (i.e., their union minus their intersection):
$$
\ytableausetup{smalltableaux}\ytableausetup{centertableaux}
\text{Symmetric difference of} \quad \ydiagram[*(red!30!white)]{7,3,3,3,3,2,2,0,0} \text{and} \quad \ydiagram[*(blue!30!white)]{5,4,4,2,1,1,1,1,1} \text{is } \quad
\begin{ytableau}
\phantom{1}&\phantom{1} & \phantom{1}&\phantom{1} & \phantom{1}& *(red!30!white) \phantom{1}& *(red!30!white)\phantom{1}\\
\phantom{1}&\phantom{1} & \phantom{1}& *(blue!30!white) \phantom{1}\\
\phantom{1}&\phantom{1} & \phantom{1}& *(blue!30!white) \phantom{1}\\
\phantom{1} & \phantom{1}& *(red!30!white) \phantom{1}\\
\phantom{1} & *(red!30!white)\phantom{1}& *(red!30!white) \phantom{1}\\
\phantom{1} & *(red!30!white)\phantom{1}\\
\phantom{1} & *(red!30!white)\phantom{1}\\
*(blue!30!white)\phantom{1}\\
*(blue!30!white)\phantom{1}
\end{ytableau}
$$
In this case, the symmetric difference contains 11 boxes, and so the earth mover's distance is 11.  We find this method to be strikingly simple and conceptual, given the classical definition of the earth mover's distance which we review in Section \ref{ss:emcdef}.  The earth mover's distance can be naturally generalized to compare an arbitrary number of histograms (see \cite{a&p} and \cite{bein}), and our main result accounts for this full generality as well.  Hence from now on, rather than ``distance,'' we will refer to the earth mover's \textit{coefficient} (EMC) of a collection of histograms.

In the second part of the paper, we consider not only the EMC but also the averages of the histograms.  We compare these averages via the difference $\mathcal D$ of the weighted totals, and we determine (using only Young diagrams) the probability that $\EMC = \mathcal D$ in the \textit{continuous} setting.  (See Corollary \ref{cor:continuous}.)  This difference $\mathcal D$ can also be generalized to an arbitrary number $d$ of histograms, which raises the combinatorial question of counting $d$-tuples of histograms with a given $\mathcal D$-value.  We give a clean solution to this problem (Theorem  \ref{thm:character}) by showing that the answers are encoded as weight multiplicities in the character of a certain virtual representation of the Lie algebra $\sl(d,\mathbb C)$.

\subsection{Classical definition of EMC}
\label{ss:emcdef}
As context for our alternative approach to the EMC, we present its original definition in the language of transport theory (the ``Monge--Kantorovich problem'') and linear programming (the ``Hitchcock--Koopmans problem'').  We therefore consider the following $d$-dimensional discrete transportation problem.  This is a generalization of the two-dimensional problem which, in the literature, is named after various combinations of Hitchcock, Koopmans, Monge and Kantorovich (see \cite{bein}).

Let the (generalized) ``supply--demand vectors'' $\alpha_1,\ldots,\alpha_d$ be $n$-tuples of nonnegative integers.  Denote by $\alpha_i(j)$ the $j^{\rm th}$ entry of $\alpha_i$, and assume that $\sum_j \alpha_i(j)=s$ for all $i=1,\ldots,d$.  (In our context, we will regarded the $\alpha_i$ as histograms with $s$ data points and $n$ bins.)  Let $C$ (for ``cost'') be the $d$-dimensional, $n \times \cdots \times n$ array whose value at each position equals the taxicab distance from the main diagonal.  (If $d=2$, then $C$ is just the $n\times n$ matrix where $C(i,j)=|i-j|$.)  For a position vector $\mathbf x \in [n]^d = \{ (x_1,\ldots,x_d) \mid 1 \leq x_i \leq n \}$, we let $C(\mathbf x)$ denote the entry of $C$ in position $\mathbf x$.  The objective is to choose another $n \times \cdots \times n$ integer array $J$, in order to solve the following problem:
\begin{align}
    \text{Minimize} \quad & \sum_{\mathclap{\mathbf x \in [n]^d}} C(\mathbf x) J(\mathbf x), \nonumber \\
    \text{subject to} \quad & \sum_{\mathclap{\mathbf x \text{ such that } x_i = j}} J(\mathbf x) = \alpha_i(j) & \text{for } 1 \leq i \leq d \text{ and } 1 \leq j \leq n, \label{emcdef}\\
    \text{and} \quad & J(\mathbf x) \geq 0 & \text{for all } \mathbf x \in [n]^d. \nonumber
\end{align}
(Geometrically, the constraint on $J$ states that its hyperplane sums, in the direction perpendicular to the $i^{\rm th}$ standard basis vector, must match the entries in $\alpha_i$.  See Figure \ref{fig:cubes} to visualize this in the case $d=3$ and $n=5$.)  

\begin{figure}[h]
 
\begin{subfigure}[t]{0.32\textwidth}
\includegraphics[width=\linewidth]{Slide1.PNG} 
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.32\textwidth}
\includegraphics[width=\linewidth]{Slide2.PNG}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.32\textwidth}
\includegraphics[width=\linewidth]{Slide3.PNG}
\end{subfigure}
 
\caption{An illustration of the conditions on $J$ in the transport problem \eqref{emcdef} defining the EMC.  (Here $d=3$ and $n=5$.)  Each arrow represents the sum of the entries in the designated plane.}
\label{fig:cubes}
\end{figure}

The \textbf{earth mover's coefficient} (EMC) of the $\alpha_i$ is the minimum value of the objective function $\sum_\mathbf x C(\mathbf x) J(\mathbf x)$.  The intuition is this: imagine each $\alpha_i$ as a collection of $s$ pebbles, distributed among $n$ piles located at $1,\ldots,n$ on the number line, with $\alpha_i(j)$ pebbles in the $j^{\rm th}$ pile.  If a ``move'' consists in moving one pebble to a neighboring pile, then the EMC is the fewest number of moves required to equalize all of the $\alpha_i$.  (In this paper, we place the piles 1 unit apart because of the motivation from histograms; the most general version of this transport problem involves arbitrary distances between piles, which need not be collinear, in which case the cost array $C$ would look very different.)

Due to a special property of the cost array $C$ (known as the Monge property, which is essentially submodularity), the optimization problem \eqref{emcdef} can be solved in $O(d^2 n)$ time.  (See \cite{a&p}, \cite{bein}, and \cite{kline} for details behind this greedy algorithm known as the ``northwest corner rule.'')  Our approach in this paper, however, provides a simple combinatorial method to compute the EMC by counting boxes shared by Young diagrams corresponding to the $\alpha_i$.

\section{Combinatorial background}
\label{s:background}

\subsection{Integer compositions}   For $s,n \in \mathbb Z_{\geq 0}$, let $\mathcal C(s,n)$ denote the set of (weak) integer compositions of $s$ into $n$ parts.  In other words, a \textbf{composition}  $\alpha \in \mathcal C(s,n)$ is an $n$-tuple $(a_0,\ldots,a_{n-1})$ such that the $a_i$ are nonnegative integers summing to $s$. It is well known that $|\mathcal C(s,n)|=\binom{s+n-1}{s}=\binom{s+n-1}{n-1}$. From this point forward, we use a Greek letter for a composition and an indexed Roman letter for its integer entries; this will avoid confusion in cases when we must also index the compositions themselves as $\alpha_1,\ldots,\alpha_d$.  We will no longer use the $\alpha_i(j)$ notation from the introduction to denote a specific entry of a composition. (The reader is of course welcome to substitute the statistical term ``histogram,'' or the transportational term ``supply--demand vector,'' for the more combinatorial term ``composition.'') In light of this shift in perspective, we now regard the earth mover's coefficient as a function $\EMC:\mathcal C(s,n) \times \cdots \times \mathcal C(s,n) \longrightarrow \mathbb Z_{\geq 0}$ which measures, in some sense, the ``closeness'' of an arbitrary number of compositions.  When necessary, we use $d$ to denote the number of compositions being considered, so that $\mathcal C(s,n)^d$ denotes the Cartesian product of $d$ copies of $\mathcal C(s,n)$.  

\subsection{RSK algorithm to compute EMC}  
As a steppingstone to our main result, we present a streamlined algorithm which improves upon the northwest corner rule mentioned above, by calculating only the support of the optimal array $J$.  
This idea was introduced in \cite{bw} for the $d=2$ case, and generalized by this author for arbitrary $d$ in \cite{erickson}.  The following algorithm is, in thin disguise, a highly specialized application of the multivariate Robinson--Schensted--Knuth (RSK) correspondence; see \cite{stanley2}, Sections 7.11--14 for its full scope.

Let $\alpha=(a_0,\ldots,a_{n-1}) \in \mathcal C(s,n)$.  We define the \textbf{word} of $\alpha$ to be the sequence $w(\alpha)$ constructed by writing ``0'' $a_0$ times, then ``1'' $a_1$ times, and so on, ending with ``$n-1$'' written $a_{n-1}$ times:
\begin{equation*}
    w(\alpha)=(\underbrace{0,\ldots,0}_{a_0},\underbrace{1,\ldots,1}_{a_1},\ldots,\underbrace{n-1,\ldots,n-1}_{a_{n-1}}).
\end{equation*}
Hence $w(\alpha)$ is a weakly increasing sequence of length $s$, with elements from the set $\{0,\ldots,n-1\}$.  For example, $w(3,2,0,3,1)=(0,0,0,1,1,3,3,3,4)$.  In the pebble-pile imagery from above, a word is the sequence obtained by recording the location of each pebble from left to right.

Given compositions $\alpha_1,\ldots,\alpha_d$, we form the matrix 
\begin{equation}
\label{wordmatrix}
    M=M(\alpha_1,\ldots,\alpha_d)=\begin{bmatrix}
    w(\alpha_1)\\ 
    \vdots\\
    w(\alpha_d)
    \end{bmatrix}
\end{equation}
whose $i^{\rm th}$ row is the word $w(\alpha_i)$.  Then the  RSK correspondence takes this $d\times s$ matrix $M$ to a $d$-dimensional, $n\times \cdots\times n$ array $J$ as follows: 
\begin{enumerate}
    \item Start with $J$ as the array of all zeros;
    \item For each column vector of $M$, interpret that vector as the coordinates of an entry in $J$, and add 1 to that entry.
\end{enumerate}
In other words, the support of $J$ is the set of columns of $M$.  As the reader can easily check, the coordinate hyperplane sums in $J$ are given by the $\alpha_i$, and so $J$ satisfies the constraint in the transport problem \eqref{emcdef}.  Moreover, since words are nondecreasing, the support of $J$ is a \emph{chain}, in the sense that the position vectors of its support are pairwise comparable under the product order on $[n]^d$.  This fact, along with the Monge property of $C$, implies that $J$ truly is a solution of the transport problem \eqref{emcdef}.  (See \cite{bein} and \cite{erickson} for details.)

Now that we have an optimal array $J$, by definition we have $\EMC(\alpha_1\ldots,\alpha_d)=\sum_\mathbf x J(\mathbf x)C(\mathbf x)$.  Rather than sum over all array positions $\mathbf x$, however, we need only sum over the support of $J$, namely, the columns of $M$:
\begin{equation}
\label{shortemddef}
    \EMC(\alpha_1,\ldots,\alpha_d)=\sum_{j=1}^s C(M_{\bullet j}),
\end{equation}
where $M_{\bullet j}$ denotes the (transpose of the) $j$th column of $M$.  It remains to compute the cost $C(\mathbf x)$ for a given $d$-tuple $\mathbf x$.  The most convenient way to compute the taxicab distance between $\mathbf x$ and the main diagonal is to consider the ``sorted'' vector $\widetilde{\mathbf x}$, whose coordinates are those of $\mathbf x$ rearranged in ascending order; for instance, if $\mathbf x = (7,4,5,4,1)$, then $\widetilde{\mathbf x}=(1,4,4,5,7)$.

\begin{proposition} 
\label{cost}
Let $\mathbf x \in [n]^d$, with the sorted vector $\widetilde{\mathbf x}=(\widetilde x_1,\ldots,\widetilde x_d)$ as above.  Then $$\displaystyle C(\mathbf x)=\sum_{i=1}^{\lfloor d/2 \rfloor}
    \widetilde x_{d+1-i}-\widetilde x_{i.}$$
\end{proposition}

The proof is in \cite{erickson}, Section 3.  As an example, take $\mathbf x = (7,4,5,4,1)$ as above.  To compute $C(\mathbf x)$, we instead inspect $\widetilde{\mathbf x}$ and sum up the pairwise differences, working outside-in:
\begin{align*}
\widetilde{\mathbf x}&=(\overbrace{1,\overbrace{4,4,5}^{5-4=\mathbf{1}},7}^{7-1=\mathbf{6}}),\\
\text{therefore }C(\mathbf x)&=6+1\\
&=7.
\end{align*}

We conclude this subsection with a full example computing the EMC using the RSK algorithm.

\begin{example}
\label{rskexample}
Set $d=4$, $n=5$, and $s=6$.  We aim to compute the EMC of these  four compositions in $\mathcal C(6,5)$:
\begin{align*}
    \alpha &= (4,1,1,0,0),\\
    \beta &= (3,0,0,0,3),\\
    \gamma &= (0,4,2,0,0),\\
    \delta &= (1,1,2,1,1).
\end{align*}
We initiate the RSK algorithm outlined above by writing out the words
\begin{align*}
    w(\alpha)&=(0,0,0,0,1,2),\\
    w(\beta)&=(0,0,0,4,4,4),\\
    w(\gamma)&=(1,1,1,1,2,2),\\
    w(\delta)&=(0,1,2,2,3,4),
\end{align*}
which become the rows of the matrix
$$
M = 
\begin{bmatrix}
0&0&0&0&1&2\\
0&0&0&4&4&4\\
1&1&1&1&2&2\\
0&1&2&2&3&4
\end{bmatrix}_{\textstyle .}
$$
Using Proposition \ref{cost}, we compute the cost $C$ for each of the six columns of $M$:
\begin{align*}
    C(0,0,1,0) &= (1-0)+(0-0) = \mathbf{1},\\
    C(0,0,1,1) &= (1-0) + (1-0) = \mathbf{2},\\
    C(0,0,1,2) &= (2-0)+(1-2) = \mathbf{3},\\
    C(0,4,1,2) &= (4-0)+(2-1) = \mathbf{5},\\
    C(1,4,2,3) &= (4-1)+(3-2)=\mathbf{4},\\
    C(2,4,2,4) &= (4-2)+(4-2)=\mathbf{4}.
\end{align*}
Finally, summing these costs, we conclude
$$\EMC(\alpha,\beta,\gamma,\delta) = 1+2+3+5+4+4 = \mathbf{19}.$$
\end{example}

\subsection{Compositions as Young diagrams}  The main result of this paper is a reinterpretation of the EMC in terms of the ubiquitous combinatorial objects known as Young diagrams.  A \textbf{Young diagram} is a finite set of congruent square \textbf{cells} arranged in left-justified rows, with row lengths weakly decreasing from top to bottom.  Given a composition $\alpha \in \mathcal C(s,n)$, we can represent it uniquely as the Young diagram whose \emph{ascending} row lengths are given by the word $w(\alpha)$.  For example: 
$$
\alpha=(3,2,0,3,1) \Longrightarrow w(\alpha)=(0,0,0,1,1,3,3,3,4) \leadsto \ytableausetup{smalltableaux}\ytableausetup{centertableaux}\ydiagram{4,3,3,3,1,1}\vspace{10pt}
$$
since we draw the Young diagram from the bottom up, and 0's correspond to empty rows.
Because of this correspondence, we will often refer to a composition $\alpha$ as if it \textit{is} a Young diagram. Specifically, we write $|\alpha|$ to denote the \textbf{size} (number of cells) of the Young diagram of $\alpha$.  It is clear that if $\alpha$ is a composition, then
\begin{equation}
\label{sizeword}
|\alpha| \text{ is the sum of the entries in }w(\alpha).
\end{equation}

Note that if $\alpha \in \mathcal C(s,n)$, then as a Young diagram, $\alpha$ has at most $s$ rows, and each of those row lengths is at most $n-1$.  Thus we have a bijective correspondence
\begin{equation}
\label{compsdiagrams}
 \mathcal C(s,n) \longleftrightarrow \mathcal Y(s,\:n-1):=\left\{\quad\parbox{4.5cm}{\centering Young diagrams which fit \\inside an  $s\times (n-1)$ rectangle}\quad\right\}_{\textstyle .}
\end{equation}
By taking \textbf{conjugates} of Young diagrams (i.e., reflection across the main diagonal), we have the additional bijective correspondences:
\begin{equation}
\label{transpose}
\begin{array}{ccc}
    \mathcal C(s,n) & \longleftrightarrow & \quad \mathcal Y(s,\:n-1)  \\[1ex]
    \Big\updownarrow & & \Big\updownarrow\\[1ex]
    \mathcal C(n-1,\:s+1) \quad & \longleftrightarrow & \quad \mathcal Y(n-1,\:s)
\end{array}
\end{equation}
This duality between the values $(s,n)$ and $(n-1,\:s+1)$ will appear throughout our results (particularly the plots in Sections \ref{s:plotsd2} and \ref{s:plotsd3}).

We will briefly refer to a \textbf{corner} in a Young diagram; this is a cell such that the result of its removal is still a Young diagram.  For example, in the Young diagram $\alpha$ depicted above, there are three corners: the last cell in the first row, the last cell in the fourth row, and the cell in the bottom row.  We will write ${\rm cor}(\alpha)$ for the number of corners in $\alpha$, which can easily be computed as the number of distinct row lengths.

\subsection{The $q$-binomial coefficients}
\label{ss:qbin}
We recall here the $q$-analog of the binomial coefficients $\binom{a}{b}$.  These \textbf{$q$-binomial coefficients} often appear in one of two guises, both of which we will encounter near the end of this paper; therefore we distinguish the two with the following notation.

On one hand, let
$[a]_q \coloneqq 1 + q + \cdots + q^{a-1}$.  Then with $[a]_q! \coloneqq [a]_q [a-1]_q \cdots [1]_q$, we define $$\qbin{a}{b} \coloneqq \frac{[a]_q!}{[b]_q![a-b]_q!}.$$  This is actually a polynomial (not just a rational function) in $q$, which encodes combinatorial information central to this paper (see \cite{stanley1}, Proposition 1.7.3):
\begin{equation}
\label{qbinyoungfact}
\parbox{0.7\linewidth}{The coefficient of $q^w$ in $\qbin{s+n-1}{s}$ equals the number of Young diagrams in $\mathcal Y(s,\:n-1)$ with size $w$.}
\end{equation}
On the other hand, let $(a)_q \coloneqq q^{-(a-1)} + q^{-(a-3)} + \cdots + q^{a-3} + q^{a-1}$.  Then again with $(a)_q! \coloneqq (a)_q \cdots (1)_q$, we define
$$
\binom{a}{b}_q \coloneqq \frac{(a)_q!}{(b)_q! (a-b)_q!}.
$$
This is a Laurent polynomial, invariant under $q \longleftrightarrow q^{-1}$, which (as we will see) arises in the representation theory of the Lie algebra $\sl(2,\mathbb C)$.

To convert between the two guises of $q$-binomial coefficients, we observe that
\begin{equation}
    \label{convertqbins}
    \binom{s+n-1}{s}_q = q^{-s(n-1)}\genfrac[]{0pt}{}{s+n-1}{s}_{q^2.}
\end{equation}

\subsection{Plane partitions}  In proving a major result in Section \ref{s:plotsd2}, we will use a generalization of Young diagrams known as plane partitions.  A \textbf{plane partition} is a Young diagram in which each cell is filled with a nonnegative integer entry, such that the entries weakly decrease along each row and column.  A plane partition is visualized three-dimensionally by stacking cubes on a Young diagram such that the height above each cell is its integer entry; for this reason, a plane partition whose underlying Young diagram has at most $x$ rows and $y$ columns, with entries at most $z$, is said to fit inside an $x \times y \times z$ box.  The number of such partitions is
\begin{equation}
\label{planepartbox}
{\rm PP}(x,y,z)= \prod_{i=1}^x \prod_{j=1}^y \prod_{k=1}^z \frac{i+j+k-1}{i+j+k-2.}
\end{equation}
(See \cite{stanley2}, sections 7.20--22, for an expansive treatment of the combinatorics of plane partitions.)  In Section \ref{s:plotsd2}, we will appeal to the following specialization:

\begin{lemma}
\label{lemma:planepart}
In the case $z=2$, we have
\begin{equation}
\label{planepart}
{\rm PP}(x,y,2)=\frac{(x+1)\cdots (x+y)\cdot (x+2)\cdots (x+y+1)}{y!(y+1)!}
\end{equation}
where the omitted factors increase by 1.
\end{lemma}

\begin{proof}
Setting $z=2$, we separate \eqref{planepartbox} into two main factors (one for $k=1$ and the other for $k=2$) and account for the telescoping cancellations:
\begin{align*}
    {\rm PP}(x,y,2) &= \left(\prod_{i,j} \frac{i+j}{i+j-1} \right) \left(\prod_{i,j} \frac{i+j+1}{i+j} \right)\\
    &= \prod_{i,j} \frac{i+j+1}{i+j-1.}
\end{align*}
Now we use induction on $x$ and $y$ to prove that this product is equivalent to \eqref{planepart}.  In the base case $x=y=1$, the product above is just the single factor $\frac{1+1+1}{1+1-1}=3$, and likewise the expression in \eqref{planepart} is $\frac{(1+1)(1+2)}{1!2!}=\frac{6}{2}=3$.  (Note that the second string of factors in the numerator of \eqref{planepart} is the empty product 1 in the case $x=y=1$.)  

To induct on $x$, assume that the corollary holds for $x-1$ and $y$.  Then we have
\begin{align*}
    {\rm PP}(x,y,2) &= \prod_{i=1}^{x} \prod_{j=1}^y \frac{i+j+1}{i+j-1}\\
    &= \prod_{j=1}^y \frac{x+j+1}{x+j-1} \cdot {\rm PP}(x-1,y,2)\\
    &= \frac{(x+y)(x+y+1)}{(x)(x+1)} \cdot \frac{(x)\cdots (x+y-1)\cdot (x+1)\cdots (x+y)}{y!(y+1)!}\\
    &= \frac{(x+1)\cdots (x+y)\cdot (x+2)\cdots (x+y+1)}{y!(y+1)!}
\end{align*}
as in \eqref{planepart}.  The induction on $y$ works out similarly. \qed
\end{proof}

\section{Main result: EMC as symmetric difference of Young diagrams}

The \textbf{symmetric difference} of two sets, denoted by the symbol $\triangle$, is
$$
A \triangle B \coloneqq (A \backslash B) \cup (B \backslash A) = (A \cup B) \backslash (A \cap B),$$
the set of elements contained in exactly one of the two sets.  In many contexts it is natural to extend this definition associatively to any finite number of sets, but to capture the behavior of the EMC we introduce a different generalization.

\begin{definition}
We say the \textbf{unimodal symmetric difference} of sets $A_1,\ldots,A_d$ is 
$$
\blacktriangle(A_1,\ldots,A_d):=\sum_{k=1}^{d-1} \min\{k,\:d-k\}\cdot\Big|\{\text{elements contained in exactly }k \text{ of the }A_i \}\Big|.
$$
\end{definition}

(It would be equivalent to let $k$ range from $0$ to $d$.)  Note that $\blacktriangle$ returns a number rather than a set. Intuitively, the unimodal symmetric difference counts elements by assigning the weight 1 to those elements contained in exactly one, or all but one, set; then the weight 2 to those elements in exactly two, or all but two, sets; and so forth, finally assigning the greatest weight $\lfloor d/2 \rfloor$ to those elements contained in exactly ``half'' of the sets. (See Figure \ref{fig:venn}, where successively higher weights are shown by successively darker shades of grey.)  Note that in the $d=2$ case, $\blacktriangle(A,B)$ agrees with $|A \triangle B|$.  

\begin{figure}[h]
\captionsetup[subfigure]{labelformat=empty}
 
\begin{subfigure}[t]{0.28\textwidth}
\includegraphics[width=0.9\linewidth]{d2.png} 
\caption{For $d=2$, weights are $0,1,0$.}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.28\textwidth}
\includegraphics[width=0.9\linewidth]{d3.PNG}
\caption{For $d=3$, weights are $0,1,1,0$.}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.28\textwidth}
\includegraphics[width=0.9\linewidth]{d4.PNG}
\caption{For $d=4$, weights are $0,1,2,1,0$.}
\end{subfigure}
\vspace{0.5cm}

\begin{subfigure}[t]{0.28\textwidth}
\includegraphics[width=0.9\linewidth]{d5.png} 
\caption{For $d=5$, weights are $0,1,2,2,1,0$.  Note that in this example, the intersection of all five sets is empty.}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.28\textwidth}
\includegraphics[width=0.9\linewidth]{d6.PNG}
\caption{For $d=6$, weights are $0,1,2,3,2,1,0$.}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.28\textwidth}
\includegraphics[width=0.9\linewidth]{d8.PNG}
\caption{For $d=8$, weights are $0,1,2,3,4,3,2,1,0$.  This image depicts a chain of eight subsets.}
\end{subfigure}
 
\caption{A visualization of the unimodal symmetric difference $\blacktriangle(A_1,\ldots,A_d)$.  Each ellipse is one of the sets $A_i$, and the ``weights'' $0,1,2,\ldots$ are depicted by successively darker shades of grey.  Elements contained in $0$ or $d$ sets are not counted (white regions); elements contained in exactly $1$ or $d-1$ sets are counted once (lightest grey); elements in exactly $2$ or $d-2$ sets are counted twice (slightly darker grey); and so forth, until elements in the darkest regions are counted $\lfloor d/2 \rfloor$ times.}
\label{fig:venn}
\end{figure}

Now, consider each Young diagram in $\mathcal Y(s,\:n-1)$ as a subset of the full $s \times (n-1)$ rectangle of cells.  It then makes sense to say that a given cell is contained within several different Young diagrams; for example, the upper-left cell is contained in every Young diagram except for the empty diagram.  Therefore, by identifying compositions with their Young diagrams, we can speak of their unimodal symmetric difference.  We now state our main result.

\begin{theorem}
\label{mainthm}
On any tuple of compositions in $\mathcal C(s,n)$, we have $\EMC = \blacktriangle$.
\end{theorem}

\begin{proof}
Let $\alpha_1,\ldots,\alpha_d \in \mathcal C(s,n)$.  By \eqref{shortemddef}, we have $\EMC(\alpha_1,\ldots,\alpha_d)=\sum_{j=1}^s C(M_{\bullet j}),$ where $M$ is the matrix defined in \eqref{wordmatrix}.  Fix $j$, and put $M_{\bullet j}=(m_1,\ldots,m_d)$.  Since $C(\mathbf x)$ is symmetric in the entries of $\mathbf x$, we can assume without loss of generality that $m_1\leq \cdots \leq m_d$.  Then by Proposition \ref{cost}, we have
\begin{align*}
    C(M_{\bullet j}) &= \sum_{i=1}^{\lfloor d/2 \rfloor} m_{d+1-i}-m_i\\
    &= \sum_{i=1}^{\lfloor d/2 \rfloor}\sum_{k=i}^{d-i}m_{k+1}-m_{k.}
\end{align*}
Now we switch the order of summation, using the fact that $i\leq k \leq d-i$ implies both $i\leq k$ and $i\leq d-k$:
\begin{align*}
    C(M_{\bullet j})&=\sum_{k=1}^{d-1}\left(\sum_{i=1}^{\min\{k,\:d-k\}}m_{k+1}-m_k\right)\\
    &= \sum_{k=1}^{d-1} \min\{k,\: d-k\}\cdot (m_{k+1}-m_k)\\
    &= \blacktriangle\Big([m_1],\ldots,[m_d]\Big),
\end{align*}
where $[m_i]$ denotes the set $\{1,\ldots,m_i\}$.
Now, recalling the construction of the matrix $M$, we know that $m_k$ is the $j$th element from the word $w(\alpha_k)$, and therefore $m_k$ is the length of the $j^{\rm th}$ row (from the bottom) of the Young diagram $\alpha_k$.  Hence $\blacktriangle([m_1],\ldots,[m_d])$ is the result of applying $\blacktriangle$ to the collection containing the $j^{\rm th}$ row (from the bottom) of each of the Young diagrams $\alpha_1,\ldots,\alpha_d$.  Letting $j$ range over all $s$ rows and taking the sum, we conclude that $\EMC(\alpha_1,\ldots,\alpha_d)=\blacktriangle(\alpha_1,\ldots,\alpha_d)$. \qed
\end{proof}


\begin{example}
We return to Example \ref{rskexample}, but this time we will calculate the EMC combinatorially, using Theorem \ref{mainthm}.  We translate the word of each composition into its corresponding Young diagram:
$$
\alpha = \ydiagram{2,1}
 \qquad 
 \beta = \ydiagram{4,4,4} \qquad
 \gamma = \ydiagram{2,2,1,1,1,1} \qquad \delta = \ydiagram{4,3,2,2,1}$$
Now we superimpose these four diagrams so that they share a common upper-left cell; see the two diagrams below.  In the first diagram, we label each cell with the number of diagrams (among $\alpha, \beta, \gamma,\delta$) which contain it; then in the second diagram, to each cell labeled $k$ we assign the weight $\min\{k,\:4-k\}$, since $d=4$, and shade as in Figure \ref{fig:venn}:
$$
\ytableausetup{nosmalltableaux}
\begin{ytableau}
4 & 4 & 2 & 2\\
4 & 3 & 2 & 1\\
3 & 2 & 1 & 1\\
2 & 1 \\
2 \\
1
\end{ytableau}
\qquad \leadsto \qquad
\begin{ytableau}
0 & 0 & *(gray)2 & *(gray)2\\
0 & *(lightgray) 1 & *(gray)2 & *(lightgray) 1\\
*(lightgray) 1 & *(gray)2 & *(lightgray) 1 & *(lightgray) 1\\
*(gray)2 & *(lightgray) 1 \\
*(gray)2 \\
*(lightgray) 1
\end{ytableau}
$$
The shading is superfluous, of course, since we only need to sum the entries of the second diagram to compute that
\begin{align*}
\EMC(\alpha,\beta,\gamma,\delta) & = \blacktriangle(\alpha,\beta,\gamma,\delta)\\
&= 2+2+1+2+1+1+2+1+1+2+1+2+1\\
&= \mathbf{19},
\end{align*}
 agreeing with the calculation in Example \ref{rskexample}.

\end{example}

We record the following corollary because many applications of the EMC restrict to the $d=2$ case, and because this case reduces to the familiar definition of symmetric difference.  We appeal constantly to this corollary throughout Section \ref{s:plotsd2}.
\begin{corollary}
\label{d=2}
For $\alpha,\beta \in \mathcal C(s,n)$, we have $\EMC(\alpha,\beta) = |\alpha \triangle \beta|$.
\end{corollary}

\section{EMC vs.\ weighted difference: $d=2$}
\label{s:plotsd2}

When we regard a composition as a histogram, it makes sense to speak of its average.  Comparing the averages of two compositions is quite distinct from taking their EMC.  For example, in $\mathcal C(10,3)$, if
$$
\alpha=(5,0,5), \quad \beta=(0,10,0) \qquad \text{and} \qquad \alpha'=(5,5,0), \quad \beta'=(0,5,5),
$$
then $\EMC(\alpha,\beta)=\EMC(\alpha',\beta')=10$, even though the two pairs are ``far apart'' in very different ways: as histograms, $\alpha$ and $\beta$ have the same average but different standard deviations, while $\alpha'$ and $\beta'$ have different averages but the same standard deviation.  In this section, we study how the EMC of two compositions interacts with their averages.  We aim to expand upon the treatment in \cite{kretschmann} calculating the expected value of the EMC when restricted to composition pairs with identical average.  Then in the following section we will generalize to arbitrary $d$.

To make the notion of ``average'' precise, we put the most natural weighting on $\mathcal C(s,n)$, namely $(0,\ldots,n-1)$, so that the \textbf{weighted total} $\mathcal T$ of a composition is defined as
\begin{equation}
\label{weightedtotal}
    \mathcal T(\alpha)=\mathcal T(a_0,\ldots,a_{n-1})\coloneqq\sum_{i=0}^{n-1} i\cdot a_{i.}
\end{equation}
In this paper, we will work only with $\mathcal T$, rather than obtaining the actual average by dividing by $s$. There is no harm in doing this, since all our compositions share a common value of $s$.

\begin{remark}
In the case $n=5$, the weighted total is simply the grade-point system familiar to university students, where the five letter grades F, D, C, B, and A are worth 0, 1, 2, 3, and 4 points, respectively.  In the context of ranked-ballot voting theory, $\mathcal T(\alpha)$ is the Borda count of a candidate who receives $a_i$ votes as the $(n-i)^{\rm th}$-choice candidate.
\end{remark}

The purpose of the weighted total $\mathcal T$ is to compare compositions to each other, and so we are interested in the signed difference between two weighted totals: 

\begin{definition}
Let $\alpha,\beta \in \mathcal C(s,n)$.  We write
\begin{equation}
    \label{defD}
\mathcal D(\alpha,\beta)\coloneqq\mathcal T(\alpha)-\mathcal T(\beta)
\end{equation}
and call this the \textbf{weighted difference} of the ordered pair $(\alpha,\beta)$.
\end{definition}

(This definition will later be subsumed by its generalization in Definition \ref{def:Dgeneral}.) The weighted total and weighted difference have a simple interpretation in the language of Young diagrams, just as the EMC does.  If $\alpha,\beta \in \mathcal C(s,n)$, then
\begin{align}
\mathcal T(\alpha)&=|\alpha|, \label{Tsize}\\
\mathcal D(\alpha,\beta) &= |\alpha|-|\beta|. \nonumber
\end{align}
In words, the weighted total of a composition is the size of its Young diagram.  To see this, recall from \eqref{sizeword} that $|\alpha|$ equals the sum of the entries in the word $w(\alpha)$.  But $w(\alpha)$ contains exactly $a_i$ copies of $i$ for each $i= 0,\ldots,n-1$, and so the sum of its entries agrees with the definition of $\mathcal T$ in \eqref{weightedtotal}.   We are now equipped to study the statistical relationship between EMC and $\mathcal D$ via pairs of Young diagrams.

\subsection{Plotting EMC vs.\ $\mathcal D$}

For fixed $s$ and $n$, we introduce a two-dimensional plot whose vertical axis measures EMC and whose horizontal axis measures $\mathcal D$.  Each ordered pair in $\mathcal C(s,n) \times \mathcal C(s,n)$ is plotted accordingly, and the number inside each dot indicates the number of ordered pairs at that point. 
We now take the reader on a brief guided tour of these plots, aided by Figures \ref{fig:d2plotssmall} and \ref{fig:d2plotsbig}.    (We also include a three-dimensional rendering in Figure \ref{fig:d2plots3d}.)  The observations below provide a sort of dictionary between the statistics of histograms and the combinatorics of Young diagram pairs; ultimately, by Corollary \ref{d=2} and by \eqref{Tsize}, everything below is a statement about the interplay of two Young diagrams' symmetric difference with their relative sizes.

\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{d2plotssmall.PNG}
    \caption{Plots created in Mathematica, using the generating function in Section \ref{s:genfun}.  Each numbered dot indicates the number of composition pairs with given EMC and weighted difference.}
    \label{fig:d2plotssmall}
\end{figure}

\begin{figure}[htb]
\begin{subfigure}[t]{0.48\textwidth}
\includegraphics[width=\linewidth]{s15_n3.png} 
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.48\textwidth}
\includegraphics[width=\linewidth]{s10_n4.png}
\end{subfigure}

\begin{subfigure}[t]{0.48\textwidth}
\includegraphics[width=\linewidth]{s12_n4.png}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.48\textwidth}
\includegraphics[width=\linewidth]{s10_n5.png}
\end{subfigure}
\caption{Plots for larger values of $s$ and $n$.  We show only the right half, and we use the color spectrum rather than display the numbers (dark blue = 1, red = maximum).}
    \label{fig:d2plotsbig}
\end{figure}

\begin{figure}[h]
\captionsetup[subfigure]{labelformat=empty}
 
\begin{subfigure}[t]{0.48\textwidth}
\includegraphics[width=0.9\linewidth]{histo_xaxis.png} 
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.48\textwidth}
\includegraphics[width=0.9\linewidth]{histo_origin.png} 
\end{subfigure}

\begin{subfigure}[t]{0.48\textwidth}
\includegraphics[width=0.9\linewidth]{histo_upperleft.png} 
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.48\textwidth}
\includegraphics[width=0.9\linewidth]{histo_below.png} 
\end{subfigure}

\caption{A three-dimensional rendering (of the right half) of the plot for $s=10$ and $n=4$ (dually, for $s=3$ and $n=11$), seen from four angles.  The height above each point is the number inside the dot in the two-dimensional plot.}
\label{fig:d2plots3d}
\end{figure}

\begin{itemize}
    \item By definition, composition pairs $(\alpha,\beta)$ lying further to the right (higher positive $\mathcal D$-values) are more ``lopsided'' (in terms of weighted total) in favor of $\alpha$, and vice versa.  But since the plot is symmetric about the vertical axis, from now on we restrict our attention to the right half, i.e., those pairs for which $\mathcal T(\alpha) \geq \mathcal T(\beta)$.  \emph{We therefore refer only to the right half of the plots in the remainder of this list.}
    
     \item The plot for $\mathcal C(s,n)$ is identical to that for $\mathcal C(n-1,\:s+1)$.  (Compare, for instance, the first two plots in the second row of Figure \ref{fig:d2plotssmall}; this is the only redundancy we have included in the figures.)  This duality is not at all obvious \emph{a priori} from the original definitions of EMC and $\mathcal D$, but it is immediate when we consider the conjugates of Young diagrams, as in \eqref{transpose}: after all, $|\alpha \triangle \beta|$ and $|\alpha|$ and $|\beta|$ are invariant under conjugates, so the EMC-vs.-$\mathcal D$ plots are as well.
     
         
    \item In general, $\EMC \geq \mathcal D$ since $\alpha \triangle \beta \supseteq \alpha \backslash \beta$.
    
    \item The values of both EMC and $\mathcal D$ range from $0$ to $s(n-1)$. 
    This is obvious when we consider the $s \times (n-1)$ rectangle containing every diagram in $\mathcal Y(s,\:n-1)$.
    
    \item In each plot, the upper-rightmost data point corresponds to the unique pair $(\alpha,\beta)$ where $\alpha$ is the full $s\times (n-1)$ rectangle and $\beta$ is the empty diagram.  Starting from here, moving one unit left on the plot corresponds to either subtracting one cell from $\alpha$ or adding one cell to $\beta$ (in such a way that both remain Young diagrams).
    
    \item All composition pairs lie on the integer lattice of points whose coordinates have the same parity.  
   This reflects the fact that adding or subtracting one cell to/from either diagram changes $|\alpha \triangle \beta|$ by exactly 1.
   
   \item The ``tail'' along the diagonal ($y=x$) on the far right reveals that after a certain threshold when $\mathcal D$ is sufficiently large, EMC and $\mathcal D$ coincide with each other;  
   in the language of Young diagrams, $|\alpha \triangle \beta| = |\alpha| - |\beta|$ implies $\beta \subseteq \alpha$, so that in any pair on the diagonal, the first diagram contains the second.  We claim that this threshold is $\mathcal D = (s-1)(n-2)$.  
   
   \begin{proof} Starting from the far right at $\mathcal D=s(n-1)$ where $\alpha$ is the full rectangle and $\beta$ is empty, the most efficient way to make $\beta$ spill outside $\alpha$ is to subtract the $s$ cells from the rightmost column of $\alpha$ and to add $n-1$ cells to the top row of $\beta$; at this point, the cell in the upper-right will belong to $\beta$ but not to $\alpha$.   Therefore, since moving left from $s(n-1)$ by $(s+n-1)$ steps takes us to the line $\mathcal D = sn - 2s - n + 1$, the ``tail'' must begin just to the right of this $\mathcal D$-value, namely $\mathcal D = sn - 2s - n +2 = (s-1)(n-2)$. \qed\end{proof}
   
    \item The highest concentration occurs relatively close to the origin, on the diagonal.  These are pairs in which one Young diagram contains the other, but with a difference of only a ``few'' cells.  More generally, at any point on the diagonal, the composition pairs have the lowest possible EMC given a fixed $\mathcal D$-value, and also the highest possible $\mathcal D$-value given a fixed EMC; in other words, if we fix either statistic, then the most ``lopsided'' possible composition pairs are those on the diagonal.  In light of these last two observations, it is natural to ask what proportion of pairs occur along the diagonal, and we answer this question in the next subsection.
   
   
   
   \item A useful statistical goal might be to determine a formula for the distribution of $\EMC$ values for a given $\mathcal D$-value. Combinatorially, the question is this: among all pairs of Young diagrams whose sizes differ by a given number of cells, what is the distribution of the symmetric differences of the pairs?  The answer is encoded in the recursive generating function in Section \ref{s:genfun}, but here we make a first step toward a closed-form expression by attacking the case $\mathcal D=0$, i.e., when two diagrams have equal size:
       \begin{itemize}
           \item Clearly the number of pairs with $\EMC=0$ is just $|\mathcal Y(s,\:n-1)|=\binom{s+n-1}{s}$, since these are the pairs of identical diagrams.  The reader can check that this binomial coefficient is indeed the value at the origin in each plot.
           \item The next possible EMC value is 2.  The question is this: for how many ordered pairs $(\alpha,\beta)$ of equally-sized diagrams in $\mathcal Y(s,\:n-1)$ is the symmetric difference exactly two cells?  For such a pair, consider the union $\gamma = \alpha \cup \beta \in \mathcal Y(s,\:n-1)$, and specifically consider the corners of $\gamma$.  Exactly one of these corners must belong to $\alpha$ alone, and exactly one of the corners (but not the same one!) must belong to $\beta$ alone.  In this way, to each $\gamma \in \mathcal Y(s,\: n-1)$ there correspond all possible ordered pairs of diagrams obtained by assigning one corner to each of the diagrams; the number of these pairs is the number of permutations of ${\rm cor}(\gamma)$ objects taken two at a time.  We conclude that the value of each plot at the point $(0,2)$ is given by     $$\sum_{\mathclap{\gamma \in \mathcal Y(s,\:n-1)}} {\rm cor}(\gamma) \cdot ({\rm cor}(\gamma)-1).
           $$
           \end{itemize}
           
          
           \end{itemize}

As an afterthought to our EMC-vs.-$\mathcal D$ plots, we should point out another convenient way to visualize the EMC together with the weighted difference.  If we impose a partial order (via inclusion) on the set of Young diagrams, then the result is \textbf{Young's lattice}.  (See \cite{stanley2}, Chapter 7; we provide a truncated picture in Figure \ref{fig:lattice}.) Given $s$ and $n$, the sublattice $\mathcal Y(s,\:n-1)$ is the interval between the empty diagram and the full $s\times(n-1)$ rectangle.  Young's lattice is \textbf{ranked} with respect to the size of the diagrams, so that every diagram in the $i^{\rm th}$ horizontal level has rank $i$.  The least upper bound (the ``join,'' written $\alpha \vee \beta$) is the union of the two diagrams, while the greatest lower bound (the ``meet'' $\alpha \wedge \beta$) is their intersection.  Hence, identifying $\alpha,\beta \in \mathcal C(s,n)$ with their Young diagrams as usual, we have
\begin{align*}
\mathcal D(\alpha,\beta) &= {\rm rank}(\alpha) - {\rm rank}(\beta),\\
\EMC(\alpha,\beta) &= {\rm rank}(\alpha \vee \beta) - {\rm rank}(\alpha \wedge \beta).
\end{align*}

\begin{figure}[htb]
    \centering
    \includegraphics[width=0.3\textwidth]{younglattice.png}
    \caption{Young's lattice, shown up to rank 5.  If compositions $\alpha$ and $\beta$ correspond to the blue and red diagrams respectively, then $\mathcal D(\alpha,\beta)=1$ since $\alpha$ is one row above $\beta$.  The darkened arrows converge above at $\alpha \vee \beta$, of rank 5, and converge below at $\alpha \wedge \beta$, of rank 2; therefore $\EMC(\alpha,\beta) =5-2=3$.}
    \label{fig:lattice}
\end{figure}

\subsection{Proportion for which $\EMC = \mathcal D$ in the continuous setting}  
As we have observed above, there is a relatively high concentration of pairs along the diagonals $y=|x|$ of our plots.  Statistically speaking, at least for the cases we have plotted, in a (perhaps surprisingly) high proportion of composition pairs, the EMC is nothing other than the absolute value of the weighted difference $\mathcal D$. We now determine this proportion.

\begin{theorem}
\label{emc=d}
The proportion of pairs in $\mathcal C(s,n) \times \mathcal C(s,n)$ such that $\EMC = |\mathcal D|$ is 
$$
\frac{2(s+n)}{n(s+1)}-\frac{(n-1)!}{(s+1)\cdots (s+n-1).}
$$
\end{theorem}

\begin{proof} 
As we observed above, $\EMC(\alpha,\beta)=|\mathcal D(\alpha,\beta)|$ if and only if the diagram of $\alpha$ contains the diagram of $\beta$ or vice versa.  But there is a bijective correspondence
\begin{equation*}
    \left\{\quad\parbox{5.5cm}{\centering unordered pairs of Young diagrams from $\mathcal Y(s,\:n-1)$ such that one diagram contains the other}\quad\right\} \longleftrightarrow \left\{\quad\parbox{3cm}{\centering plane partitions fitting in an $s \times (n-1) \times 2$ box}\quad\right\}_{\textstyle .}
\end{equation*}
To see this, consider a pair of diagrams in the left-hand set and superimpose them so that their upper-left cells coincide.  Filling any cell common to both diagrams with a ``2,'' and all the others with a ``1,'' we obtain a plane partition in the right-hand set.  In the other direction, starting with a plane partition from the right-hand set, we produce a unique pair of Young diagrams: the larger diagram is just the underlying diagram of the plane partition, and the smaller diagram is the collection of cells with the entry ``2.''

Therefore the number of unordered composition pairs such that $\EMC = |\mathcal D|$ is equal to ${\rm PP}(s,\:n-1,\:2)$.  By Lemma \ref{lemma:planepart}, this number is
$$
{\rm PP}(s,\:n-1,\:2) = \frac{(s+1) \cdots (s+n-1) \cdot (s+2) \cdots (s+n)}{n!(n-1)!}.
$$
To find the number of such \textit{ordered} pairs in $\mathcal C(s,n) \times \mathcal C(s,n)$, we multiply by 2 to account for both pairs $(\alpha,\beta)$ and $(\beta,\alpha)$, and then correct for the pairs $(\alpha,\alpha)$ by subtracting $|\mathcal C(s,n)| =\binom{s+n-1}{n-1} = \frac{(s+1) \cdots (s+n-1)}{(n-1)!}$. Hence the number of ordered pairs described in the theorem statement is
$$
2\cdot {\rm PP}(s, \: n -1, \:2) - \frac{(s+1) \cdots (s+n-1)}{(n-1)!}.
$$
Finally, to convert this into a \textit{proportion} of all ordered pairs, we divide by $|\mathcal C(s,n)|^2$, and after simplifying we obtain
\begin{align*}
    & \quad \frac{2\cdot {\rm PP}(s, \: n -1, \:2) - \frac{(s+1) \cdots (s+n-1)}{(n-1)!}}{\left(\frac{(s+1) \cdots (s+n-1)}{(n-1)!}\right)^2}\\[3ex] 
    &= \frac{\frac{2(s+1) \cdots (s+n-1) \cdot (s+2) \cdots (s+n)}{n!(n-1)!}}{\left(\frac{(s+1) \cdots (s+n-1)}{(n-1)!}\right)^2} -\frac{\frac{(s+1) \cdots (s+n-1)}{(n-1)!}}{\left(\frac{(s+1) \cdots (s+n-1)}{(n-1)!}\right)^2} \\[3ex]
    &= \frac{2(s+n)}{n(s+1)} - \frac{(n-1)!}{(s+1)\cdots (s+n-1).}
\end{align*}\qed
\end{proof}

\begin{corollary}
\label{cor:continuous}
For fixed $n$, as $s\rightarrow \infty$, the proportion of elements in $\mathcal C(s,n) \times \mathcal C(s,n)$ such that $\EMC = |\mathcal D|$ asymptotically approaches $2/n$.
\end{corollary}

\begin{proof}
Take the limit of the proportion in Theorem \ref{emc=d} as $s \rightarrow \infty$. \qed
\end{proof}

Suppose that we had defined normalized versions of EMC and $\mathcal T$, namely
$$\widehat{\EMC}(\alpha,\beta)\coloneqq \frac{\EMC(\alpha,\beta)}{s} \quad \text{and} \quad \widehat{\mathcal T}(\alpha) \coloneqq \frac{\mathcal T(\alpha)}{s},$$ in order to guarantee that both values lie on the interval $[0,\: n-1]$.  (In this way, $\widehat{\mathcal T}$ is a true weighted \textit{average}.)  Then Corollary \ref{cor:continuous} is a statement about the \textit{continuous} setting, i.e., pairs of probability distributions (rather than discrete histograms) on the set $\{0,\ldots,n-1\}$.  Indeed, both $\widehat{\EMC}$ and $\widehat{\mathcal T}$ (and therefore $\widehat{\mathcal D}$) have natural analogs on probability distributions, obtained by letting $s \rightarrow \infty$.  Then for a randomly chosen ordered pair $(A,B)$ of probability distributions on $\{0,\ldots,n-1\}$, the probability that $\widehat{\EMC}(A,B) = |\widehat{\mathcal D}(A,B)|$ is $2/n$.  This continuous result was proved using only the combinatorics of plane partitions.

\section{$\mathcal D$-distributions as weight diagrams for $\sl_d$}
\label{s:plotsd3}

\subsection{Overview} In this section, we generalize the weighted difference $\mathcal D$ in order to compare $d$ compositions rather than only two.  Our $\mathcal D$-values will no longer be single integers, but elements of the following $\mathbb Z$-module:
\begin{equation}
\label{Zddef}
    \widetilde{\mathbb Z}^d \coloneqq \Big\{(w_1,\ldots,w_d) \: \Big \vert \: w_i \in \mathbb Z\Big\} \Big / \mathbb Z(1,\ldots,1). 
\end{equation}
Since elements of $\widetilde{\mathbb Z}^d$ are equivalence classes of $d$-tuples, we write an element using square brackets around any of its representatives.  For example, $[5,2,1,3] = [2,-1,-2,0]$.  As in this example, forcing the last entry to be 0 results in a \emph{unique} way of writing an element as a $(d-1)$-tuple; we will use this convention below whenever convenient.

We will have cause to use the term ``weight''  yet again, and in yet another sense: this time, the weights we consider are those from Lie theory (elements of the dual of the Cartan subalgebra).  Specifically, we will consider those weights contained in the root lattice $\Lambda_{\rm R}$ for the Lie algebra $\sl_d = \sl(d,\mathbb C)$. The key observation in \eqref{rootlatticeiso} will be that
$$
\widetilde{\mathbb Z}^d \cong \Lambda_{\rm R}
$$
 as $\mathbb Z$-modules, so that each $\mathcal D$-value in $\widetilde{\mathbb Z}^d$ can be regarded as a weight of $\sl_d$.
(As the reader may have suspected, the results in this section will require some familiarity with representation theory and the Type A root system; we review these details in Section \ref{s:repthy}.)

In Theorem \ref{thm:character}, we prove that the distribution of $\mathcal D$-values on $\mathcal C(s,n)^d$, which is complicated combinatorial data, can be realized as the character of a certain virtual $\sl_d$-representation; this means that the plot of $\mathcal D$-values \emph{is} the weight diagram of this representation.  We provide illustrations of these diagrams for $d=3$.
 
\subsection{Weighted difference for arbitrary $d$} We now generalize the weighted difference $\mathcal D$  to compare $d$ compositions.  We want $\mathcal D$ to capture just the right amount of information --- namely, each of the pairwise differences between weighted totals, but nothing more --- and so the most natural definition is the following.  
\begin{definition}
\label{def:Dgeneral}
Given $s,n \geq 1$ and $d\geq 2$, we (re)define the \textbf{weighted difference} to be the function $\mathcal D : \mathcal C(s,n)^d \longrightarrow \widetilde{\mathbb Z}^d$ given by
$$
\mathcal D(\alpha_1,\ldots,\alpha_d) \coloneqq \big[\mathcal T(\alpha_1),\ldots,\mathcal T(\alpha_d)\big].
$$
\end{definition}

\begin{remark}
As mentioned in the overview, each element of $\widetilde{\mathbb Z}^d$ can be represented uniquely by a $d$-tuple whose final coordinate is 0, which can then be truncated into a $(d-1)$-tuple.  With this convention in mind, our new version of $\mathcal D$ agrees with the old definition in the $d=2$ case, since $\mathcal D(\alpha,\beta) = \big[\mathcal T(\alpha), \mathcal T(\beta)\big] = \big[ \mathcal T(\alpha) - \mathcal T(\beta),\:0\big] \leadsto \mathcal T(\alpha) - \mathcal T(\beta)$, just as before.
\end{remark}

We pose the natural combinatorial question: how many elements in $\mathcal C(s,n)^d$ have a given $\mathcal D$-value?  It turns out that the answer can be interpreted as a weight multiplicity in the $\sl_d$-representation described in the following theorem.

\begin{theorem}
\label{thm:character}
Let $s,n \geq 1$ and $d \geq 2$.  For $i=1,\ldots,d-1$, put $x_i = e^{\sigma_i}$, and put $x_d = e^{-(\sigma_1 + \cdots + \sigma_{d+1})}$, where $\sigma_i$ is the $i^{\rm th}$ simple root for $\sl_d$. Then the vector space
$$V = \textstyle \bigotimes^d \Sym^s(\mathbb C^n)$$
admits a virtual representation of $\sl_d$ whose character
$$
{\rm char}_{\sl_d}(V) = \prod_{i=1}^d \genfrac[]{0pt}{}{s+n-1}{s}_{x_{i}}
$$
is the distribution of $\mathcal D$-values on $\mathcal C(s,n)^d$.  Specifically, the coefficient of $x_1^{w_1} \cdots x_d^{w_d}$ equals the number of $d$-tuples whose $\mathcal D$-value is $[w_1,\ldots,w_d]$.
\end{theorem}

We reserve the proof for Section \ref{s:repthy}, along with the necessary preliminaries.  Note that the relation $x_d = (x_1 \cdots x_{d-1})^{-1}$ allows us to write the character in terms of just the variables $x_1,\ldots,x_{d-1}$; then (as the reader may already see, but we will explain in Section \ref{s:repthy}) the correspondence in the theorem boils down to the following dictionary between $\mathcal D$-values and $\sl_d$-weights:
\begin{align*}
    \widetilde{\mathbb Z}^d & \longleftrightarrow \Lambda_{\rm R}\\
    [w_1,\ldots,w_{d-1},0] &\longleftrightarrow w_1\sigma_1 + \cdots + w_{d-1}\sigma_{d-1.}
\end{align*}

\begin{example}
\label{ex:weights}
Let $d=3$, with $s=1$ and $n=2$.  Then by the character formula in Theorem \ref{thm:character}, we have
\begin{align*}
{\rm char}_{\sl_3}(V) &= \genfrac[]{0pt}{}{2}{1}_{x_{1}}\genfrac[]{0pt}{}{2}{1}_{x_{2}}\genfrac[]{0pt}{}{2}{1}_{x_{3}}\\
& = \genfrac[]{0pt}{}{2}{1}_{x_{1}}\genfrac[]{0pt}{}{2}{1}_{x_{2}}\genfrac[]{0pt}{}{2}{1}_{(x_1 x_2)^{-1}}\\
&= x_1 + x_2 + x_1 x_2 + x_1^{-1}  + x_2^{-2} + x_1^{-1}x_2^{-1} + 2.
\end{align*}
Lining up each term's exponent vector $(w_1,w_2)$ with its corresponding $\mathcal D$-value $[w_1,w_2,0]$, we conclude that in $\mathcal C(1,2) \times \mathcal C(1,2) \times \mathcal C(1,2)$, there is one triple having each of the $\mathcal D$-values
$$
[1,0,0], \quad [0,1,0], \quad [1,1,0], \quad [-1, 0, 0], \quad [0,-1,0], \quad \text{and} \quad [-1,-1,0],
$$
and two triples for which $\mathcal D = [0,0,0]$.  The reader can easily verify this distribution by hand.
\end{example}

\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{d3_plots_figure.png}
    \caption{Plots of the distribution of $\mathcal D$-values for $d=3$.  By Theorem \ref{thm:character}, these are also the weight diagrams of the space $V=\bigotimes^3 \Sym^s(\mathbb C^n)$ as a virtual $\sl_d$-representation.}
    \label{fig:d3plots}
\end{figure}

\subsection{$\mathcal D$-distributions as $\sl_d$-weight diagrams} We would like to visualize the distribution of $\mathcal D$-values for a given $s$ and $n$.  Theorem \ref{thm:character} states that such a visualization is nothing other than the weight diagram of $V$ under a certain action by $\sl_d$, and the theorem even tells us the data of the diagram explicitly via the character. Since the root lattice for $\sl_d$ can be depicted in $(d-1)$ dimensions, we can easily plot the weight diagrams when $d \leq 3$.  (Even the three-dimensional lattice for $d=4$ is quite possible to visualize.)

For $d=2$, of course, we can obtain the desired diagram simply by taking our planar plots from the previous section and ``projecting'' (via summation) each vertical strip down onto the horizontal axis; in this way, each integer on the number line is labeled with the total number of composition pairs having that $\mathcal D$-value.  (Essentially, this is just throwing away the EMC information from the plots.)  The root lattice is generated by the sole simple root $\sigma_1$, pointing in the positive $\mathcal D$-direction.  On one hand, we know that these ``column sums'' from our old plots count the number of Young diagram pairs which differ in size by a fixed number of cells; on the other hand, Theorem \ref{thm:character} says that these sums are just the weights of $\Sym^s(\mathbb C^n) \otimes \Sym^s(\mathbb C^n)$ as an $\sl_2$-representation.\footnote{When $d=2$, we can drop the term ``virtual'' since $V\cong \Sym^s(\Sym^{n-1}(\mathbb C^2)) \otimes \Sym^s(\Sym^{n-1}(\mathbb C^2)^*)$ under the standard action of $\sl_2$.  See the discussion in Section \ref{s:repthy}.}

For $d=3$, the root lattice is a two-dimensional triangular lattice generated by $\sigma_1$ (pointing due east, at 0 degrees) and $\sigma_2$ (pointing northwest, at 120 degrees).  Then \eqref{rootlatticeiso} tells us where to plot each exponent vector in ${\rm char}_{\sl_d}(V)$, which we label with the corresponding coefficient.  From Example \ref{ex:weights}, we obtain a regular hexagon of dots labeled ``1,'' along with a dot at the origin labeled ``2.''  (See the first diagram in Figure \ref{fig:d3plots}, which the reader may recognize as the weight diagram of the adjoint representation of $\sl_3$.)  In Figure \ref{fig:d3plots}, for $d=3$, we display the weight diagrams (i.e., $\mathcal D$-distributions) for several other values of $s$ and $n$.  Incidentally, Theorem \ref{thm:character} gives a much more efficient way to create these graphics than does the generating function in Section \ref{s:genfun}, especially for large values of $n$.

\begin{remark}
We consider another, perhaps more natural way to think about the plots of $\mathcal D$-distributions; we remain with the $d=3$ case, although this approach holds in any dimension.

For any ordered triple $(\alpha, \beta, \gamma)$ of compositions, draw three axes radiating from the origin (as we do in Figure \ref{fig:d3plots}): the $\alpha$-axis in the direction of $\sigma_1$, the $\beta$-axis in the direction of $\sigma_2$, and the $\gamma$-axis in the direction of $-(\sigma_1 +\sigma_2)$, i.e.,  southwest at 240 degrees.  (These are the weights corresponding to $x_1$, $x_2$, and $x_3$ in the character formula.)  Now we can plot a $\mathcal D$-value $[a,b,c]$, whether or not its final coordinate is 0, by starting at the origin and moving $a$ units parallel to the $\alpha$-axis, $b$ units parallel to the $\beta$-axis, and $c$ units parallel to the $\gamma$-axis. Notice that any multiple of $[1,1,1]$ lands on the origin, just as we would expect. 

Now the angular position of a $\mathcal D$-value tells us immediately the ordering of the three weighted totals: for example, at all points strictly between 120 and 180 degrees, we must have $\mathcal T(\beta) > \mathcal T(\gamma) > \mathcal T(\alpha)$.  The radial distance is a measure of the ``lopsidedness'' among the three weighted totals.  By the symmetry inherent in our setup, we can get a full picture of the diagram by restricting our attention to just one sector, such as that between 0 and 60 degrees where $\mathcal T(\alpha) \geq \mathcal T(\beta) \geq \mathcal T(\gamma)$.  Although we have focused on $\mathcal D$ at the expense of EMC in this section, we could nevertheless include the EMC frequencies in the $d=3$ diagrams by plotting them in the third dimension, along strips directly above each $\mathcal D$-value, just as in our $d=2$ plots.
\end{remark}

From the perspective of representation theory, rather than work with the entire weight diagram of $V$, it is natural to seek the decomposition of $V$ into irreducible subrepresentations of $\sl_3$.  Since finite-dimensional irreducible representations are indexed by their highest weight, we can actually convey the same information from the weight diagram with a much sparser diagram, on which we plot only those highest weights corresponding to the irreducible decomposition of $V$. (See Figure \ref{fig:d3irreps}, where we show only the region of the root lattice inside the dominant chamber.)  As experts will have anticipated, we programmed these decompositions by multiplying ${\rm char}_{\sl_3}(V)$ by the Weyl denominator $(1-x_1^{-1})(1-x_2^{-1})(1-(x_1x_2)^{-1})$, and then plotting the dominant weights in the resulting expansion. In these plots, the number inside each dot indicates the multiplicity of that irreducible representation inside $V$.  Note that some multiplicities are negative (depicted by red dots), reflecting the fact that $V$ is actually a \textbf{virtual representation} of $\sl_3$, i.e., a formal $\mathbb Z$-combination of irreducible representations, rather than a direct sum.  When $s=1$, we see that $V$ is isomorphic to the irreducible representation of $\sl_3$ with highest weight $(n-1)(\sigma_1 + \sigma_2)$.  As $s$ or $n$ increases, certain patterns are emerging from the diagrams, but this decomposition will be an interesting subject of further research.  The three-dimensional diagrams in the $d=4$ case will likely be of interest as well.

\begin{figure}[htbp]
\captionsetup[subfigure]{labelformat=empty}
 
\begin{subfigure}[t]{0.24\textwidth}
\includegraphics[width=\linewidth]{d3_irrep_plots/irrep_s1_n2.png} 
\caption{$s=1$, $n=2$}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.24\textwidth}
\includegraphics[width=\linewidth]{d3_irrep_plots/irrep_s1_n3.png} 
\caption{$s=1$, $n=3$}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.24\textwidth}
\includegraphics[width=\linewidth]{d3_irrep_plots/irrep_s1_n4.png} 
\caption{$s=1$, $n=4$}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.24\textwidth}
\includegraphics[width=\linewidth]{d3_irrep_plots/irrep_s1_n5.png} 
\caption{$s=1$, $n=5$}
\end{subfigure}
\vspace{0.5cm}

\begin{subfigure}[t]{0.24\textwidth}
\includegraphics[width=\linewidth]{d3_irrep_plots/irrep_s2_n3.png} 
\caption{$s=2$, $n=3$}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.24\textwidth}
\includegraphics[width=\linewidth]{d3_irrep_plots/irrep_s2_n4.png} 
\caption{$s=2$, $n=4$}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.24\textwidth}
\includegraphics[width=\linewidth]{d3_irrep_plots/irrep_s2_n5.png} 
\caption{$s=2$, $n=5$}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.24\textwidth}
\includegraphics[width=\linewidth]{d3_irrep_plots/irrep_s2_n6.png} 
\caption{$s=2$, $n=6$}
\end{subfigure}
\vspace{0.5cm}

\begin{subfigure}[t]{0.24\textwidth}
\includegraphics[width=\linewidth]{d3_irrep_plots/irrep_s3_n4.png} 
\caption{$s=3$, $n=4$}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.24\textwidth}
\includegraphics[width=\linewidth]{d3_irrep_plots/irrep_s3_n5.png} 
\caption{$s=3$, $n=5$}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.24\textwidth}
\includegraphics[width=\linewidth]{d3_irrep_plots/irrep_s3_n6.png} 
\caption{$s=3$, $n=6$}
\end{subfigure}
\hfill
\begin{subfigure}[t]{0.24\textwidth}
\includegraphics[width=\linewidth]{d3_irrep_plots/irrep_s3_n7.png} 
\caption{$s=3$, $n=7$}
\end{subfigure}
\vspace{0.5cm}

\begin{subfigure}[t]{0.25\textwidth}
\includegraphics[width=\linewidth]{d3_irrep_plots/irrep_s4_n5.png} 
\caption{$s=4$, $n=5$}
\end{subfigure} \qquad
\begin{subfigure}[t]{0.25\textwidth}
\includegraphics[width=\linewidth]{d3_irrep_plots/irrep_s4_n6.png} 
\caption{$s=4$, $n=6$}
\end{subfigure}

\caption{The decomposition of $V=\bigotimes^3 \Sym^s(\mathbb C^n)$ as a virtual $\sl_3$-representation.  Each irreducible representation of $\sl_3$ is plotted (with multiplicity) at its highest weight.  Negative multiplicities are colored red.}
\label{fig:d3irreps}
\end{figure}

\section{Representation theory and proof of Theorem \ref{thm:character}}
\label{s:repthy}

\subsection{Essentials of representation theory}
We provide a cursory overview with a view to proving Theorem \ref{thm:character}, but this section nonetheless assumes some familiarity with representation theory and the ${\rm A}_{d-1}$ root system.  Specifically, $\SL(d,\mathbb C)$ is the group of complex $d \times d$ matrices with determinant 1.  Its Lie algebra $\sl_d = \sl(d,\mathbb C)$ consists of complex $d \times d$ matrices with trace 0, equipped with the commutator bracket.    As usual, $\varepsilon_i$ denotes the \textbf{weight} (i.e., a linear functional on the Cartan subalgebra $\mathfrak h$ of diagonal matrices in $\sl_d$) which takes ${\rm diag}[h_1,\ldots,h_d]$ to the scalar $h_i \in \mathbb C$.  The trace-zero condition implies that
\begin{equation}
\label{sumepsilons}
    \varepsilon_1 + \cdots + \varepsilon_d = 0.
\end{equation}  
In a slight departure from standard notation, we will denote the $i^{\rm th}$ \textbf{simple root} by
$$
\sigma_i \coloneqq \varepsilon_i - \varepsilon_{i+1}
$$
for $i=1,\ldots,d-1$.  (The only reason we use $\sigma_i$ rather than the usual $\alpha_i$ is because we have been using $\alpha_i$ to denote compositions.) The simple roots generate the \textbf{root lattice}
$$
\Lambda_{\rm R}
\coloneqq \mathbb Z\sigma_1 \oplus \cdots \oplus \mathbb Z\sigma_{d-1} \subset \mathfrak h^*.$$
Since $\displaystyle\sum_{i=1}^{d-1} \sigma_i = \varepsilon_1 - \varepsilon_d$, we have
\begin{equation*}
    \Lambda_{\rm R} \cong \left\{ \sum_{i=1}^{d-1}w_i \sigma_i + w_d(\varepsilon_d - \varepsilon_1) \: \Big \vert \: w_i \in \mathbb Z \right\} \Bigg / \mathbb Z\left( \sum_{i=1}^{d-1} \sigma_i + (\varepsilon_d-\varepsilon_1)\right)
\end{equation*}
as $\mathbb Z$-modules.  Comparing this with the definition of $\widetilde{\mathbb Z}^d$ in \eqref{Zddef}, we have the $\mathbb Z$-module isomorphism
\begin{align}
    \widetilde{\mathbb Z}^d & \cong \Lambda_{\rm R}, \nonumber \\
    [w_1,\ldots,w_d] & \mapsto w_1 \sigma_1 + \cdots + w_{d-1}\sigma_{d-1} +w_d(\varepsilon_d - \varepsilon_1), \nonumber \\
    [w_1,\ldots,w_{d-1},0] & \mapsto \sum_{i=1}^{d-1}w_i\sigma_i. \label{rootlatticeiso}
\end{align}
This isomorphism will be our dictionary between $\mathcal D$-values on $\mathcal C(s,n)^d$ and weights of $\sl_d$.

A \textbf{representation} of a complex Lie algebra $\mathfrak g$ is a Lie algebra homomorphism $\mathfrak g \longrightarrow {\rm End}(W)$ for some complex vector space $W$; we often say that the underlying space $W$ \emph{is} the representation, with the homomorphism implied, or we say that ``$\mathfrak g$ acts on $W$.''  All representations in this paper are finite-dimensional (with the exception of the supplemental Section \ref{wallach} aimed at experts).  Given a representation $W$, its \textbf{character} ${\rm char}_{\mathfrak g}(W)$ is a formal sum of $\mathfrak g$-weights $\lambda$, often written in exponential notation, such that the coefficient of $e^\lambda$ equals the dimension of the $\lambda$-weight space in $W$.  (We omit the definition of a weight space since it is not essential for our result; to supplement our summary here, the reader is referred to \cite{fh} or \cite{gw}, among the many references on representation theory.)  The exponential notation ensures that \textit{multiplying} terms formally encodes \textit{adding} weights: $e^\lambda e^\mu = e^{\lambda  +\mu}$.  In this way, ${\rm char}_{\mathfrak g}(W\oplus W') = {\rm char}_\mathfrak g (W) + {\rm char}_\mathfrak g (W')$, and ${\rm char}_{\mathfrak g} (W \otimes W') = {\rm char}_{\mathfrak g}(W) \cdot {\rm char}_{\mathfrak g}(W')$.

Back in the $\sl_d$ setting, with the dictionary \eqref{rootlatticeiso} in mind, we now set
\begin{equation}
\label{def:x_i}
x_i = \begin{cases}
e^{\sigma_i} & 1 \leq i \leq d-1,\\
e^{\varepsilon_d - \varepsilon_1} & i = d,
\end{cases}
\end{equation}
so that we can write $\sl_d$-characters in terms of the $x_i$.  But by substituting $x_d = (x_1 \cdots x_{d-1})^{-1}$, we can actually write characters in terms of just $x_1,\ldots,x_{d-1}$.

Now we fix $s,n \geq 1$ and $d \geq 2$. The Lie algebra $\mathfrak{gl}_n=\mathfrak{gl}(n,\mathbb C)$ of complex $n \times n$ matrices acts naturally on the vector space $\mathbb C^n$ by matrix multiplication. Therefore $\mathfrak{gl}_n$ also acts (irreducibly) on $\Sym^s(\mathbb C^n)$, the $s^{\rm th}$ symmetric power of $\mathbb C^n$.

Meanwhile, $\sl_2$ also acts irreducibly on $\mathbb C^n \cong \Sym^{n-1}(\mathbb C^2)$.  The reader can consult Section 2.3.2 of \cite{gw} for the explicit action via differential operators on homogeneous polynomials, but for us the important information is the character of this $\sl_2$-action:
$$
{\rm char}_{\sl_2}(\mathbb C^n) = q^{-(n-1)} + q^{-(n-3)} + \cdots + q^{n-3} + q^{n-1} = (n)_{q,}
$$
where $q = e^{\varepsilon_1}$.  Then $\sl_2$ also acts on $\Sym^s(\mathbb C^n)$ with the character
\begin{equation}
\label{sl2symchar}
{\rm char}_{\sl_2} \Sym^s(\mathbb C^n) = \binom{s+n-1}{s}_{q,}
\end{equation}
the second guise of the $q$-binomial coefficient from Section \ref{ss:qbin}. (See \cite{gw}, Theorem 4.1.20.) Because $\mathfrak{gl}_n \cong {\rm End}(\mathbb C^n)$, and because $\mathbb C^n$ is a representation of $\sl_2$, there naturally exists a \textbf{principal embedding} $\sl_2 \hookrightarrow \mathfrak{gl}_n$, unique up to conjugation.  Hence it makes sense to restrict the $\mathfrak{gl}_n$-action on $\Sym^s(\mathbb C^n)$ to the principally embedded $\sl_2$.

Intuitively, we should regard $\Sym^s(\mathbb C^n)$ as a linearization of $\mathcal C(s,n)$, i.e., a vector space whose basis is in bijective correspondence with $\mathcal C(s,n)$: as a $\mathfrak{gl}_n$-representation, its basis consists of one weight vector $\prod_{i=0}^{n-1} e_i^{a_i}$ for each composition $\alpha = (a_0,\ldots,a_{n-1}) \in \mathcal C(s,n)$. (Here the $e_i$ are the standard basis vectors of $\mathbb C^n$, with indexing shifted down by 1.)  Since we want to compare $d$ compositions, we will study the $d$-fold tensor product
$$
V = \textstyle\bigotimes^d \Sym^s(\mathbb C^n).
$$

\subsection{Proof of Theorem \ref{thm:character}}

The vector space $V$ is an irreducible representation of $(\mathfrak{gl}_n)^d = \mathfrak{gl}_n \oplus \cdots \oplus \mathfrak{gl}_n$, with each copy of $\mathfrak{gl}_n$ acting on the corresponding tensor factor.  Restricting to the principally embedded $\sl_2$ in each copy of $\mathfrak{gl}_n$, we see that $V$ is also a representation of $(\sl_2)^d$.  Crucially, each copy of $\sl_2$ embeds into $\sl_d$, as follows.  For $i = 1,\dots,d-1$, let $\mathfrak s_i \subset \sl_d$ denote the image of the $\sl_2$-embedding given by the Lie algebra homomorphism
$$
\begin{bmatrix}
a & b \\
c & d
\end{bmatrix}
 \qquad \longmapsto \qquad
 \begin{matrix}
 & a\cdot E_{i,i} & +&  b\cdot E_{i,i+1} \\
 + & c \cdot E_{i+1,i} & + & d \cdot E_{i+1,i+1,}
 \end{matrix}
$$
where $E_{i,j}$ is the elementary matrix with 1 in position $(i,j)$ and 0's elsewhere.  Similarly, define $\mathfrak s_d \subset \sl_d$ as the image of the embedding
$$
\begin{bmatrix}
a & b \\
c & d
\end{bmatrix}
 \qquad \longmapsto \qquad
 \begin{matrix}
 -& a\cdot E_{1,1} & -&  c\cdot E_{1,d} \\
 - & b \cdot E_{d,1} & - & d \cdot E_{d,d}
 \end{matrix}
$$
via the negative transpose in the ``four corners.''

In this way, not only does each $\mathfrak s_i$ inherit (from $\sl_2$) a natural action on the $i^{\rm th}$ tensor factor of $V$, but this action extends to a (virtual) $\sl_d$-action, as follows.\footnote{In the following calculations, we must treat the special case $i=d$ differently: namely, replace all instances of $i+1$ by $1$, to respect the embedding $\mathfrak s_d$.}  We have \begin{align*}
    \mathbb C^d &\cong \text{span}\{e_i,\:e_{i+1}\} \oplus \text{span}\{e_1,\ldots,e_{i-1},\: e_{i+2},\ldots,e_d\}\\
    &\cong \mathbb C^2 \oplus \mathbb C^{d-2},
\end{align*}
where $\mathbb C^2$ is the defining representation of $\mathfrak s_i\cong \sl_2$, and $\mathbb C^{d-2}$ is the direct sum of $d-2$ copies of the trivial representation of $\sl_d$. In other words, we let $\mathfrak h \subset \sl_d$ act on $\mathbb C^d$ not as in the defining representation, but via
$$\text{diag}[h_1,\ldots,h_d] \cdot (v_1,\ldots,v_d)^\top = (0,\ldots,0,\:h_iv_i,\: h_{i+1}v_{i+1},\: 0,\ldots,0)^\top.$$  Hence we are setting $\varepsilon_j=0$ for all $j$ except $i$ and $i+1$, so that the character of this action is 
${\rm char}_{\sl_d}(\mathbb C^d) = e^{\varepsilon_i}+e^{\varepsilon_{i+1}} + (d-2).$
We then regard $\mathbb C^2$ as the formal difference $\mathbb C^d - \mathbb C^{d-2}$ of $\sl_d$-representations.  Recalling that $\varepsilon_i = -\varepsilon_{i+1}$ as $\mathfrak s_i$-weights, we have the virtual character 
\begin{align*}
    {\rm char}_{\sl_d}(\mathbb C^2) &= {\rm char}_{\sl_d}\mathbb C^d - (d-2)({\rm char}_{\sl_d} \mathbb C)\\
    &= e^{\varepsilon_i}+e^{\varepsilon_{i+1}}+(d-2) - (d-2)(1)\\
    &= e^{\varepsilon_i}+e^{\varepsilon_{i+1}}\\
    &= e^{\varepsilon_i}+e^{-\varepsilon_i}\\
    &= q_i + q_i^{-1} = {\rm char}_{\mathfrak s_i}(\mathbb C^2),
\end{align*}
where we write $q_i = e^{\varepsilon_i}$.
Hence, the $i^{\rm th}$ tensor factor $\Sym^s(\mathbb C^n) \cong \Sym^s(\Sym^{n-1}(\mathbb C^2))$ of $V$ also admits a virtual $\sl_d$-representation, whose character, by \eqref{sl2symchar}, is
$$
{\rm char}_{\sl_d}\Sym^s(\mathbb C^n) = \binom{s+n-1}{s}_{q_{i.}}
$$
But since $\varepsilon_i = -\varepsilon_{i+1}$, we have the substitution $x_i = q_i^2$, with $x_i$ as defined in \eqref{def:x_i}. Thus by \eqref{convertqbins}, we have
$$
{\rm char}_{\sl_d} \Sym^s(\mathbb C^n) = \binom{s+n-1}{s}_{q_i} = q_i^{-s(n-1)} \genfrac[]{0pt}{}{s+n-1}{s}_{x_{i.}}
$$
Multiplying all these $\sl_d$-characters for $i = 1,\ldots,d$ in order to obtain the character of the $d$-fold tensor product $V$, we have 
$$
{\rm char}_{\sl_d}(V) = \prod_{i=1}^d q_i^{-s(n-1)}\genfrac[]{0pt}{}{s+n-1}{s}_{x_{i.}}
$$
But by \eqref{sumepsilons}, we have $\prod_{i=1}^d q_i^{-s(n-1)} = \left(\prod_i e^{\varepsilon_i}\right)^{-s(n-1)} = \left( e^{\varepsilon_1 + \cdots + \varepsilon_d}\right)^{-s(n-1)} = (e^0)^{-s(n-1)}=1$, leaving us with
\begin{equation}
\label{char_sld}
{\rm char}_{\sl_d}(V) = \prod_{i=1}^d \genfrac[]{0pt}{}{s+n-1}{s}_{x_{i,}}
\end{equation}
which is the main claim of Theorem \ref{thm:character}.

It remains to show that the character \eqref{char_sld} encodes the distribution of $\mathcal D$-values on $\mathcal C(s,n)^d$.  By \eqref{qbinyoungfact}, the coefficient of $x_1^{w_1} \cdots x_d^{w_d}$ in the expansion of \eqref{char_sld} is the number of $d$-tuples of Young diagrams $(\alpha_1,\ldots,\alpha_d) \in \mathcal Y(s,\:n-1)^d$ such that $|\alpha_i|=w_i$.  But by \eqref{Tsize} and Definition \ref{def:Dgeneral}, this is the number of $d$-tuples $(\alpha_1 \ldots, \alpha_d) \in \mathcal C(s,n)^d$ such that $\mathcal D(\alpha_1, \ldots, \alpha_d) = [w_1, \ldots, w_d]$.  Making the substitution $x_d = (x_1 \cdots x_{d-1})^{-1}$ and using the dictionary in \eqref{rootlatticeiso}, we obtain a well-defined exponent vector for each $\mathcal D$-value. \qed

\begin{remark}
From this perspective of representation theory, the $(s,n) \longleftrightarrow (n-1, \: s+1)$ duality is a manifestation of \textbf{Hermite reciprocity}: as $\sl_2$-representations, 
\begin{align*}
    \Sym^s(\mathbb C^n) &\cong \Sym^s\left(\Sym^{n-1}\big(\mathbb C^2\big)\right)\\
    &\cong \Sym^{n-1}\left( \Sym^s\big(
    \mathbb C^2\big)\right)\\
    &\cong \Sym^{n-1}(\mathbb C^{s+1}).
\end{align*}
This can be seen directly from the $q$-binomial coefficient that expresses the $\sl_2$-character in \eqref{sl2symchar}.  Since the distribution of $\mathcal D$-values is completely determined by the $\sl_d$-action on $V$, which in turn is completely determined by the actions of copies of $\sl_2$, it is clear why $\mathcal C(s,n)^d$  must have the same $\mathcal D$-distribution as $\mathcal C(n-1,\:s+1)^d$. 
\end{remark}

\subsection{The first Wallach representation}
\label{wallach}

This subsection offers a deeper perspective into the representation theory of $V$ when $d=2$.  We present here the bare facts, referring the reader to \cite{ew}, page 343, and \cite{wallach} for details. 

When $d=2$, it turns out that $V=\Sym^s(\mathbb C^n) \otimes \Sym^s(\mathbb C^n)$ is the $s^{\rm th}$ graded component of an infinite-dimensional vector space $W_n$ known as the \textit{first Wallach representation} of the indefinite unitary group ${\rm U}(n,n)$.  The underlying space of this representation is
\begin{align*}
    W_n & \coloneqq \mathbb C[x_1,\ldots,x_n,y_1,\ldots,y_n]^{\GL_1}\\
    & \cong \mathbb C[\mathscr D_n],
\end{align*}
the coordinate ring of the determinantal variety $\mathscr D_n$ of $n \times n$ complex matrices with rank at most 1.  In the first line above, the superscript denotes the $\GL_1$-invariants in the polynomial ring, where $g \in \GL_1 \cong \mathbb C^\times$ acts on the polynomial function $f$ via
$$
(g \cdot f)(x_1,\ldots,x_n,y_1, \ldots, y_n) = f(g^{-1}x_1, \ldots, g^{-1}x_n, gy_1,\ldots,gy_n).
$$
It follows that $W_n$ is generated as an algebra by the monomials $x_iy_j$, for $1 \leq i,j \leq n$.  (This is a special case of the First Fundamental Theorem of Invariant Theory; see \cite{gw}, Theorem 5.2.1.)  Therefore, letting $\mathbb C[\cdot]^s$ denote the subspace of degree-$s$ homogeneous polynomial functions,
\begin{align*}
    W_n & = \bigoplus_{s=0}^\infty W_n^s\\
    &=\bigoplus_{s=0}^\infty \mathbb C[x_1,\ldots,x_n]^s \otimes \mathbb C[y_1,\ldots,y_n]^s\\
    &\cong \bigoplus_{s=0}^\infty \Sym^s(\mathbb C^n)\otimes \Sym^s(\mathbb C^n).
\end{align*}
In the context of our paper, given $s$ and $n$, we then have $V \cong W_n^s$.  It is clear how the monomial $x_1^{a_1} \cdots x_n^{a_n} y_1^{b_1}\cdots y_n^{b_n}$ corresponds (via the exponent vectors for the $x_i$ and $y_i$) to a composition pair in $\mathcal C(s,n) \times \mathcal C(s,n)$.  As we observed earlier in this section, $V \cong W_n^s$ is naturally a representation of $\mathfrak{gl}_n \oplus \mathfrak{gl}_n$.  The full picture, however, is that all of $W_n$ is a representation of $\mathfrak u(n,n)$.  By restricting the action to the maximal compact\footnote{By a ``compact Lie algebra'' we mean the Lie algebra of a compact Lie group, in this case ${\rm U}(n) \times {\rm U}(n)$.} subalgebra $\mathfrak u(n) \oplus \mathfrak u(n)$ and then complexifying, we have an action of $\mathfrak{gl}_n \oplus \mathfrak{gl}_n$, given (up to a central shift) by the Euler operators $$x_i \frac{\partial}{\partial x_j} \quad \text{and} \quad y_i \frac{\partial}{\partial y_{j.}}$$  Returning to our mental image from the introduction, we can regard each of these operators as acting on one of the two compositions by moving one pebble from pile $j$ to pile $i$.  But if we consider the full action of $\mathfrak u(n,n)$ (and hence of its complexification $\mathfrak{gl}_{2n}$), rather than just the restriction to $\mathfrak{gl}_n \oplus \mathfrak{gl}_n$, then the graded component $W_n^s$ is no longer preserved since there are ``raising'' and ``lowering'' operators of the forms $$\frac{\partial^2}{\partial x_i \partial y_j} \quad \text{and} \quad x_i y_{j,}$$
which decrease or increase the value of $s$ by 1, by removing or adding one pebble from/to each composition.  (See \cite{cew}, Section 2, for the $\mathfrak{gl}_{2n}$-action written out explicitly in terms of these differential operators.)

\section{A generating function}
\label{s:genfun}

In \cite{kretschmann}, for the $d=2$ case, a recursive definition is given for a generating function that keeps track of the number of composition pairs with given EMC and given weighted totals.  Because of the recursive nature of the definition, we must formally consider composition pairs with unequal numbers of ``piles'' ($n$ and $m$).  As noted in \cite{bw}, the EMC is still defined on $\mathcal C(s,n) \times \mathcal C(s,m)$ since we can append zeros so that all compositions are tuples of length $\max\{n,m\}$.  We do not consider the statistical meaning of the EMC in such a scenario; the unequal pile-numbers are just a means to obtain our recursion.

\begin{proposition}
\label{genfun}
Formally, let 
\begin{equation}
    \label{H_nm}
H_{n,m}(q,x,y,t) \coloneqq \sum_{s=0}^\infty \left(\sum_{\substack{\alpha \in \mathcal C(s,n),\\ \beta \in \mathcal C(s,m)}}q^{\EMC(\alpha,\beta)}x^{\mathcal T(\alpha)} y^{\mathcal T(\beta)} \right)t^s,
\end{equation}
so that the coefficient of $t^s$ is a polynomial whose coefficients give the number of composition pairs in $\mathcal C(s,n)\times \mathcal C(s,m)$ with given EMC and given weighted totals.  Then we have the recursion
\begin{equation} 
\label{H_nm recur}
H_{n,m}=\frac{H_{n-1,m}+H_{n,m-1}-H_{n-1,m-1}}{1-q^{C(n,m)}x^{n-1}y^{m-1}t}
\end{equation}
where $H_{1,1}=\frac{1}{1-t}$, and $H_{0,m}=H_{n,0}=0$.
\end{proposition}
 The proof given in \cite{kretschmann} is a specialization of that from \cite{bw}.  Here, however, we use our main result to give a short proof entirely in terms of Young diagrams.
 
 \begin{proof}
 By Corollary \ref{d=2} and by \eqref{Tsize}, we can reinterpret the generating function \eqref{H_nm} in terms of Young diagrams:
 \begin{equation*}
     H_{n,m}(q,x,y,t)=\sum_{s=0}^\infty \left(\sum_{\substack{\alpha \in \mathcal Y(s,\:n-1),\\ \beta \in \mathcal Y(s,\:m-1)}}q^{|\alpha \triangle \beta|}x^{|\alpha|} y^{|\beta|} \right)t^s.
 \end{equation*}
 For the base case $H_{1,1}$, it is clear that $\mathcal Y(s,0)$ contains only the empty diagram, so the coefficient of $t^s$ has only one term; since the empty diagram has size 0, the exponents of $x$ and $y$ in this term are both 0.  Moreover, the symmetric difference of two empty diagrams is 0, so the exponent of $q$ is also 0.  Hence the coefficient of $t^s$ is $q^0 x^0 y^0=1$, so $H_{1,1}=1+t+t^2 +\cdots = \frac{1}{1-t}$.  In case $n$ or $m$ is 0, we have $\mathcal Y(s,\:-1)=\varnothing$, since a Young diagram cannot have a negative number of columns.
 
 Now we consider $H_{n,m}$ in general. For any pair $(\alpha,\beta)$ in the inside sum, the diagram $\alpha$ has a certain number $r_\alpha$ of maximal rows (length $n-1$) at the top, and likewise $\beta$ has a certain number $r_\beta$ of maximal rows (length $m-1$) at the top.  Hence we can remove $r:=\min\{r_\alpha,r_\beta\}$ maximal rows from each diagram.  Since $t$ tracks the number of rows in each diagram, each removed row-pair contributes 1 to the exponent of $t$.  Note that the symmetric difference of a maximal row from $\alpha$ and a maximal row from $\beta$ is exactly $|n-m|=C(n,m)$, so each of the removed row-pairs contributes $C(n,m)$ to the exponent of $q$.  Moreover, each removed row-pair contributes the size $n-1$ to the exponent of $x$, and $m-1$ to the exponent of $y$.  Therefore we see that from each term in $H_{nm}$ we can factor out $(q^{C(n,m)}x^{n-1}y^{m-1}t)^r$ for some $r$, leaving us with a pair of diagrams \emph{at least one of which contains no maximal rows}; that is, at least one of them can fit inside a rectangle with one less column than before.  Hence, starting with $H_{nm}$ and factoring out the reciprocal of the denominator in \eqref{H_nm recur}, the remaining terms are precisely those appearing in $H_{n-1,m}$ or $H_{n,m-1}$.  After correcting for double-counting the terms appearing in both, we have the numerator of \eqref{H_nm recur}, and so we are done. \qed
 \end{proof}
 
 To create the plots in Figures \ref{fig:d2plotssmall}--\ref{fig:d2plots3d}, we make the substitutions
$$
x = z, \qquad y = z^{-1}
$$
so that the exponent of $z$ in each term encodes $\mathcal D(\alpha,\beta)$.  Moreover, the generating function $H_{n,m}$ naturally generalizes to an arbitrary number $d$ of compositions, following the methods in \cite{erickson}: the numerator of $H_{(n_1,\ldots,n_d)}$ simply contains a longer alternating sum to extend the inclusion--exclusion
 argument to $d$ Young diagrams, and the denominator becomes $1-q^{C(n_1,\ldots,n_d)}x_1^{n_1-1}\cdots x_d^{n_d-1}t$.  Once again, the encoded results can be interpreted either statistically --- in terms of the EMC and weighted totals $\mathcal T$ of compositions --- or combinatorially --- in terms of the unimodal symmetric difference $\blacktriangle$ and sizes $|\cdot|$ of Young diagrams. 
 
 \subsection{Closed-form examples} We first examine the specific case $H_2:=H_{2,2}$, which encodes information about the EMC and weighted totals of composition pairs in $\mathcal C(s,2)$.  Either by hand or by software, we use the recursion \eqref{H_nm recur} to find
 \begin{equation*}
     H_2 = \frac{1 - q^2 x y t^2}{(1 - t) (1 - x y t) (1 - q x t) (1 - q y t).}
 \end{equation*}
 We interpret this in terms of Young diagram pairs, as above.   In the denominator, each of the four factors corresponds to one of the ways to choose a row in each diagram simultaneously: $(1-t)$ is an empty row in both diagrams, $(1-xyt)$ is a 1-cell row in both diagrams, $(1-q x t)$ is a 1-cell row in $\alpha$ only (hence contributing 1 to the symmetric difference), and $(1-q y t)$ is a 1-cell row in $\beta$ only (again contributing 1 to the symmetric difference).  But we cannot choose just any combination of these four row-pairs and still obtain a pair of Young diagrams: specifically, we cannot choose rows from \textit{both} the third and fourth factors, since it is impossible for a Young diagram to have a nonempty row below an empty row.  This explains the numerator $1-q^2 xy t^2$, which effectively kills any term containing the product $(q x t)(q y t)$.
 
 For values of $n$ greater than 2, the closed form of $H_n$ spills over into several lines, or pages, of text; an explicit (as opposed to recursive) formula involves an enormous alternating sum of least common multiples, ranging over the power set of a certain set of monomials (see the partial order we define below, and consider the set of noncomparable pairwise products).  As an illustrative example, we take $n=3$ and inspect the denominator of $H_3$:
 $$
 (1-t)(1- xyt) (1-x^2 y^2 t) (1-q x t) (1 - q y t) (1 - q x^2 y t) (1 - q x y^2t) (1 - q^2 x^2 t) (1 - q^2 y^2 t)
 $$
 Again, each of these factors describes one way to choose a row in each diagram simultaneously, where the rows may now contain 0, 1, or 2 cells; notice that the exponent of $q$ is always the difference between those of $x$ and $y$.  But again, we cannot choose just any combination of row-pairs to build a pair of Young diagrams.  This time, the ``forbidden'' combinations seem more daunting to describe; to resolve this, we put a partial order on monomials (ignoring the $q$ and $t$ exponents), such that $x^a y^b \preceq x^{a^\prime} y^{b^\prime}$ if and only if $a \leq a'$ and $b \leq b'$.  We now see that two given row-pairs can coexist in $\alpha$ and $\beta$ if and only if their monomials are comparable under our partial order. (This is a combinatorial  translation of the ``matrix straightening'' from \cite{bw} via modding out by a determinantal ideal.)  Hence the ``forbidden'' combinations of factors are precisely those which contain the product of two noncomparable monomials from the denominator.  This necessitates an alternating sum of terms in the numerator, which (despite many cancellations) quickly becomes intractable as $n$ increases, making the recursive definition the only viable computational approach.  
 
 The coefficient of $t^2$ in the expansion of $H_3$ is
 \begin{align*}
 &1 + x y + 2 x^2 y^2 + x^3 y^3 + x^4 y^4 \\&+ q( x + y + 2x^2 y + 
 2x y^2 + 2x^3 y^2 + 2x^2 y^3+ x^4 y^3 + x^3 y^4)\\
 &+q^2(2 x^2 + x^3 y + 2 y^2 + 2 x^2 y^2 + 2 x^4 y^2 + 
 x y^3 + 2 x^2 y^4 )\\
 &+q^3(x^3+ x^4 y+ y^3+ 
 x y^4) \\
 &+q^4(x^4 + y^4).
 \end{align*}
 The reader can verify that these indeed encode all 36 ordered pairs of Young diagrams fitting inside a $2 \times 2$ rectangle, along with the sizes of the diagrams and the symmetric difference between them. The reader can also compare this expansion with the second plot in Figure \ref{fig:d2plotssmall}, where $s=2$ and $n=3$.

\section*{Declarations}
Funding: not applicable.

\noindent Conflict of interest: the author declares that he has no conflict of interest.

\noindent Availability of data and material: not applicable.

\noindent Code availability: not applicable.
 
\bibliographystyle{spmpsci}

