1、問題的引出

前幾天接觸了這么一道題：
有2n個人排隊進電影院，票價是50美分。在這2n個人當中，其中n個人只有50美分，另外n個人有1美元（紙票子）。愚蠢的電影院開始賣票時1分錢也沒有。
問： 有多少種排隊方法 使得 每當一個擁有1美元買票時，電影院都有50美分找錢
注： 1美元=100美分，擁有1美元的人，擁有的是紙幣，沒法破成2個50美分。

一下子就懵了，這怎么算，后來接觸了卡特蘭數，得到了求解這道題的正確姿勢。

以下粘帖自公眾號： 數海拾貝：卡特蘭數 — 計數的映射方法的偉大勝利