Martha and Four Friends

Date: 09/17/2001 at 07:30:12
From: vidya
Subject: Combinations permutations

Martha and four friends go to a movie. How many different ways can 
they sit together with Martha always between two friends?

My answer is 72, whereas the solutions gives the answer to the 
question as 24.

Thanking you in anticipation,
Vidya

Date: 09/17/2001 at 09:56:06
From: Doctor Ian
Subject: Re: Combinations permutations

Hi Vidya,

I get the same answer you do. The total number of ways that they can 
sit together is

  5! = 5 * 4 * 3 * 2 * 1

     = 120

The total number of ways that Martha can sit on the left end is

  4! = 24

The total number of ways that she can sit on the right end is

  4! = 24

So the total number of ways that she can sit in the middle must be

  120 - 24 - 24 = 72

I'm guessing that the person who said that 24 is the answer reasoned 
this way:

  There are 3*2*1 = 6 ways that Martha can sit with two of her
  friends on the inside. Then there are 4 ways to choose the
  person on the left; which leaves just 1 way to choose the person
  on the right; for a total of 4*3*2*1*1 = 24 ways for the 
  friends to sit together. 

However, this is incorrect, since it doesn't take into account the 
ways that the inner and outer groups can be chosen. But as I said, I'm 
just guessing.

But in problems like this - assuming they are small enough - there is 
always a way to settle a question definitively, which is to enumerate 
all the possibilities. To generate them systematically, I'm going to 
use the notation '-- ---', in which the left side represents choices 
that have been made, and the right side represents the unchosen 
elements. And let's say that Martha is 'a', and mark each permutation 
in which she doesn't appear on either end. 

  a  bcde -> ab cde -> abc de -> abcde
                                 abced
                       abd ce -> abdce
                                 abdec
                       abe cd -> abecd
                                 abedc

             ac bde -> acb de -> acbde
                                 acbed
                       acd be -> acdbe
                                 acdeb
                       ace bd -> acebd
                                 acedb

             ad bce -> adb ce -> adbce
                                 adbec
                       adc be -> adcbe
                                 adceb
                       ade bc -> adebc
                                 adecb

             ae bcd -> aeb cd -> aebcd
                                 aebdc
                       aec bd -> aecbd
                                 aecdb
                       aed bc -> aedbc
                                 aedcb

  b  acde -> ba cde -> bac de -> bacde *
                                 baced *
                       bad ce -> badce *
                                 badec *
                       bae cd -> baecd *
                                 baedc *

             bc ade -> bca de -> bcade *
                                 bcaed *
                       bcd ae -> bcdae *
                                 bcdea
                       bce ad -> bcead *
                                 bceda

             bd ace -> bda ce -> bdace *
                                 bdaec *
                       bdc ae -> bdcae *
                                 bdcea
                       bde ac -> bdeac *
                                 bdeca

             be acd -> bea cd -> beacd *
                                 beadc *
                       bec ad -> becad *
                                 becda 
                       bed ac -> bedac *
                                 bedca

  c  abde -> ca bde -> cab de -> cabde *
                                 cabed *
                       cad be -> cadbe *
                                 cadeb *
                       cae bd -> caebd *
                                 caedb *

             cb ade -> cba de -> cbade *
                                 cbaed *
                       cbd ae -> cbdae *
                                 cbdea 
                       cbe ad -> cbead *
                                 cbeda

             cd abe -> cda be -> cdabe *
                                 cdaeb *
                       cdb ae -> cdbae *
                                 cdbea
                       cde ab -> cdeab *
                                 cdeba

             ce abd -> cea bd -> ceabd *
                                 ceadb *
                       ceb ad -> cebad *
                                 cebda
                       ced ab -> cedab *
                                 cedba

  d  abce -> da bce -> dab ce -> dabce *
                                 dabec *
                       dac be -> dacbe *
                                 daceb *
                       dae bc -> daebc *
                                 daecb *

             db ace -> dba ce -> dbace *
                                 dbaec *
                       dbc ae -> dbcae *
                                 dbcea
                       dbe ac -> dbeac *
                                 dbeca

             dc abe -> dca be -> dcabe *
                                 dcaeb *
                       dcb ae -> dcbae *
                                 dcbea
                       dce ab -> dceab *
                                 decba

             de abc -> dea bc -> deabc *
                                 deacb *
                       deb ac -> debac *
                                 debca
                       dec ab -> decab *
                                 decba

  e  abcd -> ea bcd -> eab cd -> eabcd *
                                 eabdc *
                       eac bd -> eacbd *
                                 eacdb *
                       ead bc -> eadbc *
                                 eadcb *

             eb acd -> eba cd -> ebacd *
                                 ebadc *
                       ebc ad -> ebcad *
                                 ebcda
                       ebd ac -> ebdac *
                                 ebdca

             ec abd -> eca bd -> ecabd *
                                 ecadb *
                       ecb ad -> ecbad *
                                 ecbda
                       ecd ab -> ecdab *
                                 ecdba

             ed abc -> eda bc -> edabc *
                                 edacb *
                       edb ac -> edbac *
                                 edbca 
                       edc ab -> edcab *
                                 edcba

I count 72 different ways for them to sit together with Martha in the 
middle. 

Does this help?  

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/