# Counting number of permutation in which John is left to Jack

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.

-
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

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)!.$$