如何求解這道卡特蘭數的擴展問題?

01-06

首先，我們來看一個最簡單的問題：

我在學校門口賣奶茶，奶茶一元一杯。今天下午開門的時候，我發現找零的錢忘帶了。
這時候來了 2n 個人，其中 n 個人身上只有一張一元錢，另外 n 個人身上只有一張兩元錢。我就讓他們排成一隊，然後用這 n 個人的一元錢來找給付兩元的人。當然，排隊的時候得保證每次來一個付兩元的人的時候都有的找。

假設所有拿一元的人和拿兩元的人都沒有分別，我現在想知道，他們有多少種排隊方式？

這個問題的答案大家都知道，是 Cat[n]，即第 n 個卡特蘭數（Catalan number）。不過我現在的問題是如下的升級問題。

升級1：條件同上，但這時候來的人數為 3n ，其中 n 個人只有一張一元錢，n 個只有一張兩元錢， n 個只有一張三元錢（假設題設的每種面值的鈔票均存在）。我仍然讓他們排成一隊，只要有付兩元的就用一元找，付三元的就用兩元找。同樣得保證每當需要找錢時有對應的錢可以找。求他們有多少種排隊方式？

以及最終問題

升級2：條件同上，但這時候來的人數為 mn，其中擁有面值為一元至 m 元的人均有 n 個。每當支付 k （ $1<kleq m$ ）元時用 k-1 面值的鈔票去找零。求合法排隊方式數。

你的這個問題已經有確定的答案,叫做 Hook length formula.

hook 長度公式對一般形狀的 young 表都可以應用,在你這個問題的情形, 是一個 3 x n 的矩形(或者 m x n 的矩形).

可以這樣來理解: 你的問題等價於說, 在數字 1,2,3 各出現 n 次的, 長為 3n 的序列中, 有多少個滿足條件: 對任何 k, 該序列的前 k 個數字中, 數字1出現的次數大於等於數字2出現的次數大於等於數字3出現的次數.

而這個又可以進一步轉換為一個標準的 young 表,比如:

第 1 個人用的是1元紙幣,就把數字1填在 3xn 表格的第一行第一個方格;

第 2 個人用的是2元紙幣,就把數字2填在 3xn 表格的第二行第一個方格;

第三個人用的是1元紙幣,就把數字3填在表格的第一行第二個方格;

...

以此類推,

第 k 個人用的是 i 元紙幣,就把數字 k 填在第 i 行的左起第一個空著的方格中.

如果你的序列滿足所述找零要求,則最終你得到的是一個填有數字 1~3n, 每一行從左到右遞增, 每一列從上到下遞增的 3xn 表格.這是因為如果填表過程中某個時刻,某個方格填入的元素(設這個填入的元素是 k) 比它下面方格已經填好的元素大的話,說明在第 k 個顧客到來前,下面行對應的面值大的鈔票已經出現過更多次了.

反之對每一個這樣的表格你都可以還原出對應的顧客的序列.

所以對一般的 m 個鈔票,答案是(未化簡):