3
$\begingroup$

Find the number of permutations of $n$ different things taken $r$ at a time such that all $m$ specified things should never come together.


1st attempt

No of ways of choosing $r-m$ things from $n-m$ different things is $\binom {n-m} {r-m}$.

Now, we want the no of ways in which $m$ specified things never come together in a permutation involving $r$ things and they are $\binom {r-m+1}{m}$.

So our answer is $$\binom {n-m} {r-m} \binom {r-m+1}{m} (r-m)!\space(m)!$$


2nd attempt

Total no of permutations of $r$ different things taken $r$ at a time OR No of arrangements of $r$ different things is $r!$

Now we will subtract the no of cases in which $m$ things are together and they are $\binom{n-m}{r-m}(r-m+1)!\space m!$. Similar Proof can be found here Proof of Number of: *permutations of ‘n’ things, taken ‘r’ at a time, when ‘m’ specified things always come together*

So our answer comes out to be $$r!-\binom{n-m}{r-m}(r-m+1)!m!$$

It is clear that both of the answers don't match.

Can someone please clarify the following two questions?

  • Which of the answer is correct and why?
  • In my old notes It is briefly mentioned that we can do Total- Together(as in Attempt $2$) in case of only two objects/things.Based on this reasoning answer from Attempt $2$ is incorrect. So I also want a clarification for the same.
$\endgroup$
3
  • $\begingroup$ I don't fully understand your question. You said "m specified things never come together". What do you mean by never come together? Do you mean all m things should not be together (ie. m-1 of those things can be together if one of m things is separated by any other thing between them) or do you mean no two of those m things should be together (here m can be greater than r, but if you meant the above you must have m<r otherwise all those m things can never be together in any case since r are taken at a time) $\endgroup$ Aug 1, 2021 at 17:51
  • $\begingroup$ @Aman kushwaha I meant all $m$ things shouldn't be together. $\endgroup$
    – User 1207
    Aug 1, 2021 at 18:00
  • $\begingroup$ Okay ..I got it. $\endgroup$ Aug 1, 2021 at 18:10

1 Answer 1

1
$\begingroup$

Assuming than $m<r$ $\textbf{Case 1: No two things of m specified things are together}$ (Taking aside those m specified things) We will first arrange $n-m$ things taking $r-m$ things at a time, there will be $^{n-m}C_{r-m} (r-m)!$ ways.

For each one of these arrangement we have $r-m+1$ spaces between any two things in which we would put those remaining m things in $^{r-m+1}C_m m!$ ways.

So there will be total ${^{n-m}C_{r-m}} (r-m)! {^{r-m+1}C_m} m!$ ways in which n different things are permuted taken r at a time such that no two of m specified things can come together.

$\textbf{Case 2: All the specified m things are not together}$

(Taking aside those m specified things) We will first arrange $n-m$ things taking $r-m$ things at a time, there will be $^{n-m}C_{r-m} (r-m)!$ ways.

For each one of these arrangement we have $r-m+1$ spaces between any two things in which we would put those remaining m things randomly. Taking first item of those m specified things, we can select any one out of those $r-m+1$ spaces for putting it in. Then, we will have $r-m+2$ spaces, so that the next one can be put in $r-m+2$ ways. Proceeding in this manner we'll have $r-m+m=r$ ways for the last one of those m specified things.So, total such arrangements will be $(r-m+1)(r-m+2)...(r-m+(m-2)(r-1)r$(internal arrangement between m specified things is also done). But we have also counted the arrangement such that all m are together ($^{r-m+1}C_1 m!$ ways)which we need to subtract. So, the total no. of ways will be $(r-m+1)(r-m+2)...(r-2)(r-1)r-(r-m+1)m!$

Hence, the number of permutations of n different things taken r at a time such that all m specified things should never come together is $$^{n-m}C_{r-m} (r-m)! [(r-m+1)(r-m+2)...(r-2)(r-1)r-(r-m+1)m!=^{n-m}C_{r-m}[r!-(r-m+1)!m! $$

Attempt 2:

$\textbf{Case 3:All m specified things are together}$

(Taking aside those m specified things) We will first arrange $n-m$ things taking $r-m$ things at a time, there will be $^{n-m}C_{r-m} (r-m)!$ ways.

For each one of these arrangement we have $r-m+1$ spaces between any two things in which we would put those remaining m things together as one unit (while arranging them amongst themselves in $m!$ ways) in $^{r-m+1}C_1 m!$ ways.

So there will be total ${^{n-m}C_{r-m}} (r-m)! (r-m+1) m!= {^{n-m}C_{r-m}} (r-m+1)! m!$ ways of arranging n different things taken r at a time such that all m specified things should always come together.

In attempt 2 I don't know why you are subtracting the "number of permutations of n different things taken r at a time such that all m specified things should always come together" from $r!$. If you are thinking of subtracting it from anything you should think of $^{n-m}C_{r-m} r!$.

But, in any case you should notice that "all m together case" and "no two things of m together case" are not complement of each other. However "all m together case" and "all m not together case( in which some of the m specified things can be together but not all)" are actually complement and when the number of possible ways of arrangement for these two cases are added you should get $^{n-m}C_{r-m} r!$.

So the answer from corrected attempt 2 is:

$^{n-m}C_{r-m} r!-{^{n-m}C_{r-m}} (r-m+1)! m!$ ways.

$\endgroup$
2
  • $\begingroup$ @User1207 sorry only the simplification in the last step was wrong(I've deleted it now). And we are doing separate arrangement of those specified m things in their own $m!$ ways when already placed in those spaces between $r-m$ things to ensure they never come other. If you do arrangement of all the r things together in the end, how come you say that those specified m things will not come together in any of the arrangements? $\endgroup$ Aug 1, 2021 at 18:27
  • $\begingroup$ I think I made a mistake(Now edited))by arranging $r$ things at a time not $(r-m)$ and $m$ separately but that also doesn't do much in the Question. $\endgroup$
    – User 1207
    Aug 1, 2021 at 18:27

You must log in to answer this question.

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