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.

Here's a little question that I'm trying to solve:

There are k students standing in a line. What's the number of permutation if John is standing left to Jack?

Here's my attempt: $$\sum_{i=2}^{k} \sum_{j=1}^{i-1}(k-2)!$$ Jack is in the i'th index and John is in the j'th index. The are k-2 people left.

I don't see a mistake here, but it feels to complicated. Also with combinatorics I never know if I'm right or not.

Any comments? Thanks!

share|improve this question
    
Fairly often you can tell whether a formula you arrived at is right by checking whether it gives correct answer in "small" cases where you can make an explicit list. –  André Nicolas Nov 3 '12 at 18:14

2 Answers 2

up vote 3 down vote accepted

HINT John can either be to the left or right to Jack and both are equally likely.

share|improve this answer
    
So I have $\frac{k!}{2}$? It the same as I did but simpler, isn't it? Note I've corrected my formula –  Yotam Nov 3 '12 at 18:22
    
@Yotam Yes. It is indeed $\dfrac{k!}2$. –  user17762 Nov 3 '12 at 18:24

Your corrected formula is right. It would be slightly simpler to express it as $$(k-2)! \sum_{i=2}^k \sum_{j=1}^{i-1} 1.$$ The last sum is just $i-1$, so our expression simplifies to $$(k-2)! \sum_{i=2}^k (i-1).$$ And the remaining sum is just $1+2+\cdots+(k-1)$. By the usual expression for the sum of an arithmetic progression, we have $1+2+\cdots+(k-1)=\dfrac{(k-1)(k)}{2}$.

The optimal solution is the one by Marvis. But a variant of your idea is pretty quick. There are $\binom{k}{2}$ ways to choose the two places that John and Jack will occupy. For every one of these choices, there is only one way to place John and Jack. And now there are $(k-2)!$ ways to place the others, for a total of $$\binom{k}{2}(k-2)!.$$

share|improve this answer

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.