劉 倩

(西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，陜西 西安 710071)

0 引言

在大學(xué)概率論課程中，匹配問(wèn)題利用一般加法公式易于解決，但是在教學(xué)過(guò)程中，我們會(huì)先想到利用對(duì)立事件直接求解對(duì)立事件包含的有利場(chǎng)合數(shù)，即“全部錯(cuò)排”數(shù)。這是由于受到高中階段排列組合思維的影響。關(guān)鍵問(wèn)題是,錯(cuò)排數(shù)目很容易就能計(jì)算出來(lái)嗎？本文從一道高考錯(cuò)排問(wèn)題談起，討論錯(cuò)排數(shù)目的遞推公式，再擴(kuò)展到匹配問(wèn)題，討論匹配問(wèn)題的數(shù)學(xué)期望，即平均配對(duì)個(gè)數(shù)，最后進(jìn)一步將匹配問(wèn)題的條件加強(qiáng)，討論多項(xiàng)匹配問(wèn)題。

1 錯(cuò)排問(wèn)題

近年來(lái)，全國(guó)高考試題注重了對(duì)考生能力和素質(zhì)的考查，試題設(shè)計(jì)增加了貼近日常生活的應(yīng)用型案例，其中的“賀卡問(wèn)題”就屬于這方面的一道題。

例1(賀卡問(wèn)題[1])同室4人各寫一張賀年卡，先集中起來(lái)，然后每人從中拿一張別人送的賀年卡，則4張不同的賀年卡不同的分配方式有

A. 6種 B. 9種 C. 11種 D. 23種

這個(gè)問(wèn)題情境新穎，無(wú)法直接套用公式、法則，主要考查加法或乘法原理或從反面考慮(排除法)的思想方法，考查分析問(wèn)題與解決問(wèn)題的能力。

“賀卡問(wèn)題”實(shí)際是被著名數(shù)學(xué)家歐拉稱為“組合數(shù)論的一個(gè)妙題”的“裝錯(cuò)信封問(wèn)題”的一個(gè)特例?！把b錯(cuò)信封問(wèn)題”是指：一個(gè)人寫了n封不同的信及相應(yīng)的n個(gè)不同的信封，他把這n封信都裝錯(cuò)了信封，問(wèn)都裝錯(cuò)信封的裝法有多少種? 這個(gè)問(wèn)題是由當(dāng)時(shí)最有名的數(shù)學(xué)家約翰·伯努利的兒子丹尼爾·伯努利提出來(lái)的。這道高考題就是以組合數(shù)學(xué)中著名的“錯(cuò)排問(wèn)題”為背景，用生活實(shí)例設(shè)計(jì)問(wèn)題，十分新穎。

例2(錯(cuò)排問(wèn)題[2])有n個(gè)正整數(shù)1，2，3，…，n，將這n個(gè)正整數(shù)重新排列，使其中的每一個(gè)數(shù)都不在原來(lái)的位置上，這種排列稱為正整數(shù)1，2，3，…，n的錯(cuò)排，問(wèn)這n個(gè)正整數(shù)的錯(cuò)排個(gè)數(shù)是多少?

瑞士著名數(shù)學(xué)家歐拉按一般情況給出了一個(gè)遞推公式，

D(n)=(n-1)(D(n-2)+D(n-1)),

(1)

特殊地，D(1)=0，D(2)=1。

可以用一個(gè)直觀的例題理解該遞推公式并最終得到錯(cuò)排數(shù)的通項(xiàng)公式。

例3(裝錯(cuò)信封問(wèn)題)用A，B，C，…表示寫著n位友人名字的信封，a，b，c，…表示n份相應(yīng)的寫好的信紙。把錯(cuò)裝的總數(shù)為記作D(n)。假設(shè)把a(bǔ)錯(cuò)裝進(jìn)B里了，包含著這個(gè)錯(cuò)誤的一切錯(cuò)裝法分兩類：

1) b裝入A里，這時(shí)每種錯(cuò)裝的其余部分都與A、B、a、b無(wú)關(guān)，應(yīng)有D(n-2)種錯(cuò)裝法。

2) b裝入A、B之外的一個(gè)信封，這時(shí)的裝信工作實(shí)際是把(除a之外的)n-1份信紙b，c，…裝入(除B以外的)n-1個(gè)信封A，C，…，顯然這時(shí)裝錯(cuò)的方法有D(n-1)種。

總之，在a裝入B的錯(cuò)誤之下，根據(jù)加法原理，共有D(n-2)+D(n-1)種錯(cuò)裝法。

a裝入C，裝入D……的n-2種錯(cuò)誤之下，同樣都有D(n-2)+D(n-1)種錯(cuò)裝法，根據(jù)乘法原理，n個(gè)不同元素的錯(cuò)排數(shù)遞推公式為D(n)=(n-1)(D(n-2)+D(n-1))。

有了遞推公式，很容易得到錯(cuò)排數(shù)的通項(xiàng)公式

(2)

具體推導(dǎo)過(guò)程可參閱相關(guān)文獻(xiàn)[1]。事實(shí)上，用上述方法解題，就是反復(fù)考慮包含與排斥的情形，這實(shí)際就是利用了容斥原理。基于上面的遞推公式，賀卡問(wèn)題的正確答案是B。

下面考察錯(cuò)排數(shù)公式的兩個(gè)簡(jiǎn)單應(yīng)用。

例4數(shù)1，2，3，…，9的全排列中，求偶數(shù)在原來(lái)位置上，其余都不在原來(lái)位置上的錯(cuò)排數(shù)目。

分析實(shí)際上，這是1，3，5，7，9五個(gè)數(shù)的錯(cuò)排問(wèn)題，因此，錯(cuò)排數(shù)目是44。

例5對(duì)上述問(wèn)題略加變化:數(shù)1，2，3，…，9的全排列中，求恰好有5個(gè)數(shù)不在原來(lái)位置上的排列數(shù)。

2 匹配問(wèn)題

同樣沿用上述裝錯(cuò)信封問(wèn)題進(jìn)行探討。

例6(匹配問(wèn)題[3])一個(gè)人寫了n封不同的信及相應(yīng)的n個(gè)不同的信封，他任意地將這n封信裝入n個(gè)信封中，問(wèn)至少有一封信和信封是一致的概率是多少?

分析這個(gè)題目有多種解法。記Ai表示第i封信的信紙和信封一致，i=1,2,3,…,n,則所求概率為P(A1∪A2∪…∪An)。

解法1若直接計(jì)算有利場(chǎng)合數(shù)，無(wú)疑是十分復(fù)雜的。

解法2已知錯(cuò)排數(shù)通項(xiàng)公式(2)的情況下，利用對(duì)立事件進(jìn)行求解。

從而概率為

(3)

解法3相比前兩種方法，采用一般加法公式P(A1∪A2∪…∪An)，直接求解：

…

所以，

(4)

更進(jìn)一步，計(jì)算平均匹配個(gè)數(shù)，即求放對(duì)的信封數(shù)X的數(shù)學(xué)期望和方差。這同樣是一道易錯(cuò)題目。期望通過(guò)直接計(jì)算有利場(chǎng)合數(shù)，這無(wú)疑也是十分復(fù)雜的。針對(duì)復(fù)雜隨機(jī)變量的數(shù)學(xué)期望求解，可以利用期望的可加性進(jìn)行計(jì)算。

令

于是有

(5)

(6)

匹配問(wèn)題中匹配數(shù)的數(shù)學(xué)期望與方差均為1，與信封個(gè)數(shù)n無(wú)關(guān)。

3 多項(xiàng)匹配問(wèn)題[4]

例7有n個(gè)人填寫一份登記表并交一張照片，現(xiàn)在把登記表及照片任意地裝入n個(gè)有姓名的檔案袋中(每袋只允許裝入一份登記表及一張照片)，那么沒(méi)有一袋的登記表及照片都裝對(duì)的概率是多少？進(jìn)而這種場(chǎng)合下，錯(cuò)排數(shù)是多少？

解記Ai表示第i袋的登記表和照片都一致，i=1,2,…,n，利用一般加法公式(4)，得

(7)

其中,

代入公式(7)，得到

(8)

利用公式(2)和(8)，得到該多項(xiàng)配對(duì)問(wèn)題中的錯(cuò)排數(shù)目為

(9)

當(dāng)n=3，完全錯(cuò)裝的概率是13/18，此時(shí)，完全錯(cuò)裝的方法一共有26種。

4 結(jié)論

在概率論課程中，古典概型是一個(gè)學(xué)習(xí)的難點(diǎn)。本文以匹配問(wèn)題為研究對(duì)象，探討其不同解決方法之間的關(guān)系。我們發(fā)現(xiàn)大部分同學(xué)會(huì)想到對(duì)立事件，即解決“n個(gè)不同元素全部錯(cuò)排問(wèn)題”，與利用一般加法公式進(jìn)行計(jì)算，取對(duì)立后得到的結(jié)果是一致的。顯然，利用一般加法公式的求解要更加方便。這就是為什么在大學(xué)的概率論課程體系中，我們?cè)谝敫怕实墓砘x之后，會(huì)系統(tǒng)學(xué)習(xí)概率的性質(zhì)并引入概率論中幾個(gè)重要的公式，比如全概率公式、貝葉斯公式。這些公式的共同特點(diǎn)就是可以解決復(fù)雜的古典概型問(wèn)題[5-6]，因此在學(xué)習(xí)概率論時(shí)，要特別提醒學(xué)生注意概率論的各個(gè)基本概念和理論是怎樣運(yùn)用到實(shí)際生活中的。