韓新社

（武漢船舶職業(yè)技術(shù)學(xué)院公共課部，湖北武漢 430050）

問題 在一場激烈的足球賽開始前，售票工作正在緊張地進(jìn)行中。每張球票50元?，F(xiàn)有2n個人排隊購票，其中有n個人手持50元的鈔票，另外n個人手持100元的鈔票，假設(shè)開始售票時售票處沒有零錢。問這2n個人有多少種排隊方式，才不致使售票處出現(xiàn)找不開錢的局面？

解法一，從題目中可以推斷出，只有手持100元的人才需要找50元。也就是說，當(dāng)手持100元的球迷到達(dá)售票處時，售票處至少一張50元的零錢。不難看出，從隊首開始往后數(shù)，任何時候，只要手持100元球迷總數(shù)比手持50元的球迷少，就肯定可以把錢找開。從這個問題可以聯(lián)想到括號匹配問題。假設(shè)每個手持50元的球迷是一個左括號“（”，而手持100元的球迷是右括號“）”，要求任意一個左括號都要有一個右括號與它對應(yīng)。類似的，任意一個手持100元的球迷，他從售票處找回的50元都來自于他之前一個手持50元的球迷。所以，始終找得開錢的排隊方式對應(yīng)著合法的括號排列。

根據(jù)解決括號匹配問題的思路，可以考慮用棧來解決問題。假設(shè)存在一個棧，遍歷n個左括號“（”和n個右括號“）”排成的隊列，每次如果是左括號“（”，則將其壓人棧中；如果是右括號“）”，則讓棧尾的左括號“（”出棧，如果能夠始終保持棧中有足夠的左括號，那么該排列是一個合法排列。

因此，可以做如下分析。第0個符號一定是左括號，否則該隊列肯定出錯。假設(shè)第0個左括號跟第k個符號匹配，那么從第1個符號到第（k－1）個符號，第（k＋1）個符號到第（2n－1）個符號也都是一個合法的括號序列?？上攵?，k肯定是奇數(shù)。否則，第2個符號到第（k－1）個符號之間只有奇數(shù)個符號就不合法，設(shè)k＝2i＋1（i＝0，┄，n－1），如圖1所示。

圖1 括號排列示意圖

假設(shè)2n個符號中合法的括號序列個數(shù)為f（2n），若第0個括號（左括號）與第k＝2i＋1（i＝0，┄，n－1）個括號（右括號）匹配，那么剩余括號的合法序列為：f（2i）·f（2n－2i－2）個，根據(jù)上面的分析，可以得到如下遞推式：

解法二，為了便于描述，這里用1表示持有50元的球迷，用0表示持有100元的球迷。那么2n個球迷的排隊就對應(yīng)n個1和n個0的排列，例如：1，1，0，0，0，┄，1。如果序列的任意前k（k＝1，2…，2n－1）項中1的個數(shù)都不少于0的個數(shù)，我們稱這樣的一個序列是合法的，否則稱其為非法序列。顯然合法的序列正好與可行的排列方式一一對應(yīng)。同時，定義由（n－1）個1和（n＋1）個0組成的序列為σ序列（僅僅是一個記號，沒有任何特殊的含義），這樣的序列共有

在一個非法序列中，存在某個k，使得序列前k個項中1的個數(shù)少于0的個數(shù)。即存在k使得前k項中1的個數(shù)比0的個數(shù)剛好少1個，取其中最小的k。那么這個序列的后（2n－k）項中1的個數(shù)剛好會比0的個數(shù)多1個。將后2n－k項中的0換為1，1換為0，于是得到一個新的序列：由（n－1）個1和（n＋1）個0組成的序列，那么這是一個σ序列。這樣我們就已經(jīng)成功地將一個非法序列對應(yīng)到唯一一個σ序列。所以，非法序列和σ序列一一對應(yīng)。

同理，σ序列也可一映射到一個非法序列。對任意一個σ序列，存在某個k，使得序列的前k項中1的個數(shù)少于0的個數(shù)（因為只有n－1個1，而有n＋1個0）。進(jìn)一步地，存在某個k，使得序列前k項中1的個數(shù)比0的個數(shù)剛好少一個，取其中最小的k。那么這個序列的后（2n－k）項中1的個數(shù)剛好會比0的個數(shù)少1個。將后（2n－k）項的0換成1，1換成0，于是得到一個新的序列：由n個1和n個0組成。而這個序列正是一個非法序列（因為前k項中1的個數(shù)比0的個數(shù)少）。我們又成功地將一個σ序列對應(yīng)到唯一一個非法序列。

1 盛 驟，謝式千，潘承毅.概率論與數(shù)理統(tǒng)計［M］.高等教育出版社，2006.

2 吳 翊，吳孟達(dá)，成禮智.數(shù)學(xué)建模的理論與實踐［M］.國防科技大學(xué)出版社，2002.

3 張珠寶.數(shù)學(xué)建模與數(shù)學(xué)實驗［M］.高等教育出版社，2005.