Bijection between sets and multisets

Question

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?

Answer 1

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\}$.

Answer 2

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\}$.

Answer 3

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\}$.