Question

將編號為1，2，3，4，5的五個小球放入編號為1，2，3，4，5

的五個盒子中，每個盒子只放入一個，

① 一共有多少種不同的放法？

② 若編號為1的球恰好放在了1號盒子中，共有多少種不同的放法？

③ 若至少有一個球放入了同號的盒子中(即對號放入)，共有多少種不同的放法？

Answer 1

① 將第一個球先放入，有5種不同的的方法，再放第二個球，這時以4種不同的放法，依此類推，放入第三、四、五個球，分別有3、2、1種放法，所以總共有5×4×3×2×1＝120種不同的放法。

② 將1號球放在1號盒子中，其余的四個球隨意放，它們依次有4、3、2、1種不同的放法，這樣共有4×3×2×1＝24種不同的放法。

③ (解法一)

在這120種放法中，排除掉全部不對號的放法，剩下的就是至少有一個球放入了同號的盒子中的放法種數(shù)。

為研究全部不對號的放法種數(shù)的計算法，設(shè)A₁為只有一個球放入一個盒子，且不對號的放法種數(shù)，顯然A₁＝0，A₂為只有二個球放入二個盒子，且不對號的放法種數(shù)，∴ A₂＝1，A₃為只有三個球放入三個盒子，且都不對號的放法種數(shù)，A₃＝2，……，A _n為有n個球放入n個盒子，且都不對號的放法種數(shù)。

下面我們研究A _n+1的計算方法，考慮它與A _n及A _n－1的關(guān)系，

如果現(xiàn)在有 n個球已經(jīng)按全部不對號的方法放好，種數(shù)為A _n。取其中的任意一種，將第n＋1個球和第n＋1個盒子拿來，將前面n個盒子中的任一盒子(如第m個盒子)中的球(肯定不是編號為m的球)放入第n＋1個盒子，將第n＋1個球放入剛才空出來的盒子，這樣的放法都是合理的。共有n A _n種不同的放法。

但是，在剛才的操作中，忽略了編號為m的球放入第n＋1個盒子中的情況，即還有這樣一種情況，編號為m的球放入第n＋1個盒子中，且編號為n＋1的球放入第m個盒子中，其余的n－1個球也都不對號。于是又有了nA _n－1種情況是合理的。

綜上所述得A _n＋1＝nA _n＋nA _n－1＝n(A _n＋A _n－1).

由A₁=0, A₂=1, 得A₃=2(1＋0)=2, A₄＝3(2＋1)=9, A₅＝4(9＋2)=44.

所以至少有一個球放入了同號的盒子中的放法種數(shù)為全部放法的種數(shù)減去五個球都不對號的放法種數(shù)，即120－44＝76種。

(解法二)

從五個球中選定一個球，有5種選法，將它放入同號的盒子中 (如將1號球放入1號盒子)，其余的四個球隨意放，有24種放法，這樣共有5×24＝120種放法。

但這些放法中有許多種放法是重復(fù)的，如將兩個球放入同號的盒子中(例如1號球和2號球分別放入1號盒子、2號盒子中)的放法就計算了兩次，這樣從總數(shù)中應(yīng)減去兩個球放入同號的盒子中的情況，得120－＝120－60(種)。

很明顯，這樣的計算中，又使得將三個球放入同號的盒子中(例如1號球、2號球和3號球分別放入1號盒子、2號盒子和3號盒子中)的放法少計算了一次，于是前面的式子中又要加入＝20種，

再計算四個球、五個球放入同號盒子的情況，于是再減去四個球放入同號盒子中的情況，最后加上五個球放入同號中的情況。

整個式子為120－＋－＋＝120－60＋20－5＋1＝76(種)。