0
$\begingroup$

How many ways are there to pick r objects from n objects when repetitions are allowed and either both the first and the second objects appear exactly once or both do not appear?

So here is what I tried and I'm not sure if it's correct.

If we have n bins and each bin is an object, and we choose each object once we will have r-n, but since the first and second object appear once or not at all we have r-(n-2)+-2, at least I think. So using

$n+k-1 \choose k$

I think I can get

$n+(r-(n-2)\pm2)-1 \choose k$

Is this correct? I dont think it is, but I'm not sure how else to go about this.

$\endgroup$
1
$\begingroup$

We can simply separate the $2$ cases:

1 and 2 element don't appear

This means that we must choose $r$ elements with repetition, from $n-2$ elements:

$${{n-2+r-1}\choose{r-1}}={{n+r-3}\choose{r-1}}$$

1 and 2 element appear one time

This time we have to select $r-2$ elements with repetition, from $n-2$ elements:

$${{n-2+r-2-1}\choose{r-2-1}}={{n+r-5}\choose{r-3}}$$

Since the two cases are disjoint, the result is the sum of them:

$${{n+r-5}\choose{r-3}}+{{n+r-3}\choose{r-1}}$$

$\endgroup$
  • $\begingroup$ Sorry if the following is obvious, but I'm still a beginner. In the first case why is it (r-1) at the bottom and not just r? In the second case we are picking 1 and 2 once, and everything else can be picked with repetitions. I understand this, but I don't get how that translates to using r-2 and n-2, wouldn't n-2, make 1 and 2 not appear? $\endgroup$ – Brownie Apr 29 '19 at 21:25
  • $\begingroup$ @Brownie If you want to select $r$ objects from $n$ and the order doesn't matter and each object can be reapeted than the general formula is: ${{n+r-1}\choose{r-1}}$ or ${{n+r-1}\choose{n}}$ $\endgroup$ – Eureka Apr 29 '19 at 21:30
  • $\begingroup$ Oh alright thanks! I wasn't using the general formula correctly. One last thing, so in the second case, you do r-2 because that's how man you are doing with repetition, and then you do n-2, because objects 1 and 2 aren't used. If I'm understanding this correct, when do you factor in the fact that they appear once? $\endgroup$ – Brownie Apr 29 '19 at 21:33
  • 1
    $\begingroup$ @Brownie since we fixed them and they don't appear anymore in the formula ($n-2$) they appear only $1$ time. $\endgroup$ – Eureka Apr 29 '19 at 21:37

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.