7
$\begingroup$

enter image description here Basically it means choosing r things out of n, where order doesn't matter, and you are allowed to pick a thing more than once. For example, $\{1, 1, 2\}$ out of $\{1, 2, 3, 4\}$.

I managed to find another solution:

$$ {n \choose r} + (r-1){n \choose r-1} + (r-2){n \choose r-2} + \cdots + {n \choose 1} $$

I am having trouble proving that these two are equivalent.

$\endgroup$
4
  • $\begingroup$ Are you sure there is not an $r$ in front of the first term? $\endgroup$
    – Demosthene
    Commented Mar 1, 2015 at 12:06
  • $\begingroup$ I think there isn't. $\endgroup$
    – qed
    Commented Mar 1, 2015 at 12:07
  • 1
    $\begingroup$ The formula cannot be correct (with or without an initial factor $r$) because the extra terms added by increasing $r$ beyond $n$ are all $0$, but $\binom{n+r-1}{r-1}=\binom{n+r-1}n$ does keep increasing (polynomially in $r$) when $r$ increases beyond $n$. Did you try some small explicit values? $\endgroup$ Commented Mar 1, 2015 at 12:13
  • 1
    $\begingroup$ Yes, I did. For example, n = 4, r = 3. But I now realize I didn't take into consideration that multiple elements can be repeated at the same time, such as {1, 1, 2, 2} out of {1, 2, 3, 4, 5}. So, indeed, this is not a solution at all. $\endgroup$
    – qed
    Commented Mar 1, 2015 at 12:17

1 Answer 1

2
$\begingroup$

As has already been pointed out, unfortunately the two solutions are not equivalent.

However, if we use Pascal's Rule:- $${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$$ and apply this $r$ times to ${r+n-1 \choose r}$ the following solution can be shown to be equivalent:-

$${r-1 \choose r-1}{n \choose r} + {r-1 \choose r-2}{n \choose r-1} + {r-1 \choose r-3}{n \choose r-2} + \cdots + {r-1 \choose 0}{n \choose 1}$$ In other words the following relationship holds:- $${r+n-1 \choose r}=\sum_{k=1}^r{r-1 \choose k-1}{n \choose k}$$ Perhaps allowing the repetition of multiple elements at the same time results in the binomial terms ${r-1 \choose k-1}$ for $k\in \{1,2,..,r\}.$

$\endgroup$
3
  • $\begingroup$ I think maybe you want to replace the first n-1 with n in the identity you're using. $\endgroup$
    – user84413
    Commented Mar 1, 2015 at 22:57
  • $\begingroup$ @user84413: Well spotted - there was an error in the identity I stated. I have fixed this, but with $k$ instead of $k-1$. $\endgroup$ Commented Mar 2, 2015 at 8:39
  • $\begingroup$ Thanks - I guess my "correction" wasn't quite correct. $\endgroup$
    – user84413
    Commented Mar 2, 2015 at 16:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .