0
$\begingroup$

I have the following problem :

How many ways are there to sit $n$ people to sit on bench with length $n$ assume that John must see Eric on his left.

I have the solution for this problem but I don't completely understand the answer :

$$\binom n2*1*(n-2)!$$

I understand the part of $(n-2)!$, But I don't know how $\binom n2$ implies that John sees Eric on his left? from $\binom n2$ we get all the possibilities for Eric and John to sit on the bench but how do we know its a valid possibility meaning that John sees John to his left.

Note : I do know the solution of $\frac{n!}{2}$ I'd like to know this solution as well.

Thank you, very much!

$\endgroup$
  • 1
    $\begingroup$ Once we choose the two seats to put reserved signs on, which of our two people sits where is determined. $\endgroup$ – André Nicolas Apr 12 '16 at 18:10
  • $\begingroup$ @AndréNicolas as far as I understand $\binom n2$ give us the amount of possibilities to sit two people in bench of $n$, but we only need the possibilities John sees Eric to his left, I think we get more possibilities then we should since the formula also count the possibilities that John sees Eric to his $right$. $\endgroup$ – John C Apr 12 '16 at 18:24
  • 1
    $\begingroup$ The number $\binom{n}{2}$ counts the number of ways to choose the seats that will be occupied by John and/or Eric. Once we have chosen this pair of seats, where John and Eric actually sit is determined by the condition that John sees Eric somewhere to his left. $\endgroup$ – André Nicolas Apr 12 '16 at 18:28
  • $\begingroup$ I see it now!, Thanks:) $\endgroup$ – John C Apr 12 '16 at 18:47
  • $\begingroup$ You are welcome. $\endgroup$ – André Nicolas Apr 12 '16 at 18:48
5
$\begingroup$

We can regard the bench as a sequence of chairs. Now, we first fix which two seats John and Eric would sit. This is the question of which two seats they would sit and how many of them exist. This is basically equivalent to choosing two of the seats among $n$ seats; hence, $n\choose{2}$. Now, given that we choose how they sit, there is only one way to allocate John and Eric in these seats given the requirement that one should sit to the left of the other, hence the $1$. Finally, we would need to seat the rest $(n-2)$ people to the remaining $(n-2)$ seats, which would happen in $(n-2)!$ different ways. Therefore, the total number of ways would be as you remarked $$ {n\choose 2 }\times 1\times (n-2)! $$

$\endgroup$
  • $\begingroup$ I don't understand how $\binom n2$ implies John sees Eric to his left I think we get more possibilities then we should using this formula, because we don't consider the order between them, can you please explain? $\endgroup$ – John C Apr 12 '16 at 18:28
  • $\begingroup$ It does not, the part that it is implied is when I multiply this by $1$. Normally, there are $2$ ways of seating Eric and John in these two seats, if we get rid of the requirement that Eric is to the left of John. However, since we want them to sit in a particular order, we should discount for that, which gives rise to the multiplication with $1$ rather than $2$ because there is only one way after choosing the seats that Eric is to the left of John. Note that if instead we didn't care about this and proceeded without the restriction, from the above calculations you would reach $n!$ asexpected. $\endgroup$ – Mollie Apr 12 '16 at 18:32
0
$\begingroup$

There are n-1 places to put John (He can't be in the last seat on the left since Eric must be on the left). If he is in the next to last place on the left, Eric can only be seated immediately next to him. There is 1] way to do that. If John is seated in the third seat from the left, there are 2 places Eric could be seated, if his is seated on the fourth seat form the left, there are 3 places Eric could be seated, etc. until, if John is seated in the last place on the right, there are n-1 places Eric could be seated. In other words, there are 1+ 2+ 3+ ...+ (n- 2)+ (n-1) possible ways to seat John and Eric so that Eric is always to the left of John. If you don't know the (fairly famous) formula for that you can do it this way: Suppose S= 1+ 2+ 3+ ...+ (n-1). Then also S= (n-1)+ (n- 2)+ ...+ 3+ 2+ 1. Now, notice that 1+ (n-1)= n, 2+ (n-2)= n, ..., until (n- 2)+ 2= n, (n-1)+ 1= n. So if we add those two formulas for S, adding on the right in pairs vertically, 2S= n+ n+ ...+ n+ n where we are adding n n-1 times. That is, 2S= n(n-1) so S= n(n-1)/2.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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