探究一道以卡特蘭數(shù)為背景的概率題

安徽省淮南第二中學(xué)(232001) 趙帥

一、原題呈現(xiàn)

(淮南第二中學(xué)屆高三模擬)某中學(xué)為了豐富學(xué)生的課外生活,減輕學(xué)生的生活壓力,組織學(xué)生開展以班級(jí)為單位的猜謎語比賽,規(guī)定每班的初始分為0 分,隨機(jī)抽取題目,猜對(duì)得5 分,猜錯(cuò)扣5 分,并且猜測結(jié)果只有“對(duì)”與“錯(cuò)”兩種,設(shè)高二年級(jí)某班學(xué)生猜對(duì)的概率為,猜錯(cuò)的概率為,記“該班學(xué)生完成n次猜謎語后的總分為Sn”.若規(guī)定積分扣到零分則被淘汰(第一次輸也會(huì)被淘汰),求S5=5 的概率.

解析S5=5,即總共猜謎語5 次,猜錯(cuò)2 次,又由Si≥5(i=1,2,3,4),可得共有以下可能:

①第一次和第二次猜對(duì),第三次猜錯(cuò),第四次猜對(duì),第五次猜錯(cuò);

②第一次、第二次和第三次猜對(duì),其余兩次猜錯(cuò).故所求概率為:

二、問題一般化與變式

易知,若猜謎語的次數(shù)為奇數(shù),則猜正確和猜錯(cuò)誤的次數(shù)中二者必為一奇數(shù)一偶數(shù),則最后的得分必為5 的奇數(shù)倍;若猜謎語的次數(shù)為偶數(shù),則猜正確和猜錯(cuò)誤的次數(shù)中二者必為兩奇數(shù)或兩偶數(shù),則最后的得分必為5 的偶數(shù)倍.

在滿足規(guī)定:積分扣到零分則被淘汰(第一次猜錯(cuò)也會(huì)被淘汰)的情況下,則S2n+1=5×(1+2m)=10m+5(m,n∈N)與S2n=5×2m=10m(m,n∈N?)概率為多少?

分析要解決這個(gè)問題,先從解決S5=5 的概率入手.我們可建立一個(gè)坐標(biāo)“棋盤”,為了簡潔,縱坐標(biāo)為得分的.如圖1.

圖1

首先,初始情況對(duì)應(yīng)圖中O點(diǎn),由于第一次猜謎語一定要贏,則必須到達(dá)A(1,1)點(diǎn),然后沿著最短路徑到達(dá)B(5,1)點(diǎn)(過程中必有兩次正確兩次錯(cuò)誤).顯然符合規(guī)定的路徑條數(shù)有且只有兩條,故所求概率為:

顯然這種解法易于觀察,但對(duì)于研究更一般的情形很難解決.所以對(duì)解法做出以下調(diào)整.

若不考慮規(guī)定,則從A點(diǎn)到B的最短路徑數(shù)為=6,但很顯然6 條最短路徑中并不是每個(gè)都符合規(guī)定(即路徑要在x軸上方),為此,取B′(5,?1),則可發(fā)現(xiàn),不滿足規(guī)定的A點(diǎn)到B點(diǎn)所有經(jīng)過x軸的最短路徑與A點(diǎn)到B′點(diǎn)所有最短路徑為一一對(duì)應(yīng)的關(guān)系,則它們的路徑數(shù)相同,故不符合規(guī)定的最短路徑數(shù)為=4.故所求概率為

圖2

據(jù)此,我們根據(jù)以上分析可得以下定理,并證明之.

定理1 由整點(diǎn)A(x1,y1)到整點(diǎn)B(x2,y2)的所有最短路徑條數(shù)為

證明可知直線AC的方程為:y?y1=x?x1,直線BC的方程為:y?y2=?(x?x2),解得C點(diǎn)坐標(biāo)為,故由點(diǎn)A到點(diǎn)C需要經(jīng)過x3?x1=次步驟,同時(shí)也為共x2?x1步驟中所有“上升”的步驟數(shù).由組合知識(shí)可得,由整點(diǎn)A(x1,y1)到整點(diǎn)B(x2,y2)的所有最短路徑條數(shù)為

定理2 由整點(diǎn)A(x1,y1)到整點(diǎn)B(x2,y2)(其中y1>0,y2>0,x2?x1≥y1+y2)圖象恒在x軸上方(不含x軸)的所有最短路徑條數(shù)為

證明由定理1 可知,為整點(diǎn)A(x1,y1)到整點(diǎn)B′(x2,?y2)(點(diǎn)B關(guān)于x軸的對(duì)稱點(diǎn))的所有最短路徑數(shù).即證由整點(diǎn)A(x1,y1)到整點(diǎn)B(x2,y2)圖象經(jīng)過x軸所有最短路徑數(shù)等于由整點(diǎn)A(x1,y1)到整點(diǎn)B′(x2,?y2)的所有最短路徑數(shù).設(shè)P為由點(diǎn)A到點(diǎn)B所有經(jīng)過x軸的最短路徑構(gòu)成的集合,P′為由點(diǎn)A到點(diǎn)B′所有最短路徑構(gòu)成的集合,即證|P|=|P′|.下證P與P′為一一映射.

設(shè)由點(diǎn)A到點(diǎn)B的最短路徑中與x軸的第一個(gè)交點(diǎn)為點(diǎn)M,則由點(diǎn)M到點(diǎn)B的路徑與由點(diǎn)M到點(diǎn)B′的路徑均關(guān)于x軸對(duì)稱,且剩余路徑均相同,顯然P與P′為一一映射,故|P|=|P′|,定理成立.

變式1 若積分扣到零分則被淘汰(第一次猜錯(cuò)也會(huì)被淘汰),求S9=15 的概率.

解設(shè)猜對(duì)的次數(shù)為x,猜錯(cuò)的次數(shù)為y,則有x+y=9且x?y=3 解得x=6,y=3.由于規(guī)定,則需求出從(1,1)點(diǎn)到(9,3)點(diǎn)的最短路徑條數(shù)與(1,1)點(diǎn)到(9,?3)點(diǎn)的最短路徑條數(shù)之差,則可通過構(gòu)造棋盤得:

變式2 若積分扣到零分則被淘汰(第一次猜錯(cuò)也會(huì)被淘汰),求S2n+1=10m+5(m,n∈N)與S2n=10m(m,n∈N?)的概率.

解對(duì)于S2n+1=10m+5(m,n∈N),設(shè)猜對(duì)的次數(shù)為x,猜錯(cuò)的次數(shù)為y,則有x+y=2n+1 且x?y=2m+1 解得x=m+n+1,y=n?m.由于規(guī)定,則需求出從(1,1)點(diǎn)到(2n+1,2m+1)點(diǎn)的最短路徑條數(shù)與(1,1)點(diǎn)到(2n+1,?2m?1)點(diǎn)的最短路徑條數(shù)之差,則可通過構(gòu)造棋盤得:同理,對(duì)于S2n=10m(m,n∈N?),可得:

三、鏈接高考并推廣

題目(2016年高考全國Ⅲ卷)定義“規(guī)范01 數(shù)列”{an}如下:{an}共有2m項(xiàng),其中m項(xiàng)為0,m項(xiàng)為1,且對(duì)任意的k≤2m,a1,a2,···,ak中0 的個(gè)數(shù)不少于1 的個(gè)數(shù).若m=4,則不同的“規(guī)范01 數(shù)列”共有( )

A.18個(gè) B.16個(gè) C.14個(gè) D.12個(gè)

解記每項(xiàng)取1 得1 分,取0 扣一分.則此“規(guī)范01數(shù)列”的個(gè)數(shù)為:由(1,1)點(diǎn)到(8,0)點(diǎn)且圖象恒在直線y=?1 圖象上方的最短路徑條數(shù),構(gòu)造棋盤,也即:由(1,2)點(diǎn)到(8,1)點(diǎn)且圖象恒在x軸上方的最短路徑條數(shù),即:

推廣定義“規(guī)范01 數(shù)列”{am+n} 如下:{am+n}共有m+n項(xiàng),其中m項(xiàng)為1,n項(xiàng)為0,且對(duì)任意的k≤m+n(m≥n),a1,a2,···,ak中0 的個(gè)數(shù)不少于1的個(gè)數(shù),求不同的“規(guī)范01 數(shù)列”個(gè)數(shù).

解記每項(xiàng)取1 得1 分,取0 扣一分.則此“規(guī)范01 數(shù)列”的個(gè)數(shù)為:由(1,1)點(diǎn)到(m+n,m?n)點(diǎn)且圖象恒在直線y=?1 圖象上方的最短路徑條數(shù),也即:由(1,2)點(diǎn)到(m+n,m?n+1)點(diǎn)且圖象恒在x軸上方的最短路徑條數(shù),即:

綜上,再進(jìn)行深入研究可知問題的結(jié)論背景直指組合數(shù)學(xué)中的“卡特蘭數(shù)”(組合數(shù)學(xué)中一個(gè)常出現(xiàn)在各種計(jì)數(shù)問題中的數(shù)列,其在出棧次序問題,凸多邊形三角劃分問題,信息學(xué)中有很多得應(yīng)用).我們可通過構(gòu)造棋盤模型,將原本復(fù)雜的問題變?yōu)楦鼮榫唧w清晰,為解決這類概率(計(jì)數(shù))問題提供了便利.