将编号为1，2，3，4，5的五个小球放入编号为1，2，3，4，5的五个盒子中，每个盒子只放入一个，①一共有多

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种放法中，排除掉全部不对号的放法，剩下的就是至少有一个球放入了同号的盒子中的放法种数．
为研究全部不对号的放法种数的计算法，设A₁为只有一个球放入一个盒子，且不对号的放法种数，显然A₁=0，A₂为只有二个球放入二个盒子，且不对号的放法种数，∴A₂=1，A₃为只有三个球放入三个盒子，且都不对号的放法种数，A₃=2，A_n为有n个球放入n个盒子，且都不对号的放法种数．
下面我们研究A_n+1的计算方法，考虑它与A_n及A_n-1的关系，
如果现在有n个球已经按全部不对号的方法放好，种数为A_n．取其中的任意一种，将第n+1个球和第n+1个盒子拿来，将前面n个盒子中的任一盒子（如第m个盒子）中的球（肯定不是编号为m的球）放入第n+1个盒子，将第n+1个球放入刚才空出来的盒子，这样的放法都是合理的．共有nA_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．
所以至少有一个球放入了同号的盒子中的放法种数为全部放法的种数减去五个球都不对号的放法种数，即120-44=76种．
（解法二）
从五个球中选定一个球，有5种选法，将它放入同号的盒子中（如将1号球放入1号盒子），其余的四个球随意放，有24种放法，这样共有5×24=120种放法．
但这些放法中有许多种放法是重复的，如将两个球放入同号的盒子中（例如1号球和2号球分别放入1号盒子、2号盒子中）的放法就计算了两次，这样从总数中应减去两个球放入同号的盒子中的情况，得120-C₅²P₃³=120-60（种）．
很明显，这样的计算中，又使得将三个球放入同号的盒子中（例如1号球、2号球和3号球分别放入1号盒子、2号盒子和3号盒子中）的放法少计算了一次，于是前面的式子中又要加入C₅³P₂²=20种，
再计算四个球、五个球放入同号盒子的情况，于是再减去四个球放入同号盒子中的情况C₅⁴P₁¹，最后加上五个球放入同号中的情况C₅⁵．
整个式子为120-C₅²P₃³+C₅³P₂²-C₅⁴P₁¹+C₅⁵=120-60+20-5+1=76（种）．