Question

There are 10 girls in a class, all with different heights. They want to form a queue so that no girl stands directly between two girls shorter than her. How many ways are there to form the queue?

Answer 1

Solution:

Let $g_1,g_2,...,g_{10}$ be 10 girls and their heights are represented in the graph:

Given that no girl can stand between two shorter than her.

So, $g_{10}$ can stand only at position 1.

Ways of Position of $g_{10}$ is 1 and $g_9$ is 1.

Then $g_8$ is between $g_9, g_7$ or $g_{10},g_9$ , so it has 2 ways.

Similarly, ways for $g_7$ are 3, $g_6$ are 4, $g_5$ are 5, $g_4$ are 6, $g_3$ are 7, $g_2$ are 8 and $g_1$ are 9.

Thus, total possible ways = 1+1+2+3+4+5+6+78+9 = 46.