# Total number of ways to arrange objects subject to constraint [duplicate]

This question already has an answer here:

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.

## marked as duplicate by saulspatz, Jendrik Stelzner, YuiTo Cheng, Parcly Taxel, N. F. Taussig combinatorics StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); May 26 at 11:00

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 1 Answer

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.