1,Catalan數(shù)

　　飯后，姐妹洗碗，妹妹把姐姐洗過的碗一個一個放進碗櫥摞成一摞。共有n個兩兩相異的碗，洗前也摞成一摞，也許因為妹妹貪玩，碗拿進櫥子不及時，姐姐就把洗過的碗摞在傍邊：

　　-

　　----

　　——--

　　--——

　�。�1）待洗（2）待摞（3）已摞

　　問最后小妹摞起的碗摞可能有幾種方式？

　　這個題目有個同解題是這樣的：

　　一隊不同的汽車行進在大街上，它們可以在任何時刻拐進一個死胡同里去加油，然后再出來加入隊伍。問你最后出城時汽車隊列有多少種可能形式？

　　呵呵，大家想想，有意思呢！

　　[簡短分析]

　　這是個有趣的組合問題。組合數(shù)學(xué)是離散數(shù)學(xué)的一部分，研究的是組合計數(shù)問題。圖論原來也是組合數(shù)學(xué)的一部分，后來才分家的：）。組合計數(shù)的一個指導(dǎo)性技巧是，如果對于一個過程的計數(shù)不好研究，就可以找一個和它有一一對應(yīng)的過程，而且該過程相對很好研究，這不是很美嗎？

　　你看看，如果碗有n個，姐姐每方下一個，就畫一個“（”，妹妹如果摞一個，就畫一個“）”，如果妹妹不貪玩，剛放下就能放好，串就是“（）（）（）……（）”，對吧？現(xiàn)在你來考慮一下，下次我說答案：）。

　　汽車車隊也是如此，車進了胡同就畫“（”，出來時再畫“）”，而沒有進胡同的就是“（）”，呵呵，所以同解呢。

　　離散的問題，技巧性很大，初看問題的解沒有規(guī)律，仿佛量體裁衣般的，但也有指導(dǎo)性的思路對吧？

　　2，拉姆賽問題

　　樸素的方式敘述：

　　r（p，q）是任意給的人群中必有p人相識或必有q人彼此不相識的人群人數(shù)之最小值。例如，r（3，3）=6，就是說，任意個的人群，最少6個人，一定可滿足其中3個人相識，或3個人互相不認識。r（p，q）就稱為拉姆賽數(shù)。

　　圖論的方式敘述：

　　Anyp，qinN,把一個完全圖G用紅與藍兩色進行邊涂色，每條邊一種顏色，其結(jié)果或者有一個紅色p邊形，連同其全部對角線皆為紅色，或者有一個藍色q邊形，連同其全部對角線皆為藍色，G最小的頂點數(shù)，能保證出現(xiàn)上述結(jié)果，就是拉姆賽數(shù)r（p，q）。

　　經(jīng)過幾代人的努力，加上計算機的幫忙，現(xiàn)在人類求的9個非平凡的拉姆賽數(shù)：

　　r（3，3）=6，r（3，4）=9，r（3，5）=14

　　r（3，6）=18，r（3，7）=23，r（3，8）=28

　　r（3，9）=36，r（4，4）=18，r（4，5）=25

　　呵呵，你來試試，你能給出哪些拉姆賽數(shù)的推理過程？

　　[背景趣聞]

　　關(guān)于求拉姆賽數(shù)的艱巨性，著名匈牙利數(shù)學(xué)家厄爾多斯曾用下面的話比喻：

　　某年某月某日，一伙外星強盜入侵地球，威脅道，若不能一年內(nèi)求出r（5，5），他們將滅絕人類！面對如此生死關(guān)頭，人類應(yīng)當(dāng)召集全球所有的數(shù)學(xué)家和計算機專家，夜以繼日的計算r（5，5），以求人類免于滅頂之災(zāi)；如果外星人要我們求得r（6，6），我們就別無選擇了，干脆直接開戰(zhàn)，放手一搏：）。

　　3，夢中情人

　　約翰的夢中情人長著金黃色的頭發(fā)，藍藍的眼睛，纖細的身子，高高的個子。他認識阿

　　黛爾，貝蒂，卡洛爾和多麗絲四位小姐，其中一位是約翰的夢中情人。（1）只有三位小

　　姐是藍眼睛和細身材。（2）只有兩位是黃頭發(fā)和高個子（3）只有兩位是細身材和高個

　　子。（4）只有一位是藍眼睛和黃頭發(fā)（5）阿黛爾和貝蒂眼睛顏色相同。（6）貝蒂和

　　卡洛爾頭發(fā)顏色相同（7）卡洛爾和多麗絲身材不同（8）多麗絲和阿黛爾身高相同。四

　　位中誰是約翰的夢中情人？

　　[簡單分析]

　　呵呵，顯然這是個數(shù)理邏輯問題了。可以建立形式化的模型來分析，也可以用樸素的推理過程來做。很有意思的，這是離散數(shù)學(xué)的魅力！