A relation between two enumeration problems It's easy to see the number of non-negative solution of the equation $\sum_{k=1}^nx_k=r$ (each $x_k$ is an integer) and the number of sequence $1\leq u_1\leq\cdots\leq u_r\leq n$ are equal: both equal $n+r-1\choose r$. So I think there should be a natural bijection between them, but what is it?
 A: Given a non-negative integer solution to $\sum_{k=1}^n x_k = r$, associate the sequence $u_i$ as follows.  For each $1 \leq i \leq r$, let $1 \leq u_i \leq n$ be the unique index such that $\sum_{k=1}^{u_i} x_k \geq i$, while $\sum_{k=1}^{u_i-1} x_k < i$.  It is easy to see that $1 \leq u_1 \leq u_2 \leq \cdots \leq u_r \leq n$, and that this map is invertible.
For example, if $n=4$ and $r=7$, the bijection sends the solution $(4,2,0,1)$ to $(1,1,1,1,2,2,4)$.  Conversely, given the sequence $(1,1,3,3,3,4,4)$, the solution is $(2,0,3,2)$.
Edit: Explicitly, the inverse map is given by sending a sequence $(u_1,u_2,\dots,u_r)$ to the solution $(x_1,x_2,\dots,x_n)$, where $x_i$ is equal to the number of times that $i$ appears in the sequence $u_1, u_2, \dots, u_r$.  That is, $x_i = \# \{1 \leq j \leq r: u_j = i \}$.
Less formally, the map from $x$'s to $u$'s is given by writing each number $1 \leq i \leq n$ $x_i$ times in the sequence $u$, while the map from $u$'s to $x$'s is given by letting $x_i$ be the number of times $i$ appears in the $u$ sequence.
