Denote by $C(n, k, r)$ the number of integer tuples $(x_1, x_2, \cdots, x_k)$ satisfying following conditions. $x_1 \geq x_2 \geq \cdots \geq x_k \geq 0$ $x_1+x_2+ \cdots +x_k = n$ $x_1 \leq r$ Claim 1. $C(n, k, r) = C(n, r, k)$ for all $n, k, r$. Proof. It's easily proved using Ferrers diagram. Now let $m = sq + r_s$ where $q, r_s$ are integers such that $0\leq r_s < s$. Claim 2. $\displaystyle A(m, s, t) = \sum_{i=0}^q C(m-is, s-1, t)$ Proof. We divide cases by the minimum value of the integer partition. Pick any integer partition satisfying the condition of $A(m, s, t)$. If $i$ is the minimum value of this partition, (in other words, $x_s = i$) from the third condition we have $x_1 - i \leq t$. Then we can make one-to-one correspondence such that $(x_1, x_2, \cdots, x_s)$ correspond to $(x_1-i, x_2-i, \cdots, x_{s-1} - i)$, which is a integer partition satisfying the condition of $C(m-is, s-1, t)$. Since $i$ can vary from $0$ to $q$, Claim 2 is proved. Claim 3. $\displaystyle A(m, t, s) = \sum_{i=0}^q C(m-is, t, s-1)$ Proof. For any partition $(x_1, x_2, \cdots, x_t)$ satisfying the condition of $A(m, t, s)$, we do the following operation repetitively. Operation 1. If $x_1 \geq s$, for $a=0, 1, \cdots, s-1$, subtract $1$ from $x_j$ where $j$ is the maximum index such that $x_j \geq x_1 - a$. Operation should be performed in order of $a=0, 1, \cdots, s-1$. Then the total sum of $(x_1, x_2, \cdots, x_t)$ will decrease by $s$. This operation will be terminated when $x_1 \leq s-1$ is satisfied. Let $(z_1, z_2, \cdots, z_t)$ be the resulting integer tuple after operation is terminated. If the operation is repeated $i$ times, $\displaystyle \sum_{i=1}^t z_i = m-is$ will hold. Furthermore, $(z_1, z_2, \cdots, z_t)$ is a integer tuple satisfying the condition of $C(m-is, t, s-1)$. Now it suffices to check the converse operation that can make $(z_1, z_2, \cdots, z_t)$ correspond to $(x_1, x_2,\cdots, x_t)$ to show that there exist a one-to-one correspondence between $A(m, t, s)$ and $ \sum_{i=0}^q C(m-is, t, s-1)$. Converse operation would be the following. Let $(z_1, z_2, \cdots, z_t)$ be the tuple satisfying the condition of $C(m-is, t, s-1)$. We will do the operation exactly $i$ times and make a tuple $(x_1, x_2, \cdots, x_t)$ satisfying the condition of $A(m, t, s)$ such that if we do Operation 1 to $(x_1, x_2, \cdots, x_t)$ we get $(z_1, z_2, \cdots, z_t)$. Operation 2. For $a=0, 1, \cdots, s-1$, add $1$ to $z_j$ where $j$ is the maximum index such that $z_j \geq z_t + a$. It's quite straightforward to verify that the resulting tuple $(x_1, x_2, \cdots, x_t)$ is transformed into the original tuple $(z_1, z_2, \cdots, z_t)$ by Operation 1. Hence one-to-one correspondence exists, and Claim 3 is proved. Finally \[ A(m, s, t) = \sum_{i=0}^q C(m-is, s-1, t) = \sum_{i=0}^q C(m-is, t, s-1) =A(m, t, s) \]finishes the proof.

A proof without words:

Attachments:

This is essentially the same as above, but more formally. For a positive integer $n$ define $[n]=\{1,\ldots,n\}$ for brevity. Let $X(m,s,t)$ be the set of integer tuples $(x_1, x_2, \ldots, x_s)$ satisfying the following conditions. $x_1 \ge x_2 \ge \cdots \ge x_s \ge 0$ $x_1+x_2+ \cdots +x_s = m$ $x_1-x_s \le t$ Moreover, let $Y(m,s,t)$ be the set of all $s\times t$ tables $A$ of nonnegative integers satisfying the following conditions: $A_{i,j}\ge A_{i',j'}$ whenever $i\le i'$ and $j\le j'$, $\sum_{(i,j)\in[s]\times[t]}A_{i,j}=m$, and the absolute difference between any two numbers in the same row or column of $A$ is at most $1$. We construct functions $$X(m,s,t)\leftrightarrow Y(m,s,t).$$ Let us explain each construction: $X(m,s,t)\to Y(m,s,t)$: Given a tuple $(x_1,\ldots,x_s)$ in $X(m,s,t)$, define an $s\times t$ table $A$ by $A_{i,j}=\left|\{k\in\mathbb N\left|\right. k\equiv j\pmod{t},\;k\le x_i\}\right|$ for all $(i,j)\in[s]\times[t]$. This way, the sum of elements in row $i$ is $x_i$, so in particular $\sum_{(i,j)\in[s]\times[t]}A_{i,j}=m$. Moreover we have $A_{i,j}=1+\left\lfloor\frac{x_i-j}{t}\right\rfloor$. Hence $A_{i,j}\ge A_{i',j'}$ whenever $i\le i'$ and $j\le j'$. Now let $i,i'\in[s]$ and $j,j'\in[t]$ be arbitrary indices. Since $\left|x_i-x_{i'}\right|\le t$ we have $\left|A_{i,j}-A_{i',j}\right|\le 1$. Finally, since $\left|j-j'\right|<t$ we have $\left|A_{i,j}-A_{i,j'}\right|\le 1$. $Y(m,s,t)\to X(m,s,t)$: Suppose we are given a table $A\in Y(m,s,t)$. For every $i\in[s]$ define $x_i=\sum_{j\in[t]}A_{i,j}$. The condition of decreasing cells guarantees that $x_1\ge x_2\ge\ldots\ge x_s$. Moreover, the last condition guarantees that $x_1-x_s\le t$. It is easy to prove that both constructions are inverses of each other. To finish the problem, note that there is a bijection $Y(m,s,t)\to Y(m,t,s)$ given by reflection.

So this is actually "stacking" the layers math90 wrote: This is essentially the same as above, but more formally. For a positive integer $n$ define $[n]=\{1,\ldots,n\}$ for brevity. Let $X(m,s,t)$ be the set of integer tuples $(x_1, x_2, \ldots, x_s)$ satisfying the following conditions. $x_1 \ge x_2 \ge \cdots \ge x_s \ge 0$ $x_1+x_2+ \cdots +x_s = m$ $x_1-x_s \le t$ Moreover, let $Y(m,s,t)$ be the set of all $s\times t$ tables $A$ of nonnegative integers satisfying the following conditions: $A_{i,j}\ge A_{i',j'}$ whenever $i\le i'$ and $j\le j'$, $\sum_{(i,j)\in[s]\times[t]}A_{i,j}=m$, and the absolute difference between any to numbers in the same row or column of $A$ is at most $1$. We construct functions $$X(m,s,t)\leftrightarrow Y(m,s,t).$$ Let us explain each construction: $X(m,s,t)\to Y(m,s,t)$: Given a tuple $(x_1,\ldots,x_s)$ in $X(m,s,t)$, define an $s\times t$ table $A$ by $A_{i,j}=\left|\{k\in\mathbb N\left|\right. k\equiv j\pmod{t},\;k\le x_i\}\right|$ for all $(i,j)\in[s]\times[t]$. This way, the sum of elements in row $i$ is $x_i$, so in particular $\sum_{(i,j)\in[s]\times[t]}A_{i,j}=m$. Moreover we have $A_{i,j}=1+\left\lfloor\frac{x_i-j}{t}\right\rfloor$. Hence $A_{i,j}\ge A_{i',j'}$ whenever $i\le i'$ and $j\le j'$. Now let $i,i'\in[s]$ and $j,j'\in[t]$ be arbitrary indices. Since $\left|x_i-x_{i'}\right|\le t$ we have $\left|A_{i,j}-A_{i',j}\right|\le 1$. Finally, since $\left|j-j'\right|<t$ we have $\left|A_{i,j}-A_{i,j'}\right|\le 1$. $Y(m,s,t)\to X(m,s,t)$: Suppose we are given a table $A\in Y(m,s,t)$. For every $i\in[s]$ define $x_i=\sum_{j\in[t]}A_{i,j}$. The condition of decreasing cells guarantees that $x_1\ge x_2\ge\ldots\ge x_s$. Moreover, the last condition guarantees that $x_1-x_s\le t$. It is easy to prove that both constructions are inverses of each other. To finish the problem, note that there is a bijection $Y(m,s,t)\to Y(m,t,s)$ given by reflection.