# Proof for bijection between the set of k-multisets & the set of k-subsets.

In the u.g. book on combinatorics, by David Mazur, there is question #13 on proof in sec. 1.3.
Note: The book, use $$[n]$$ to denote the set of the first $$n$$ positive integers.

This exercise outlines a bijective proof of the formula $$\left(\!\!\!\binom{n}{k}\!\!\!\right) = \binom{k+n-1}{k}$$ from Section 1.1. Let $$A$$ be the set of $$k$$-multisets taken from $$[n]$$ and let $$B$$ be the set of $$k$$-subsets of $$[k+n-1]$$. Assume that the $$k$$-multiset $$\{a_1,a_2,\ldots,a_k\}$$ is written in non-decreasing order: $$a_1 \le a_2 \le\ldots\le a_k$$. Define $$f: A \to B$$ by $$f({a_1, a_2, ..., a_k}) = {a_1, a_2+1, a_3+2,\ldots, a_k+k-1}.$$ This function, and proof, is originally due to Euler.
(a) Prove that the outputs of $$f$$ are indeed $$k$$-subsets of $$[k + n - 1]$$. This requires proof since it is not immediately clear from the definition of $$f$$.
(b) Prove that $$f$$ is a bijection.

My approach is given below for part (a) & request vetting & help (as in the final para.):
Out of $$n$$ unique elements, $$k$$ are chosen; with their size (how many of each type are chosen) being in non-decreasing order.
(a) For the function $$f$$, the elements are non-decreasing (weakly ordered) in domain (set $$A$$). However in range, the elements are in increasing order by addition of $$j-1$$ for $$j$$-th element. In set $$B$$, the $$j$$-th element in $$f({a_1, a_2, ..., a_k})$$ is $$a_j +j -1$$.
The lower limit of values in set $$B$$ (i.e. the smallest value chosen as number of elements for any of the $$k$$ elements; let, in ordering be $$a_1$$) is $$\ge 1$$.
While the upper limit is derived below:
Since $$\forall j \in [k]$$:
(i) $$(1\le a_1 \le a_j)$$ & $$(0\le j-1) \implies 1\le a_j +j - 1$$.
(ii) $$(a_j \le a_k \le n)$$ & $$(j-1 \le k-1)$$

From (i) & (ii), get:
$$\forall j \in [k],\,\, 1\le a_j +j - 1 \le k +n -1$$, with $$(k+n-1)$$ being the upper limit.

So, all the different elements of $$f({a_1, a_2, ..., a_k})$$ belong to $$[n+k-1]$$, i.e. the set of first $$n+k-1$$ positive integers.

Next, need show that all the mappings are unique, as need show that the outputs of $$f$$ are unique. This can be shown by proving that the elements in range are in increasing order, i.e. none of the range elements is repeated.
This can be easily shown by taking the two components of the mapping $$f(j)=a_j+j-1$$, i.e. $$a_j$$ & $$j-1$$; out of which $$a_j$$ can repeat, but the second part is unique.

However, how to show that it is not possible for the quantity $$a_j+j-1$$ to not repeat is not clear. Given below is an example to elaborate the confusing part:
Let $$n=6, k=4, a_1 = 1, a_2 = 2, a_3 =3, a_4=3$$ by which I mean that the elements of domain that are chosen are four with their corresponding no. of elements being $$1,2,3,3$$. I want to know how it is possible to ensure with the mapping $$f$$ yielding unique values in range. Say, $$i=2, j=4, a_i = 2, a_j = 3, i-1 = 1, j-1 = 3$$, and it is clear that $$a_i+i-1 = 3, a_j+j-1= 6$$; but how to theoretically prove the uniqueness of $$f(a_k)$$ for all $$k$$ is not known.

• The sequence $(a_j+j-1)$ is strictly increasing. – Lord Shark the Unknown Jan 26 at 22:25
• @LordSharktheUnknown But how it is not possible that if $i != j$, then the quantity $a_j+j-1$ never is repeated. I mean that $a_j=l, a_i=m$, with $i\le j$, hence $l\ge m$, but how to ensure that the value $a_j+j-1$ or $a_i +i-1$ is not taken up for any other $a_k+k-1$ for any $k$ in $[n]$. – jiten Jan 26 at 22:38
• What has $i!$ to do with anything? If $k>j$ then $a_k+k-1>a_j+j-1$, and if $k<j$ then $a_k+k-1<a_j+j-1$. That is what strictly increasing means. – Lord Shark the Unknown Jan 26 at 22:41

For part $$(a)$$, for $$i < j$$, we have $$a_i \le a_j$$ and $$i-1 < j-1$$,

Hence $$a_i +i-1 < a_j + j-1.$$

In general, if $$a \le b$$ and $$c < d$$, then we have $$a+c < b+d$$.

To see this note that

\begin{align} b+d - (a+c) &= (d-c)+(b-a) \end{align}

$$d-c$$ is positive and $$b-a$$ is nonnegative. Hence the sum is positive.

• Kindlly give the notation to be used for the statement: "If $f$ function then $f^{-1}$ function iff $f$ function injective (one-to-one).", as given at : math.stackexchange.com/q/1764370/424260. I am confused as it is not clear as to which statement 'iff' associates with. For me, it is: "If $f$ function then ($f^{-1}$ function iff $f$ function injective (one-to-one))." But, unable to give notn. for that as : using the symbols : $\cup, \cap, \implies$. – jiten Jan 31 at 0:32
• your interpretation is correct. try to read the solutions? – Siong Thye Goh Jan 31 at 1:03
• I am not in question per se, but the notation used to express it. Before forming notation, need interpretation, which (you say that) mine is correct. As per it, meaning is : "If $f$ function then ($f^{−1}$ function iff $f$ function injective (one-to-one))." But, question is taken from same text as of this question (Ex. Q.7 , sec. 1.3). Book soln. considers two parts: (a) if part ($\implies$): Assume $f^{-1}$ is a fn.,need prove $f$ is one-to-one $\dots$; (b) only if part : Assume that $f$ is one-to-one. To prove that $f^{-1}$ is a fn., let $b$ be any element in domain of $f^{-1}$$\dots$ – jiten Jan 31 at 1:23
• i have no idea what you are asking about. – Siong Thye Goh Jan 31 at 1:35
• Request to join room : chat.stackexchange.com/rooms/89042/…. – jiten Jan 31 at 1:38