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?
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.
Comments
Leave a comment