100種不同英雄，抽300次，每次抽取都是獨立的。請問這300次抽取抽到全部100個英雄的概率是多少？

01-11

100種不同英雄，抽300次，每次抽取都是獨立的。請問這300次抽取抽到全部100個英雄的概率是多少？

算了一下，很小，大概0.4%的樣子。

先講方法，後面給代碼

1. 我們把問題抽象一下，把具體的數字拿掉，用 $f(n, m, N)$ ，表示有 $N$ 個英雄，抽取 $n$ 次，抽出來 $m$ 個不同的英雄的概率

先不考慮邊界情況，那麼我們看這個函數要怎麼算：假設我抽 $n$ 次抽出來 $m$ 個不同的，分兩種情況，最後一次抽出來的以前也抽出來過和最後一次抽出來的，以前從沒抽出來過，如下

最後一次這個英雄以前也抽出來過，那麼之前相當於 $n-1$ 次抽出來了 $m$ 個英雄，概率為 $f(n-1, m, N)$ ，算上這次還得在這m個英雄中間抽，所以總共是 $frac{m}{N}f(n-1, m, N)$
最後這個英雄第一次抽出來，那麼通過類似的分析可以得到此時的概率是 $frac{N - m + 1}{N} f(n - 1, m - 1, N)$

而整個概率就是這兩種情況加起來，因為是不重不漏的劃分。

邊界情況懶得分析了，出來0次選0個英雄是100%的，其餘都是0

2.下面給出計算的代碼，附圖展示了100個英雄的情況下，抽取次數和抽中所有英雄的概率之間的關係，可以看到300次的時候，抽出所有英雄的概率是非常小的，500次大概就能有50%的概率隨出所有英雄了，抽1000次情況下得到100個不同的概率就很接近100%了

--------------------------------------

正事不做，跑到這來繼續講題目，一個組合數學的方法，容斥原理，假設抽 $n$ 次的方案沒選出英雄 $i$ 的方案的集合記為 $A_i$ ，記住是沒選出，那麼很容易知道沒選出k個英雄的方案數是：

$(N-k)^n$

然後直接套到容斥原理，我們就得到了選出所有英雄的方案數： $sum_{k=0}^{N}{-1^k { m C}_N^k}(N-k)^n$

這個結果除以 $N^n$ 就是結果，不過上式還是個累加的式子，沒研究怎麼化簡，簡單寫了個程序，驗證了一下和前面的結果是一致的：）

大家說的都很好，我這裡再提供一個當n（題目中為100）比較大的時候，快速近似求解以及低成本運算的思路（Poisson Process近似）

$P(Tleq t)=prod_{i=1}^{100}(1-e^{-p_{i}t } )$

$p_{i}=frac{1}{100}$

於是

$P(Tleq 300)=(1-e^{-frac{300}{100} } )^{100}approx 0.006054714$

事實上，當n很大的時候，我們可以用熟悉的重要極限得到更簡明的結論（化簡後的結論）：

$lim_{n ightarrow infty }{P(Tleq t)}=(1-e^{-frac{t}{n} } )^{n}=(1-e^{-frac{t}{n} } )^{e^{frac{t}{n}+lnn-frac{t}{n} }}=e^{-e^{lnn-frac{t}{n} } }$

下面是組合數學法和泊松估值法在本題中的對比結果（黑：組合數學法，紅：泊松法，綠：化簡後的結論）：

後兩種計算速度明顯要快於組合數學方法，這裡不做數據比較

-----------------------------------------------------------------------------

大概是0.004 貼代碼

-module(calc). -compile(export_all).


print() -&>

	{A,B} = calc_p(0,0),

	io:format("p is ~w",[B/A]).
calc_p(A,150) -&>

	{A,150};

calc_p(A,B) -&>

	N= calc_p1(300,[]) + B,

	calc_p(A+1,N).

calc_p1(0,L1) -&> L2 = lists:usort(L1), %io:format("L2:~w",[[length(L2),length(L1)]]), case erlang:length(L2) of 100 -&> 1; _ -&> 0 end; calc_p1(N,L1) -&> %random:seed(now()), Rand = random:uniform(100), calc_p1(N-1,[Rand|L1]).

結果圖：

我自己也寫過code算過,很早之前了,大概0.05%左右的概率. 當時是進行大量的實驗得到的概率的,有沒有辦法通過數學方法得到精確值??

應該是 $C_{300}^{100} imes P_{100}^{100} div 100^{300}$ 吧

100個盒子300個球，300個球隨便放，可以平攤可以全堆1個盒子里(這盒子真大)，這是全部事件，高中排列組合可以算，滿足題目要求的事件為100個盒子裡面每個都有球，剩下200個球隨便放，這裡需要分步計算，100個盒子里的球c300 100*a100 100，再乘以下一步中200個球的放法，計算方式同所有事件，鑒於答案中已經列出的計算式，此題計算量巨大

另付全部事件的計算方式:鑒於100個盒子放300個球較難理解，可以看做300個球去選盒子，每個球都有100個選擇，則所有事件為100的300次方

P.S.:題主保重身體，不要累著了

P.S.2:圖片貌似好像大概似乎出了點小小的問題，如果要看請私聊我