第二百九十八章 卡塔朗數(shù)（組合）

　　卡塔朗有一天去劇場(chǎng)排隊(duì)，看到售票處因?yàn)闆]有找零的錢而跟顧客發(fā)生了沖突。

　　很多顧客都抱怨為什么劇場(chǎng)售票處沒有足夠的零錢，而劇場(chǎng)售票處的人也發(fā)現(xiàn)大家都用大整錢。

　　卡塔朗在想，不見所有的人用整錢，只是沒有足夠零錢的人排隊(duì)排在前頭，導(dǎo)致零錢被找光而發(fā)生了斷供。

　　卡塔朗在想：“如果帶零錢的人全部在前面排隊(duì)，那么問題一定好解決?！?p>　　“不見得所有有零錢的人一定在前方排隊(duì)，而是有一部分人有零錢的人在前面即可，但是有零錢的人是多少個(gè)呢？”

　　卡塔朗在假設(shè)，售票窗口前有2n個(gè)人排隊(duì)買票，每張門票定價(jià)5角，每人限購(gòu)一張。這些人中，只帶一張5角人民幣的與只帶一張1元人民幣的各有n人。

　　開始售票時(shí)，售票窗口沒有角票可以找零。試問：大家都能順利買票，售票員始終沒有找不出零錢困擾的排隊(duì)方法共有多少種?

　　卡塔朗開始思考用0代表身邊帶5角錢的人，1代表帶1元錢的人，則本問題即可變成：有n個(gè)0和n個(gè)1，問有多少種排列方法，使排成的0、1序列里，任意前i(i可從1變到2n)個(gè)數(shù)字中，0的個(gè)數(shù)總不少于1的個(gè)數(shù)，此性質(zhì)稱為前束性質(zhì)。

　　卡塔朗開始畫圖，發(fā)現(xiàn)把0看作向右走一步，把1看作向上走一步，則很明顯，n個(gè)0和n個(gè)1所組成的序列將和圖中從原點(diǎn)(0，0)到點(diǎn)(n，n)的遞增路徑是一一對(duì)應(yīng)的。于是，我們只要計(jì)算路徑的條數(shù)就行了。

　　很快卡塔朗找到了一個(gè)公式計(jì)算排隊(duì)的方法，如果是有n個(gè)5角和n個(gè)1元的人的排隊(duì)，則有（2n）!/(n!(n+1)!)個(gè)辦法。

　　如果是有1個(gè)人排隊(duì)是1個(gè)辦法，2個(gè)人排隊(duì)則是1個(gè)辦法，3個(gè)人排隊(duì)是2個(gè)辦法。此后的4、5、6、7、8、9、10個(gè)人排隊(duì)分別有5，14，42，132，429，1430，4862種辦法。

　　卡塔朗數(shù)是一個(gè)組合數(shù)，一些組合計(jì)數(shù)問題可以歸結(jié)為解下列形式的遞歸關(guān)系：un=u1un-1+u2un-2+…+un-1u1，n≥2，且u1=1，它的解un稱為卡塔朗數(shù)。

　　一般認(rèn)為這種數(shù)是由比利時(shí)數(shù)學(xué)家卡塔朗在1838年首先提出的，但后來有人指出，實(shí)際上大數(shù)學(xué)家歐拉早在1758年就已認(rèn)識(shí)到它了。

　　我國(guó)內(nèi)蒙古師范大學(xué)羅見今副教授以大量的史料論證，所謂“卡塔朗數(shù)”的首創(chuàng)者其實(shí)并非歐洲人，而是我國(guó)清朝的蒙古族學(xué)者明安圖(1692～1763)。他的發(fā)現(xiàn)早于歐拉，比卡塔朗的發(fā)現(xiàn)，幾乎早了一百年。