0

Suppose that you are ticket collector in Cinema office. It cost 50 dollars to watch a movie. There are 20 people in line. 10 people in that line have exactly 100 dollar bills and 10 people have exactly 50 dollar bill. Now, since it is early in morning,you do not have any change. So,the people should be arranged in such a way that the line goes on without any interruption. What are total number of ways to arrange people in such a way that line proceeds smoothly?

One valid combination:

50,100,50,100,50,100,50,100,50,100,50,100,50,100,50,100,50,100,50,100

An invalid one:

100,50,....,50

My take: I tried to do this problem for small number like 3,4,5. However,I see no pattern to generalize the result to more people.

Abhi7731756
  • 129

1 Answers1

3

Interpret a person with a \$50 note as an opening bracket (you gain a \$50 note for later use) and a person with a \$100 note as a closing bracket (you use up a \$50 note in giving change to this person). Then, since there are an equal number of persons with \$50 and \$100 notes, the valid arrangements are in bijection with the number of ways to arrange ten pairs of brackets, correctly matched, so there are $C_{10}=16796$ valid arrangements, where $C_n$ denotes the Catalan numbers.

Parcly Taxel
  • 103,344