1won't that be a bit too many?..lol
1. n boys B1,B2,...,Bn and n girls G1,G2,...,Gn line up.Find the number of arrangements in which Gi is ahead of Bi for all i=1,2,...,n.
-
UP 0 DOWN 0 1 2
2 Answers
1I think it can be solved through recurrence:
Suppose the number of ways of such arrangements of n boys and n girls is denoted by f(n)
Now to find out f(n+1) we have to add 1 boy and one girl in a selected arrangement out of a total of f(n) arrangements.
suppose the positions are denoted by a_{i} i=1,2,3...,2n
Now there are 2n+1 gaps including the gaps on two sides.
let B_{n+1} be
inserted in the i^{th} gap that is between a_{i-1} and a_{i}.
Number of choices left for G_{n+1} = (2n-i+1+1)=(2n-i+2)
So, total number of ways = \sum_{1}^{2n}{(2n-i+2)}+1
so, we get the recurrence :
f(n+1)=(2n^{2}+3n+1)f(n)
now, f(1)=1
multiplying and cancelling alternate terms we get the required solution!
There may be calculation mistakes but I hope the method is correct!
