Catalan數字

若將一正n邊形分割成n-2個三角形,有幾種分法? (Euler多邊形分割問題)
tex2html_wrap12285
參考資料: D顤rie, H. Problem 7 in 100 Great Problems of Elementary Mathematics: Their History and Solutions. New York: Dover, pp. 21-27, 1965.
Honsberger, R. Mathematical Gems I. Washington, DC: Math. Assoc. Amer., pp. 130-134, 1973.
Catalan數字
0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
11 58786
12 208012
13 742900
14 2674440
15 9694845
參考資料: Martin Gardner, Time Travel and Other Mathematical Bewilderments, pp. 254-255.

以二項係數來表示: Cn= Binomial[2 n, n]/(n + 1)
displaymath11253








最簡單的遞迴關係: Cn=(4n-6)Cn-1/n.

Cn的其他形式
displaymath12261
Johann Andreas von Segner 遞迴關係:
1 1 2 5 14
14 5 2 1 1
14 5 4 5 14 42

奇數的Catalan數字只出現於標號為2k -1處.

小於215-1的Catalan數字當中只有C2=2及C3=5為質數.

Catalan 問題(1838):固定n個符號依序排列,我們要差入n-1對括號使得每
一對括號恰好夾著兩項「式子」.這兩項「式子」可以是相鄰的兩個
符號,相鄰的兩個括號組或是相鄰的符號及括號組.試問:有多少種方法?
(1 (2 3))   ((1 2) 3)

(1 (2 (3 4)))   (1 ((2 3) 4))
((1 2) (3 4))   ((1 (2 3)) 4)    (((1 2) 3) 4)

(1 (2 (3 (4 5))))   (1 (2 ((3 4) 5)))
(1 ((2 3) (4 5)))   (1 ((2 (3 4)) 5))
(1 (((2 3) 4) 5))   ((1 2) (3 (4 5)))
((1 2) ((3 4) 5))   ((1 (2 3)) (4 5))
((1 (2 (3 4))) 5)   ((1 ((2 3) 4)) 5)
(((1 2) 3) (4 5))   (((1 2) (3 4)) 5)
(((1 (2 3)) 4) 5)   ((((1 2) 3) 4) 5)

(1 (2 (3 (4 (5 6)))))   (1 (2 (3 ((4 5) 6))))
(1 (2 ((3 4) (5 6))))   (1 (2 ((3 (4 5)) 6)))
(1 (2 (((3 4) 5) 6)))   (1 ((2 3) (4 (5 6))))
(1 ((2 3) ((4 5) 6)))   (1 ((2 (3 4)) (5 6)))
(1 ((2 (3 (4 5))) 6))   (1 ((2 ((3 4) 5)) 6))
(1 (((2 3) 4) (5 6)))   (1 (((2 3) (4 5)) 6))
(1 (((2 (3 4)) 5) 6))   (1 ((((2 3) 4) 5) 6))
((1 2) (3 (4 (5 6))))   ((1 2) (3 ((4 5) 6)))
((1 2) ((3 4) (5 6)))   ((1 2) ((3 (4 5)) 6))
((1 2) (((3 4) 5) 6))   ((1 (2 3)) (4 (5 6)))
((1 (2 3)) ((4 5) 6))   ((1 (2 (3 4))) (5 6))
((1 (2 (3 (4 5)))) 6)   ((1 (2 ((3 4) 5))) 6)
((1 ((2 3) 4)) (5 6))   ((1 ((2 3) (4 5))) 6)
((1 ((2 (3 4)) 5)) 6)   ((1 (((2 3) 4) 5)) 6)
(((1 2) 3) (4 (5 6)))   (((1 2) 3) ((4 5) 6))
(((1 2) (3 4)) (5 6))   (((1 2) (3 (4 5))) 6)
(((1 2) ((3 4) 5)) 6)   (((1 (2 3)) 4) (5 6))
(((1 (2 3)) (4 5)) 6)   (((1 (2 (3 4))) 5) 6)
(((1 ((2 3) 4)) 5) 6)   ((((1 2) 3) 4) (5 6))
((((1 2) 3) (4 5)) 6)   ((((1 2) (3 4)) 5) 6)
((((1 (2 3)) 4) 5) 6)   (((((1 2) 3) 4) 5) 6)
Euler多邊形分割問題與Catalan問題之一一對應:

Arthur Cayley問題:三價有根樹形之個數.
[ again, not much without pictures -- sorry ]







Cayley問題與Euler多邊形分割問題與Catalan問題之一一對應:










小蟲產生樹形之二進數

兩個候選人各得n票,問有幾種開票次序使得A永遠不落後於B?

如何將2n個高矮都不一樣的學生分成兩排,使得每一排n人由左至右同時
每一行的兩人前後都依照高矮次序來排列?

2n個人排隊買票,其中n人持有100元鈔票而其他n人持有50元鈔票。假如
售票員沒有預備零錢,而每張票賣50元。問有多少種排隊次序使得不需
等待找錢?

圓圈上設有2n點,有多少種方法畫n條兩兩不相交的弦使得所有的2n點
都位在這些弦的端點?
[ Again, a picture speaks a thousand etc. ]



求以下方程式非負整數解a0, a1, a2,...,a2n+1的個數:
a0= a2n+1=0, |ai,- ai+1|=1, i=1,2,...,2n.
求滿足
f:{1,2,...,n} -> {1,2,...n},
f(x) le x, 1 le x le n
f(x)lef(y), 1lexleylen
之函數的個數.

求滿足下方程式之解x0,x1, x2,...,x2n的個數:
xi=1或-1,
x0+x1+ x2+...+xk>0, k=0,1,2,...2n
x0+x1+ x2+...+x2n=1.
設Tn為所有的n x n上三角矩陣.證明Tn中有Cn+1個理想. (Shapiro, Amer. Math. Monthly (1975) pp. 634-637.)