[proofplan]
We encode the pooled sample as one exchangeable vector of length $N=m+n$, keeping track of which coordinates came from the $X$ sample. Continuity of the common distribution gives no ties with probability one, so the ordered positions are well-defined. Exchangeability implies that every strict ordering of the $N$ observations is equally likely; hence the set of ordered positions occupied by the $X$ labels is uniform over all $m$-element subsets of $\{1,\dots,N\}$. The rank-sum statistic is exactly the sum of those selected positions, which gives the claimed subset-sum law.
[/proofplan]
[step:Encode the pooled observations and eliminate ties]
Set $N := m+n$. Let $(\Omega,\mathcal{F},\mathbb{P})$ denote the probability space on which the random variables $X_1,\dots,X_m,Y_1,\dots,Y_n$ are defined. For each $k \in \{1,\dots,N\}$, define the real-valued [random variable](/page/Random%20Variable) $Z_k: \Omega \to \mathbb{R}$ by setting $Z_k := X_k$ when $1 \leq k \leq m$ and $Z_k := Y_{k-m}$ when $m+1 \leq k \leq N$. Define the pooled random vector $Z: \Omega \to \mathbb{R}^N$ by $Z(\omega) := (Z_1(\omega),\dots,Z_N(\omega))$ for $\omega \in \Omega$.
Define the deterministic label map $\ell: \{1,\dots,N\} \to \{X,Y\}$ by $\ell(k)=X$ if $1 \leq k \leq m$ and $\ell(k)=Y$ if $m+1 \leq k \leq N$.
Let
\begin{align*}
E := \{Z_a \neq Z_b \text{ for all distinct } a,b \in \{1,\dots,N\}\}.
\end{align*}
Since the common distribution is continuous, each difference event $\{Z_a=Z_b\}$ has probability $0$. By the finite union bound,
\begin{align*}
\mathbb{P}(E^c)
\leq
\sum_{1 \leq a < b \leq N} \mathbb{P}(Z_a=Z_b)
=
0.
\end{align*}
Thus $\mathbb{P}(E)=1$, and ranks may be computed on $E$ without ambiguity.
[/step]
[step:Show that every strict ordering of the pooled sample has equal probability]
For a permutation $\pi$ of $\{1,\dots,N\}$, define the event
\begin{align*}
E_\pi := \{Z_{\pi(1)} < Z_{\pi(2)} < \cdots < Z_{\pi(N)}\}.
\end{align*}
The events $(E_\pi)_\pi$ are disjoint and their union is $E$. Because $Z_1,\dots,Z_N$ are independent and identically distributed, the random vector $Z$ is exchangeable: for every permutation $\sigma$ of $\{1,\dots,N\}$, the vector $(Z_{\sigma(1)},\dots,Z_{\sigma(N)})$ has the same distribution as $(Z_1,\dots,Z_N)$. Therefore $\mathbb{P}(E_\pi)$ is the same for every permutation $\pi$. Since $\mathbb{P}(E)=1$ and there are $N!$ permutations,
\begin{align*}
\mathbb{P}(E_\pi)=\frac{1}{N!}
\end{align*}
for every $\pi$.
[/step]
[step:Convert uniform orderings into uniform subsets of rank positions]
For each $m$-element subset $A \subset \{1,\dots,N\}$, define
\begin{align*}
F_A := \{\{R_1^X,\dots,R_m^X\}=A\}.
\end{align*}
On the no-tie event $E$, the event $F_A$ occurs exactly when the ordered positions in $A$ are occupied by the $m$ coordinates whose labels are $X$.
Fix $A \in \mathcal{A}_{m,N}$. The number of permutations $\pi$ satisfying $E_\pi \subset F_A$ is $m!n!$: the $m$ indices from $\{1,\dots,m\}$ may be assigned to the positions in $A$ in $m!$ ways, and the $n$ indices from $\{m+1,\dots,N\}$ may be assigned to the complementary positions in $n!$ ways. Hence
\begin{align*}
\mathbb{P}(F_A)
=
\sum_{\pi : E_\pi \subset F_A} \mathbb{P}(E_\pi)
=
m!n! \cdot \frac{1}{N!}
=
\frac{1}{\binom{N}{m}}.
\end{align*}
Thus $\{R_1^X,\dots,R_m^X\}$ is uniformly distributed over $\mathcal{A}_{m,N}$.
[guided]
The goal is to pass from uniformity of complete orderings to uniformity of the smaller object we care about: the set of rank positions occupied by the $X$ observations.
Fix an $m$-element subset $A \subset \{1,\dots,N\}$, and define
\begin{align*}
F_A := \{\{R_1^X,\dots,R_m^X\}=A\}.
\end{align*}
This event says that, after sorting the pooled observations from smallest to largest, exactly the positions in $A$ carry an $X$ label.
Now count how many strict orderings produce this event. A strict ordering is represented by a permutation $\pi$ through
\begin{align*}
E_\pi := \{Z_{\pi(1)} < Z_{\pi(2)} < \cdots < Z_{\pi(N)}\}.
\end{align*}
For $E_\pi$ to imply $F_A$, the positions in $A$ must be filled by the $m$ indices $1,\dots,m$, which are exactly the coordinates corresponding to $X_1,\dots,X_m$. These $m$ indices can be arranged among the positions in $A$ in $m!$ ways. The remaining $n$ positions must be filled by the indices $m+1,\dots,N$, corresponding to $Y_1,\dots,Y_n$, and these can be arranged in $n!$ ways. Therefore the number of strict orderings that lead to the same rank-position set $A$ is
\begin{align*}
m!n!.
\end{align*}
From the previous step, every strict ordering has probability $1/N!$. Since the events $E_\pi$ are disjoint, we add their probabilities:
\begin{align*}
\mathbb{P}(F_A)
=
\sum_{\pi : E_\pi \subset F_A} \mathbb{P}(E_\pi)
=
m!n! \cdot \frac{1}{N!}
=
\frac{m!n!}{N!}
=
\frac{1}{\binom{N}{m}}.
\end{align*}
This value is independent of the chosen subset $A$. Hence every $m$-element subset of rank positions is equally likely.
[/guided]
[/step]
[step:Identify the rank-sum law with the subset-sum law]
Let $U$ be a random subset uniformly distributed over $\mathcal{A}_{m,N}$. The preceding step shows that the random set $\{R_1^X,\dots,R_m^X\}$ has the same distribution as $U$. Since
\begin{align*}
S_X = \sum_{i=1}^m R_i^X = \sum_{r \in \{R_1^X,\dots,R_m^X\}} r,
\end{align*}
we obtain
\begin{align*}
S_X \stackrel{d}{=} \sum_{r \in U} r.
\end{align*}
Consequently, for every integer $s$,
\begin{align*}
\mathbb{P}(S_X=s)
=
\frac{1}{\binom{N}{m}}
\#\left\{A \in \mathcal{A}_{m,N} : \sum_{r \in A} r = s\right\}.
\end{align*}
The right-hand side depends only on $m$ and $n$, so the exact rank-sum null law is distribution-free under the two-sample null.
[/step]
