# Combinatorics: Things always included together

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?

-
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

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$$

-
awesome explanation, thanks Shaktal! –  Karan Jun 6 '12 at 9:24