Associated Topics || Dr. Math Home || Search Dr. Math

### 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,

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
```
Associated Topics:
High School Discrete Mathematics

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search