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.

  • $\begingroup$ Are you sure there is not an $r$ in front of the first term? $\endgroup$ – Demosthene Mar 1 '15 at 12:06
  • $\begingroup$ I think there isn't. $\endgroup$ – qed Mar 1 '15 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$ – Marc van Leeuwen Mar 1 '15 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 Mar 1 '15 at 12:17

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

  • $\begingroup$ I think maybe you want to replace the first n-1 with n in the identity you're using. $\endgroup$ – user84413 Mar 1 '15 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$ – Alijah Ahmed Mar 2 '15 at 8:39
  • $\begingroup$ Thanks - I guess my "correction" wasn't quite correct. $\endgroup$ – user84413 Mar 2 '15 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.