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

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.
• 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) Aug 1, 2021 at 17:51
• @Aman kushwaha I meant all $m$ things shouldn't be together. Aug 1, 2021 at 18:00
• Okay ..I got it. Aug 1, 2021 at 18:10

Assuming than $$m $$\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.

• @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? Aug 1, 2021 at 18:27
• 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. Aug 1, 2021 at 18:27