如題 

感謝!

如題 

感謝!

一、這個問題等價於下述問題：

這裡有 n 種色球，每種色球的個數分別是 P₁,P₂,P₃,...,P_n，共有 N = P_1 + P_{2 +} P_{3 +} ... + P_{n 顆球}

將這 N 顆球由左至右排列，位置最左為 1，最右為 N，求滿足下列條件的排列數:

1. 對於任意位置 k ， 1 <= k <= N，在區間 [1, k] 中，第 i + 1 種色球的個數必定不超過第 i 種色球的個數。

二、以輸入範例的 Case 3: 來說，n = 2, P₁=4, P₂=2，答案 9。

即求 aaaabb 滿足第一點中條件的排列方法數，共有下列 9 個：

1. aaaabb

2. aaabab

3. aaabba

4. aabaab

5. aababa

6. aabbaa

7. abaaab

8. abaaba

9. ababaa

三、當 n = 2，m = P_1 = P₂ 時，相當於解以下經典的問題：

1. 在 m x m 的網格中，從最左下角到最右上角，每次只能往上或往右走一步，求路徑不越過對角線的走法數。

    從這個問題可以比較直觀看出原題目遞迴關係式的由來。

2. 求 m 組括號合法的組合數。

四、keyword：

Hook length formula(鉤長公式)

Catalan number(卡塔蘭數)

Young tableau(楊表)

一路領先問題

P.S. ZJ 此題目前測資是錯誤的，修正前請不要在這解此題，有興趣的可以去 UVa 解 11915 - Recurrence。