Bijection between sets and multisets I know that there are ${n+k-1 \choose k}$ multisets of size $k$ of a subset of size $n$.  This means that there must be a bijection between multisets of size $k$ of a set of size $n$ and subsets of size $k$ of a set of size $n+k-1$.  A specific example is the number of multisets of size $3$ of a $5$ element set is the same the number of substs of size $3$ of a $7$ element set ($3 + 5 - 1 = 7$).  I found an illustration of this specific bijection on wikipedia (https://en.wikipedia.org/wiki/File:Combinations_with_repetition;_5_multichoose_3.svg).
Does anyone know of a general bijection using $n$ and $k$ rather than specific numbers?
 A: The usual stars and bars technique for proving the multiset formula also gives the desired bijection.  That is we have two bijections:

Multisets of size $k$ taken from a set with $n$ elements  $\leftrightarrow$
Sequences of $n-1$ bars (dividers) and $k$ stars   $\leftrightarrow$
Subsets of size $k$ taken from a set with $n + k-1$ elements.

To illustrate, with $k = 3$ and $n = 5$, the sequence of *'s and bars
$$| \ |\ * * \ | \ | *$$
on the one hand encodes the multiset $3^2, 5$ taken from $\{1, 2, \dots, 5\}$, and on the other hand encodes the subset $\{3,4,7\}$ taken from $\{1,2, \dots, 7\}$.  How do these encodings work?  For the multiset interpretation,  think of the $4 = n-1$ bars as marking off $n = 5$ bins, and the stars indicating $2$ objects in the $3$rd bin and $1$ object in the $5$th bin.  For the subset encoding, the $*$'s appearing in positions 3, 4 and 7, indicating the subset $\{3,4,7\}$ of $\{1,2, \dots, 7\}$.
A: The usual bijection takes the $n$-element set as $\{1,2\ldots,n\}$
and takes the multiset $\{a_1,a_2,\ldots, a_k\}$
with $a_1\le a_2\le\cdots\le a_k$ to $\{a_1,a_2+1,a_3+2,\ldots,a_k+k-1\}
\subseteq\{1,\ldots,n+k-1\}$.
A: Yes, you can sort your multiset with repetition in weakly increasing order for instance 
$$
[1,1,2,1,2,1,1,2]\to [1,1,1,1,1,2,2,2]
$$ 
then the multisets of size $k$ out of $n$ elements can be identified with the weakly increasing functions $\varphi : \{1,\cdots ,k\}\to \{1,\cdots ,n\}$. Now one transforms such a function to a strictly increasing one by 
$$
\hat{\varphi} : i\to \varphi(i)+i-1
$$
to the first value, you add nothing to the second, you add one to the third, you add two. One can prove (exercise) that this procedure sends bijectively weakly increasing functions $\varphi : \{1,\cdots ,k\}\to \{1,\cdots ,n\}$ to strictly increasing functions $\hat{\varphi} : \{1,\cdots ,k\}\to \{1,\cdots ,n+k-1\}$. The last ones are in bijection with their range which are exactly $k$-subsets of $\{1,\cdots ,n+k-1\}$.
