Problem: Steve is piling $m\geq 1$ indistinguishable stones
on the squares of an $n\times n$ grid.
Each square can have an arbitrarily high pile of stones.
After he finished piling his stones in some manner,
he can then perform \emph{stone moves}, defined as follows.
Consider any four grid squares, which are corners of a rectangle,
i.e.\ in positions $(i, k)$, $(i, l)$, $(j, k)$, $(j, l)$
for some $1\leq i, j, k, l\leq n$, such that $i<j$ and $k<l$.
A stone move consists of either removing one stone from each of
$(i, k)$ and $(j, l)$ and moving them to $(i, l)$ and $(j, k)$ respectively,
or removing one stone from each of $(i, l)$ and $(j, k)$
and moving them to $(i, k)$ and $(j, l)$ respectively.

Two ways of piling the stones are equivalent if they can be obtained
from one another by a sequence of stone moves.
How many different non-equivalent ways can Steve pile the stones on the grid?

\end{enumerate}

Solution: The answer is $\binom{m+n-1}{n-1}^2$.
The main observation is that the ordered sequence of column counts
(i.e.\ the number of stones in the first, second, etc.\ column)
is invariant under stone moves, as does the analogous sequence of row counts.

\paragraph{Definitions.}
Call these numbers $(c_1, c_2, \dots, c_n)$
and $(r_1, r_2, \dots, r_n)$ respectively,
with $\sum c_i = \sum r_i = m$.
We say that the sequence $(c_1, \dots, c_n, r_1, \dots, r_n)$
is the \emph{signature} of the configuration.
These are the $2m$ blue and red numbers shown in the example below
(in this example we have $m=8$ and $n=3$).
\begin{center}
\begin{asy}
  unitsize(1.5cm);
  for (int i=0; i<=3; ++i) {
    draw( (0,i)--(3,i), gray );
    draw( (i,0)--(i,3), gray );
  }
  label("$c_1=\boxed{5}$", (0.5,3), dir(90), blue);
  label("$c_2=\boxed{2}$", (1.5,3), dir(90), blue);
  label("$c_3=\boxed{1}$", (2.5,3), dir(90), blue);

  label("$r_1=\boxed{3}$", (0,2.5), dir(180), red);
  label("$r_2=\boxed{3}$", (0,1.5), dir(180), red);
  label("$r_3=\boxed{2}$", (0,0.5), dir(180), red);

  real r = 0.1;
  filldraw(circle((0.3,2.7), r), gray, black);
  filldraw(circle((0.6,2.4), r), gray, black);
  filldraw(circle((1.4,2.3), r), gray, black);
  filldraw(circle((0.6,1.7), r), gray, black);
  filldraw(circle((0.4,1.4), r), gray, black);
  filldraw(circle((0.7,0.5), r), gray, black);
  filldraw(circle((2.4,1.6), r), gray, black);
  filldraw(circle((1.6,0.4), r), gray, black);
  label("Signature: $(5,2,1;3,3,2)$", (1.5,0), dir(-90));
\end{asy}
\end{center}
By stars-and-bars, the number of possible values $(c_1, \dots, c_n)$
is $\binom{m+n-1}{n-1}$.
The same is true for $(r_1, \dots, r_n)$.
So if we're just counting \emph{signatures},
the total number of possible signatures is $\binom{m+n-1}{n-1}^2$.

\paragraph{Outline and setup.}
We are far from done.
To show that the number of non-equivalent ways is also this number,
we need to show that signatures correspond to pilings.
In other words, we need to prove:
\begin{enumerate}
  \ii Check that signatures are invariant around moves
  (trivial; we did this already);
  \ii Check conversely that two configurations
  are equivalent if they have the same signatures
  (the hard part of the problem); and
  \ii Show that each signature is realized by at least
  one configuration (not immediate, but pretty easy).
\end{enumerate}

Most procedures to the second step are algorithmic in nature,
but Ankan Bhattacharya gives the following far cleaner approach.
Rather than having a grid of stones,
we simply consider the multiset of ordered pairs $(x,y)$
corresponding to the stones.
Then:
\begin{itemize}
  \ii a stone move corresponds to switching two $y$-coordinates
  in two different pairs.
  \ii we \emph{redefine} the signature to be the multiset $(X,Y)$
  of $x$ and $y$ coordinates which appear.
  Explicitly, $X$ is the multiset that contains $c_i$ copies
  of the number $i$ for each $i$.
\end{itemize}
For example, consider the earlier example which had
\begin{itemize}
  \ii Two stones each at $(1,1)$, $(1,2)$.
  \ii One stone each at $(1,3)$, $(2,1)$, $(2,3)$, $(3,2)$.
\end{itemize}
Its signature can then be reinterpreted as
\[
  (5,2,1; 3,3,2)
  \longleftrightarrow
  \begin{cases}
    X = \{1,1,1,1,1,2,2,3\} \\
    Y = \{1,1,1,2,2,2,3,3\}.
  \end{cases}
\]
In that sense, the entire grid is quite misleading!

\paragraph{Proof that two configurations with the same signature are equivalent.}
The second part is completed just because
transpositions generate any permutation.
To be explicit, given two sets of stones,
we can permute the labels so that the first set is
$(x_1, y_1)$, \dots, $(x_m, y_m)$ and
the second set of stones is
$(x_1, y_1')$, \dots, $(x_m, y_m')$.
Then we just induce the correct permutation on $(y_i)$ to get $(y_i')$.

\paragraph{Proof that any signature has at least one configuration.}
Sort the elements of $X$ and $Y$ arbitrarily (say, in non-decreasing order).
Put a stone whose $x$-coordinate is the $i$th element of $X$,
and whose $y$-coordinate is the $i$th element of $Y$,
for each $i = 1, 2, \dots, m$.
Then this gives a stone placement of $m$ stones with signature $(X,Y)$.

For example, if
\begin{align*}
  X &= \{1,1,1,1,1,2,2,3\} \\
  Y &= \{1,1,1,2,2,2,3,3\}
\end{align*}
then placing stones at
$(1,1)$, $(1,1)$, $(1,1)$, $(1,2)$, $(1,2)$, $(2,2)$, $(2,3)$, $(3,3)$
gives a valid piling with this signature.