1
$\begingroup$

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!

  • 0
    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.2012-11-03

2 Answers 2

3

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

  • 0
    @Yotam Yes. It is indeed $\dfrac{k!}2$.2012-11-03
0

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