Question

假如有五個數(shù)字分別要放置在編號為12345的位置上（設(shè)計成一組一組的序列），如果序列在每個位置都不重疊相同數(shù)字的話能排5組，如果不管重疊多少個數(shù)字的話（全部排列組合）應(yīng)該是120組，現(xiàn)在的問題是如果讓它重疊一個、兩個、三個數(shù)字分別能排多少組？用公式怎么算？

Answer 1

考點：排列、組合及簡單計數(shù)問題

專題：排列組合

分析：先根據(jù)題意求出D_n=（n-1）（D_n-2+D_n-1），特殊地，D₁=0，D₂=1，再分別求出重疊一個、兩個、三個數(shù)字分別能排的組數(shù)，得到公式，問題得以解決．

解答： 解：當(dāng)n個編號元素放在n個編號位置，元素編號與位置編號各不對應(yīng)的方法數(shù)用D_n表示，那么D_n-1就表示n-1個編號元素放在n-1個編號位置，各不對應(yīng)的方法數(shù)，其它類推．第一步，把第n個元素放在一個位置，比如位置k，一共有n-1種方法；
第二步，放編號為k的元素，這時有兩種情況：（1）把它放到位置n，那么，對于剩下的n-1個元素，由于第k個元素放到了位置n，剩下n-2個元素就有D_n-2種方法；（2）第k個元素不把它放到位置n，這時，對于這n-1個元素，有D_n-1方法；
綜上得到，
D_n=（n-1）（D_n-2+D_n-1），
特殊地，D₁=0，D₂=1，
所以，D₃=2×（0+1）=2，
D₄=3×（1+2）=9，
重疊三個：有C₅³×D₂=10×1=10組，
重疊二個：有C₅²×D₃=10×2=20組，
重疊一個：（即1放在1號位，或2放在2號位，…，且只有一個數(shù)字對號），有C₅¹×D₄=5×9=45組，
公式為C_n^m×D_n-m（其中n為元素的個數(shù)，m為重疊的個數(shù)）

點評：本題考查了排列組合的問題，關(guān)鍵是求出元素編號與位置編號各不對應(yīng)的方法數(shù)D_n，屬于中檔題．