[科普中國]-西蒙-紐科姆問題

西蒙-紐科姆問題(Simon-Newcomb's problem)是確定某種排列數(shù)的一個(gè)問題，設(shè)π是多重集S={iki|i=1，2，…，n}的一個(gè)排列，把π分段，使得段數(shù)最少且每段中數(shù)字呈非降順序，這樣的每一段稱為π的一個(gè)上升段.所謂西蒙-紐科姆問題就是求S的恰有r個(gè)上升段的排列數(shù)N(1k1，2k2，…，nkn;r).若以S2(n，k)表第二類斯特林?jǐn)?shù)，則N(1k1，2k2，…，nkn;r)等于(A)k11(A)k22…(A)knn的展開式中xr的系數(shù)，其中的(A)i=A(A+1-x)(A+2-2x)…·(A+k-1-(k-1)x)，Ai≡Ai(x)，n=1，2，…，且Ai(x)=x∑i-1k=0S2(i，i-k)(i-k)!(x-1)k。1

基本介紹十九世紀(jì)著名的英國天文學(xué)家西蒙·紐科姆(Simon Newcomb)把一副撲克牌一張一張地放在桌上，只要牌的面值是以非減次序出現(xiàn)的，他就把它們堆成一堆，但每當(dāng)待堆放的下一張牌的面值小于前者時(shí)，他就開始一個(gè)新的堆，他想要知道，在整副牌以這種方式分發(fā)完畢之后，形成給定堆數(shù)的概率。

因此，西蒙·紐科姆問題就是，求在一個(gè)多重集合的隨機(jī)排列中，路段的概率分布問題2。

相關(guān)介紹下面將推導(dǎo)出現(xiàn)于這個(gè)游戲中的平均堆數(shù)2。

首先假定有m種不同類型的牌，每種類型恰有p張。例如，通常的橋牌，如果不考慮花色時(shí)，有m=13和p=4。P.A.麥克馬洪發(fā)現(xiàn)了應(yīng)用于這種情況的值得注意的對稱性(Combinatory Analysis1，(Cambridge，1915)，212-213]：有k+1個(gè)路段的排列個(gè)數(shù)等同于有個(gè)路段的排列個(gè)數(shù)。當(dāng)p=1時(shí)，這個(gè)關(guān)系易于驗(yàn)證，但對于p>1時(shí)，它是十分令人驚奇的。

顯然，沒有很簡單的對應(yīng)；麥克馬洪的證明是以生成函數(shù)而不是以一種組合構(gòu)造為基礎(chǔ)的。但福塔的對應(yīng)提供了一個(gè)有用的簡化，因?yàn)樗嬖V我們，在具有k-1個(gè)路段的排列和其兩行表示法恰含有k個(gè)x1的情況，而且等價(jià)于。由于(1)對應(yīng)于具有南k+1個(gè)路段的一個(gè)排列，而(2)對應(yīng)于具有個(gè)路段的一個(gè)排列，而且由于把(1)變?yōu)?2)的變換是可逆的(它把(2)變回(1)]，麥克馬洪的對稱性條件已經(jīng)建立。

由于對稱性，在一個(gè)隨機(jī)排列中路段的平均數(shù)必須是

例如，利用一副標(biāo)準(zhǔn)撲克牌，由西蒙·紐康姆的單人游戲得到的平均堆數(shù)將是25(所以它不象是一種有吸引力的單人游戲)。

給定任意多重集合，其中諸x是不同的，利用一個(gè)相當(dāng)簡單的論證，實(shí)際上可以一般地確定路段的平均數(shù)。設(shè)，并想象這個(gè)多重集合的所有排列都已經(jīng)寫下來，我們來考察；對于每個(gè)固定的i值，大于的機(jī)會如何，這里1≤i的次數(shù)恰是≠的次數(shù)之半，而且不難看出，==xj恰有次，其中N是排列的總數(shù)。因此，=恰有：

次，而且>恰有

次。因?yàn)樵诿總€(gè)排列中定有一個(gè)路段在an處結(jié)束，因此若對i求和并加上N，則得到在所有N個(gè)排列當(dāng)中路段的總數(shù)

除以N即給出所求的平均路段數(shù)2。

本詞條內(nèi)容貢獻(xiàn)者為:

王海俠 - 副教授 - 南京理工大學(xué)