韓新社
(武漢船舶職業(yè)技術(shù)學(xué)院公共課部,湖北武漢 430050)
問題 在一場激烈的足球賽開始前,售票工作正在緊張地進行中。每張球票50元?,F(xiàn)有2n個人排隊購票,其中有n個人手持50元的鈔票,另外n個人手持100元的鈔票,假設(shè)開始售票時售票處沒有零錢。問這2n個人有多少種排隊方式,才不致使售票處出現(xiàn)找不開錢的局面?
解法一,從題目中可以推斷出,只有手持100元的人才需要找50元。也就是說,當手持100元的球迷到達售票處時,售票處至少一張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)。進一步地,存在某個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 吳 翊,吳孟達,成禮智.數(shù)學(xué)建模的理論與實踐[M].國防科技大學(xué)出版社,2002.
3 張珠寶.數(shù)學(xué)建模與數(shù)學(xué)實驗[M].高等教育出版社,2005.