求問一道概率題，6個小孩有6條狗，我隨機的把狗給小孩，全部錯誤（即沒有一隻狗找到主人）的概率是多少？

01-21

如題，求一個機智的方法，或者隨便什麼想法，能稍微啟發下我，謝謝！
=========
8月30日更
感謝大家的回答，我已經理解了！

這是「錯排問題」，錯排的數目是 $n!(frac{1}{2!}-frac{1}{3!}+cdots+(-1)^nfrac{1}{n!})$ ，相應的概率就是 $frac{1}{2!}-frac{1}{3!}+cdots+(-1)^nfrac{1}{n!}$

如果要推導錯排的數目，常用的做法是遞推，這裡不再贅述，網上搜索一下就好；

不過也可以直接推導概率，基本想法就是容斥原理

（容斥原理在集合數目少的時候可以用Venn圖畫出圖示，嚴格證明可以用數學歸納法）

用小孩和小狗的例子來說明一下這個式子， $A_1$ 表示「1號孩子得到了自己的小狗，其它小孩不論」的所有情況， $A_1 cup A_2$ 表示「1號孩子或者2號孩子中至少有一個人得到了自己的小狗，其它小孩不論」的所有情況， $A_1 cap A_2$ 表示「1號孩子和2號孩子都得到了自己的小狗，其它小孩不論」的所有情況。外面那個P是指概率(Probability)， $P(A_1)$ 就是 $A_1$ 發生的概率。

注意到這裡面有對稱性（也就是說， $A_1$ ~ $A_6$ 的數目是相同的，相應的 $A_1 cup A_2$ 和任意的 $A_i cup A_j$ 的數目也是相同的，等等等等），所以我們可以把k個A相交的概率記為 $a_k = mathbb{P}(A_{i_1} cap A_{i_2} cap cdots cap A_{i_k})$ ，它的含義是「同時有k個小孩都得到自己的小狗（其它小孩不論）的概率」（所以所謂的「對稱性」就是不管是對哪k個小孩這個概率都是相同的），很容易計算得出 $a_k=frac{(n-k)!}{n!}$ ，分母是所有的排列總數，分子是剩下n-k個小孩分配n-k條小狗的排列總數。

此時上述容斥原理可以寫成

這裡 $inom{n}{k}=frac{n!}{k!(n-k)!}$ 是二項式係數，和後面的 $a_k=frac{(n-k)!}{n!}$ 相乘，正好只剩下 $frac{1}{k!}$ ，因此「至少有一個小孩拿到自己的小狗」的概率就是

$displaystyle sum_{k=1}^n(-1)^{k-1}frac{1}{k!}=1-frac{1}{2!}+frac{1}{3!}-cdots+(-1)^{n-1}frac{1}{n!}$

而「全部拿錯」是「至少有一個拿對」的對立事件，兩者的概率和為1，所以相減之後就得到了上述答案。

只有高中概統水平的渣渣表示突然對這個問題產生了興趣，自己研究了一番，來強答一波……如有誤請大牛們輕噴orz

記有n個元素進行全排，錯排的情況數為a_n

a_2顯然為1

n=3時，可以這樣看，全排中

1.要麼順序全對（1種）

2.不會有對2錯1的情況

3.要麼對1錯2，就是先從3個元素中選1個規定它位於正確的位置（3C1），然後剩下兩個元素要求它們錯排（a_2），總結果3C1*a_2

4.剩下的情況就是3個元素全部錯排，用3！減去上面的就行：a_3=3！-3C1*a_2-1=2

n=4.5.6時演算法類似，甚至可以寫出a_n的遞推公式，見圖，雖然對於這樣一個遞推本渣渣無力解之orz

答完後看了看百度百科-錯排問題，給出的方法比我的高明多了，遞推式簡單易解⊙▽⊙這就是演算法的魅力啊，同樣的問題，不同的思路，數學處理難度天壤之別……

題主的問題可以抽象成1-6這六個數字構成的集合到自身的一個bijection。

首先可以得到所有可能的映射總數是6! = 720，然後需要做的是求出符合要求的映射個數。由於題意，每個數字不能映射到自己。

Digression 1:

下面約定 (a1, a2, a3, ... , an) 代表映射a1-&>a2-&>a3-&>...-&>an-&>a1，形成一個圈，也就是說a1映射到a2，a2映射到a3，…依此類推，a(n-1)映射到an，an映射回a1。可以證明只要是有限的集合內的bijection都可以寫成這種表達式，或者這種表達式的組合。（其實這就是permutation，逃）

註：(a1, a2, a3, ... , an)和(an, a1, a2, a3, ... , a(n-1))是一樣的。

回到正題，集合內總共有6個元素，需要將其內部的bijection表達成上述形式。而括弧內的元素個數要&>1，因為=1的話就相當於是這個元素映射到自己了，這是我們要排除的情況。

而 6 = 4+2 = 3+3 = 2+2+2，也就是有四種可能的結構：

1. (a1, a2, a3, a4, a5, a6)

2. (a1, a2, a3, a4)(a5,a6)

3. (a1, a2, a3)(a4, a5, a6)

4. (a1, a2)(a3, a4)(a5, a6)

Digression 2:

對於含有n個元素的(a1, a2, a3, ... , an)，不同的組合方式有 (n-1)! 種，嚴格的證明可以用數學歸納法。即對於(a1, a2, a3, ... , a(n-1))，an有n-1種插入方法。

讓我們再次回到正題 (?ω?)

第1種情況，有 5! = 120 種可能；

第2種情況，首先有 6C4 = 15 種劃分，於是有 15*3!*1! = 90 種可能；

第3種情況，有 6C3 / 2! = 10 種劃分，於是有 10*2!*2! = 40 種可能；

第4種情況，有 6C2*4C2 / 3! = 15 種劃分，於是有 15*1!*1!*1! = 15 種可能。

總共120 + 90 + 40 + 15 = 265。

所以概率是 265 / 720 = 53 / 144

ps：因為這題規模很小，只有6個元素，如果規模大的話可能就不適用了。還沒有考慮n個的情形，感覺有點複雜。

就醬 o(｀ω′ )o

提供一個錯誤的思路。

①②③④⑤⑥

假設序號相同為正確匹配

A66=120為所有排法

對①來說，有5總排法

注意！注意！注意！接下來是易錯點

對②來說，第一反應是4種排法，但是這裡忽略了一點，①本身不能匹配自己，但是②可以匹配①。

所以②的排法不是4，以此類推全錯的排法不是A55。

和排名第一思路是一樣的，但不是抄襲他的。可以可以這樣看，P1表示第一個小孩找到自己的狗。那麼P1VP2……VP6表示有小孩找到自己的狗。總可能數可以根據容斥原理求解。最後用全集減去前面的解應該就是答案了。這是離散數學高級計數部分的內容

這是一道錯排的概率問題，看你的問題你喜歡直接了當的演算法。你只需記住6個全部都錯排的話，它的可能情況有265種可能，分子為265，分母對6個孩子進行全排A66=720,概率即為265/720，希望能幫到你