Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Find the number of permutations of $n$ different things taken $r$ at a time so that two particular things are always included and are together?

Including two things initially, i have $(n-2)$ things from which I can choose $(r-2)$ things. Hence $\,^{(n-2)}C_{(r-2)}$ denote the combinations which can be arranged in $(r-2)!$

The two things can be interchanged in 2! ways within themselves.

Furthermore, when $r$ things are selected, I have $r+1$ ways where I can insert two things which have to remain together.

So I get $\,^{(n-2)}C_{(r-2)} \cdot (r-2)! \cdot 2! \cdot (r+1)$

Am I doing the right thing?

share|improve this question
    
You don't have $r$ things into which to put the two particular ones, you only have $r-2$ things. That gives you $r-3$ spaces in between the $r-2$ other things, plus the space at the beginning and end, for a total of $r-1$ locations where you can insert the two things that have to be together. –  Arturo Magidin Jun 5 '12 at 18:59
    
A slightly different way. Tie together the two people who must be together. Then we have $r-1$ "people" who can be permuted in $(r-1)!$ ways. Untie them, they can permute themselves in $2!$ ways. So get $\binom{n-2}{r-2}(r-1)!2!$. –  André Nicolas Jun 5 '12 at 19:15
    
Elegant solution Andre, thanks a lot :) –  Karan Jun 6 '12 at 9:25
add comment

1 Answer

up vote 3 down vote accepted

You have started off in the correct way, that is, recognizing that you now have an increased restriction upon the number of items you need to choose and the number of items to chose from.

You now need to permute $(r-2)$ things from $(n-2)$ things as you identified, so we have $\,^{n-2}P_{r-2}$ ways of doing this. However, we have to consider two more factors, firstly, the fact that we can arrange the two items that must be next to each other in $2!=2$ ways (as you already stated), and secondly that we can put this pair of items in any of the $(r-2+1)=(r-1)$ places in the set.

Therefore the number of ways of arranging the items as described in your problem can be found by:

$$\,^{n-2}P_{r-2} \cdot 2! \cdot (r-1)$$

N.B: $$\,^{n}P_{r}\equiv {(n)}_{r}\equiv \frac{n!}{(n-r)!}, \forall r\le n$$ And: $$\,^{n}P_{r}\equiv0, \forall r \gt n$$

share|improve this answer
    
awesome explanation, thanks Shaktal! –  Karan Jun 6 '12 at 9:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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