將3組小括弧、2組方括弧、1組角括弧排成一列,各種括弧之間沒有先後使用的規定,但是每一組括弧的左括弧必須排在右括弧的左邊,而且每一組括弧中間如果有其他括弧,則這些括弧必須是完整的一組括弧;舉例來說:(<>)[()[]]()是一種合格的排列法,而<)(>[([])]()與(<)>[([])]()都是不合格的排列法。
請問以上的6組括弧,共有幾種合格的排列法? 答:
種。
[解答]
我們知道括號的問題跟Catalan Number有關,
但此題的括號數跟一般的括號不太一樣,
先所有的都看成小括號,
若
1組:(),1種
2組:()(), (()),2種
3組:()()(), (())(), ()(()), (()()), ((())),5種
4組:()()()(),(()())(), ()(()()), (((()))), (()()()), ((()())), ((()))(), ()((())), (())(()), (())()(), ()()(()), ()(())(), ((())()), (()(())),14種
可以視為Dick Path, 左括號就是往上走,右括號就往下走,不能低於水平線…
所以6組括號
C6=132,再乘
6!3!2!1!=60,所以是
132
60=7920。
我一開始列錯了,還以為答案錯了…