一個人談過k次戀愛（k大於等於12），那麼他集齊十二星座的概率是多少？

01-14

如題，假設他的擇偶條件中不涉及星座，並且各個星座與他戀愛的概率相同。這只是一道嚴肅的概率計算題。

如果用組合數學的方法做，會出現大量重複的情況，燒腦燒了一個小時，這條路不通。目前高贊用多項式倒是推出個漂亮的遞推公式，但是燒電腦。

然而！我在高贊 @Luyao Zou 評論里發現 @馮某某用的是馬爾可夫鏈，我的天簡直是天才啊！我一定要寫出來沾一下理性之光！

我們把問題化簡為：

一個雙性戀談過k次戀愛（k大於等於2），那麼他集齊兩個性別的概率是多少？

首先這個雙性戀者要麼是沒談過戀愛，要麼是只和一個性別的人談過戀愛，要麼是兩個性別都談過。把以上三種狀態標記為X0 X1 X2。

然後是轉移概率，比如說一個 X1的人再談一次戀愛他變成X0的概率是0、變成X1的概率是0.5,、變成X2的概率是0.5，以此類推我們可以寫出轉移矩陣

（忽略括弧......）

如果我們想計算一個沒談過戀愛的人(X0)在談一次戀愛後，轉移到三個狀態的概率，只需要用行向量(1,0,0)左乘轉移矩陣得到(0,1,0)，也就是說他百分百地變成了只和一個性別的人談過戀愛，超棒有沒有！

在深入一點，如果這個人告訴我們，他有a的概率沒談過戀愛，b的概率只和一個性別談過戀愛，c的概率和兩個性別的人都談過戀愛。現在得知他又談了一次戀愛，那麼目前他三種狀態的概率是多少呢？用(a,b,c)乘以矩陣得(0 , a+0.5b , 0.5b+c)，超棒有沒有！！

如果再談兩次，那就再乘以矩陣兩次，超棒有沒有！！！

題中的人一開始沒談過戀愛，那麼狀態就是(1,0,0)，再用矩陣的k次冪乘初始狀態得到的行向量的最後一個元素就是他男女通殺的概率，超棒有沒有！！！！

以此類推，12星座就是用一個13*13的矩陣記錄下轉移概率，乘k次，就這麼爽！

直接把時間複雜度從高票的O(2^n)降到O(n)，超爽有沒有！(其實高票的方案如果採用記錄各個alpha值而不用遞歸的話也可以把時間複雜度降到O(n)但空間複雜度會增加到O(n)(演算法使我快樂(傲嬌臉)))

唉……昨天發的這個結果

$P(k) = frac{k!}{12^{12}(k-12)!}$

是錯的，丟人啊！這個式子很明顯的，P(20)=2.7 已經爆表了。錯在很多情況重複計算了。你們啊，還點贊……

但是代數多項式這個思路是對的。從代數角度來看，這個問題等價於，12 元多項式函數

$f(x_1,x_2,ldots,x_{12}) = (x_1+x_2+cdots+x_{12})^k$

中， $x_1x_2x_3cdots x_{12}$ 每一個變數次數都大於等於 1 的項的係數和與所有項的係數和之比為多少。

用遞推關係來算吧。

先約定幾個記號。考慮一般情況，記

$f_n^{(k)} = left(sum_{i=1}^nx_i ight)^k$

為 n 元 k 次多項式。本問題的情況就對應 $f_{12}^{(k)},,(k >12)$

如果把這個多項式展開，記包含 n 個變數中 m 個的項前的係數為 $alpha_m^{(k)}$

就是說， $alpha_1^{(k)}$ 就是只含有一個變數的項 $x_1^k,x_2^k,ldots x_n^k$ 這幾個項前面的係數和； $alpha_2^{(k)}$ 就是只含兩個變數的 $x_i^lambda x_j^{(k-lambda)},,(i eq j)$ ；以此類推。當然， $mleqmin(n,k)$ ，因為 m 不可能超過變數數，m 也不可能超過多項式的總次數

下面開始找遞推關係。很顯然的

$alpha_1^{(1)} = n$

$alpha_0^{(k)} = 0$

因為 $f_n^{(1)} = x_1 + x_2 + cdots + x_n$

而不可能存在不含任何變數的項

當次數 k 增加 1 時，可以把多項式看成乘積

$f_n^{(k)} = f_n^{(k-1)}f_n^{(1)} = f_n^{(k-1)}( x_1 + x_2 + cdots + x_n )$

那麼在 $f_n^{(k)}$ 中只含 m 個變數前的係數和 $alpha_m^{(k)}$ 會是多少呢？

它包含兩種情況。一種來自 $f_n^{(k)}$ 中只含 m-1 個變數的項，在 $( x_1 + x_2 + cdots + x_n )$ 中另外找一個 $x_j$ 不屬於之前 m-1 個項的，乘起來，這種選擇應該有 n-(m-1) 種。另一種來自 $f_n^{(k)}$ 中只含 m 個變數的項，在 $( x_1 + x_2 + cdots + x_n )$ 中只能選擇乘上屬於之前 m 個變數的項。這種選擇有 m 種。所以

$alpha_{m}^{(k)} = (n+1-m)alpha_{m-1}^{(k-1)} + malpha_m^{(k-1)}$

有了這個關係，再加上初始條件，就可以推算任何一種情況了。任何出現 m=0 的情況，都變成 0

這個關係對不對，我用 n=2 來驗證一下。因為 n=2 的情況就是二項式展開，我們明確知道

$alpha_1^{(k)} = 2,,,alpha_2^{(k)} = 2^k - 2$

用上面的遞推關係，令 n=2，

$alpha_1^{(k)} = (3-1)alpha_0^{(k-1)} + 1alpha_1^{(k-1)} = alpha_1^{(k-1)} = cdots = alpha_1^{(1)} = 2$

$alpha_2^{(k)} = 1alpha_1^{(k-1)} + 2alpha_2^{(k-1)} = 2+2alpha_2^{(k-1)}$

這個遞推可以輕鬆地求到通項的，因為

$alpha_2^{(k)} + 2 = 2(2+alpha_2^{(k-1)}))$

就是 $2^k$ ，所以 $alpha_2^{(k)} = 2^k - 2$

所有項的係數和好求，只要令 x1 到 xn 全部等於 1，總係數和即為 $alpha_ ext{total} = f(1,1,ldots,1) = n^k$

這有點信心了。那麼令 n=12，然後寫個小程序來算

#! encoding = utf8

def alpha(n, k, m): if k &< m or m==0: return 0 elif k &< 1 or m &< 1: raise ValueError("k and m must be larger than 1") elif not (isinstance(n, int) and isinstance(k, int) and isinstance(m, int)): raise ValueError("n, k, and m must be integer") elif k==1 and m == 1: return n else: c = alpha(n, k-1, m-1) * (n + 1 - m) + alpha(n, k-1, m) * m return c if __name__ == "__main__": n = 12 for i in range(19): k = i + n co = alpha(n, k, n) pk = co/(n**k) print("{:4d} {:.4%}".format(k, pk))

遞歸效率不高的，別把 range() 設得太大，把電腦跑死了別怪我

n = 12，k 從 12 一直到 30 的結果：

好難啊……如果降低點要求，集齊四季的話（n=4），好一點：

看來啊，還是要多找女朋友

我編了個小程序模擬。

20 5.1%

30 36.2%

40 67.3%

50 85.1%

60 93.6%

70 97.2%

80 98.9%

90 99.5%

100 99.8%

大概從145開始就絕大多數是100%了...

http://www.guokr.com/post/592618/

萬一有人專門收集這個呢？233

((1/12)^12)*(11/12)^(k-12)

十二分之一的十二次方乘以十二分之十一的k-12次方

k個恰好集齊12個的幾率，那這就需要滿足第k-1個時集齊了11個星座。我們把這k-1個人編號為1~k-1，那麼其中一定有11個人互相之間星座不同。

假如遇上任意一個星座的人的概率均等，那麼遇到這十一個人的概率為(1/12)的11次方。11個人每個人的星座都不同嘛。對於剩下的(k-12)個人，只要他們的星座不是正好缺的第12個星座就可以了。也就是說他們來自任意已存在的11個星座都可以，每個人的概率為11/12，一共(11/12)^(k-12)的概率

好了，這時候這個同學和第k-1個妹紙分手了，迎來了人生的大圓滿湊齊第12個，遇見某個特定星座的概率是1/12。要滿足k-1個人湊齊了11個星座的概率是(1/12)^11 * (11/12)^(k-12),第k個湊齊剩下那個星座的概率是1/12，那麼k個正好湊齊12星座的概率就兩者相乘

(1/12) × （1/12）^11 × (11/12)^(k-12) 竟然打出乘號了好激動！

以上，是問題「K個正好集齊12星座」的概率。如果你要問，不一定是K個正好集齊，而是k大於等於12，k個的時候集齊了但不一定是正好集齊。我還真不知道怎麼辦，等人回答吧。

咋算的啊？有木有人知道公式

這不就是贈券收集問題嗎

sum_{i=0}^{12}C(12, i) * (-1)^i * (i / 12)^K

小學容斥

運氣不好的時候就差最後一個死活集不齊

已談完十二星座發現人生最悲哀的是最後發現沒有一個星座適合我我只是要孤獨終老了嗎

組合數學

簡直喵的生氣，別說近兩年一個男票都沒有，已經在天蠍座上栽了三四五六次了，感覺集齊十二星座

並

不

可

能