Let $m,n,r \in \mathbb{N}$. Find the number of $r$-element multi-subsets of the multi-set $$M= \{ a_{1},a_{2},...,a_{n},m.b \} $$
when $r \leq m,r\leq n$.
Below is the given answer.
$\sum_{i=0}^{r} \binom{n}{i}$
My thoughts:
1) $M$ has (n+1) distinct elements.
2) Use this forumula : $H_{r}^{n} = \binom{r+n-1}{r}$
I'm not sure how to get the answers and why there would be 3 answers for the 3 different conditions.
EDIT:
1) Still haven't received any response. Anyone?
Let $S=\{a_1,\cdots,a_n\}$ and consider the cases 1) $r\le n, r\le m,\;\;$ 2) $n\le r\le m,\;\;$ 3) $m\le r\le n$.
In each case, we can choose $i$ elements from $S$ and $r-i$ $b's$, where $i\le r$ and $i\le n$ and $r-i\le m$.
1) In case 1, $0\le i\le r$ and there are $\binom{n}{i}$ ways to choose $i$ elements from S, so
$\;\;\;$there are $\displaystyle\sum_{i=0}^{r}\binom{n}{i}$ multisets.
2) In case 2, $0\le i\le n$ so there are $\displaystyle\sum_{i=0}^{n}\binom{n}{i}=2^n$ multisets.
$\;\;\;$ (In this case, we can choose any subset of $S$, and $S$ has $2^n$ subsets.)
3) In case 3, $i\le r$ and $r-i\le m\implies r-m\le i\le r$,
$\;\;\;$so there are $\displaystyle\sum_{i=r-m}^{r}\binom{n}{i}$ multisets.