Counting Possible Arrangements for a Group Photo

Date: 10/21/2003 at 19:11:16
From: kimberly
Subject: story problem

Eight women of eight different heights are to pose for a photo in two 
rows of four.  Each woman in the second row must stand directly behind 
a shorter woman in the first row.  In addition, all of the women in 
each row must be arranged in order of increasing height from left to 
right.  Assuming that these restrictions are fully adhered to, in how 
many different ways can the women pose?

I understand the question, but I cannot figure out where to begin in 
order to construct an equation.  I have only figured out how to move 
the numbers around, and there must be a more efficient approach.

  5678
  1234

  4678
  1235

  2678
  1345

etc....

Date: 10/22/2003 at 08:09:29
From: Doctor Luis
Subject: Re: story problem

Hi Kimberly,

Interesting question.  I suppose you numbered the women 1 thru 8 in 
order of ascending height, where women 8 is tallest.  We know that 
only one person is tallest since all the heights are different.  It's 
important to know their heights are unique, otherwise we'd have to 
worry about permuting the women of equal height.

We know there's 8 possible places for the women.  Following your 
notation, we have these positions:

   Back row:  EFGH
  Front row:  ABCD

The requirements for this arrangement are A<B<C<D, E<F<G<H, and
A<E, B<F, C<G, D<H.

Well, let's start by positioning tall woman number 8.  She can't be in 
the front row or anyone behind her would be shorter.  So positions 
A,B,C,D are out.  Likewise, she can't be either E,F,G or someone to 
the right of her would be shorter.  So the only choice for woman 8 is 
position H.

The tallest woman only had one choice.  What about the shortest woman?    
Similar reasoning can convince you that woman 1 can only be at 
position A.

Because women 1 and 8 are fixed, we have a single configuration, which 
I'll call R1.

   Back row:  EFG8
  Front row:  1BCD

Women 2 thru 7 have yet to be positioned.  Inspired by our method so 
far, we start by positioning the shortest and tallest of the women 
that are left.

We start with the taller one, woman 7.  She can be placed either at D,
right in front of 8, or she can be placed at G.  Those are the only 
two choices for her, since the tallest person must be placed to the 
right of everyone else that's shorter.  If she's in the back row, she
must be at G, or there'd be no one taller to fill in between women 7 
and 8.  If she's in the front row, she must be at D, because she's the 
tallest person left after we've placed 8.

A similar argument holds for woman 2.  Her only two choices are B,E.

Two choices for 2 and two choices for 7 leaves us with 4 possible
configurations.

                S1      S2      S3      S4
   Back row:   2FG8    2F78    EFG8    EF78
  Front row:   1BC7    1BCD    12C7    12CD

So, our single configuration R1 branched out into four configurations
S1 thru S4.  Every time we branch out, we must add the number of
arrangements for each configuration.

Remember that the four women that have yet to be positioned are women 
3, 4, 5, and 6.  We always seek to position the tallest and shortest 
women first, hence women 3 and 6 will be positioned.  Once 3 and 6 are 
in place, each configuration could branch out into one or more
possible configurations.

And finally, now that only two women are left, 4 and 5, you can easily 
position them and count the number of configurations.

This is a systematic method you can use to come up with all the 
possible arrangements.  By picking two women at a time, the tallest 
and shortest, you'll end up with a tree that's four levels deep.  How 
many nodes, each representing a different configuration, would we have 
in this tree?

The first time we picked (1 and 8) there was no branching since the
choice was unique.  So there's one node at level one.

For the second pick, we showed that there are four branches coming out 
because there are two choices for woman 2, and two choices for woman 
7.  There's a total of four nodes at level two, one for each 
configuration S1 thru S4.

For the third pick, we'd expect less branching since we have less  
freedom because of the ordering conditions.  One of the women is
probably going to have no choice for where she stands (you can tell
by analyzing S1 thru S4), so we'd expect a branching factor of two
(i.e. the number of choices for only one woman).  So, for level three,
we expect about 8 nodes.

For the fourth pick, we have two people left to position.  If they had 
no choice whatsoever, we'd have a branch factor of one, or 8 nodes for 
level four.  If they had full freedom, the branch factor would be two, 
and we'd have 16 nodes at level four.  This means we'd expect 
somewhere between 8 and 16 nodes for level four of our tree.

But by level four all the women are standing.  This means that we 
expect the number of possible arrangements to be between 8 and 16. 
This is a small enough tree that we can draw it by hand. 

Here it is:


                             EFG8
                             1BCD
     _________________________|__________________________ 
     |             |                  |                  |
   2FG8          2F78               EFG8               EF78
   1BC7          1BCD               12C7               12CD
     |         ____|____         _____|____          _____|___
     |         |       |         |         |         |        |
   2F68      2678     2F78      EF68     3F68      EF78     E678
   13C7      13CD     13C6      1237     12C7      1236     123D
 ____|__       |    ___|___      |      ___|__       |     ___|__
 |      |      |    |      |     |      |     |      |     |     |
2468  2568   2678  2478  2578   4568  3468  3568   4578  4678  5678
1357  1347   1345  1356  1346   1237  1257  1247   1236  1235  1234


That should represent the total number of arrangements.  Look at each 
node, and convince yourself that the branches below a node represent 
all the possibilities for that node.  I don't think I missed any, but 
let me know if you can find any other configurations.

Let us know if you have any more questions.

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

Date: 10/22/2003 at 21:51:02
From: kimberly
Subject: Thank you (story problem)

Dr. Luis,

Thank you so very much for your help and wonderful explanation.  I am
currently studying for the GMAT and plan to take the exam sometime 
next year.  I have purchased several guides and have constructed a
strict study routine for the next several months.  This problem really 
got me stuck :) You'll probably hear from me again! 

Kind regards, 

Kimberly