大家好
這題是97年元智資工的題目，
相較於書上的答案，我是有想到另一個答案，
麻煩大家幫忙看一下，謝謝。
若排列後恰有k個數在自然位置上
則相當於剩下n-k個數排列後不在自然位置，也就是剩下n-k個數在做亂序， for 0<=k<=n 。
若恰有0個數在自然位置上，則剩下有n-0個數同時在做亂序 ，方法數為 Dn-0
若恰有1個數在自然位置上，則剩下有n-1個數同時在做亂序 ，方法數為 1*Dn-1
若恰有2個數在自然位置上，則剩下有n-2個數同時在做亂序 ，方法數為 2*Dn-2
...
若恰有k個數在自然位置上，則剩下有n-k個數同時在做亂序 ，方法數為 k*Dn-k (k = 0,1, .. ,n)
因此總共排列數為 : Dn-0 + 1*Dn-1 + 2*Dn-2 + 3*Dn-3 + ... + k*Dn-k = 西格瑪(i=0到k) i*Dn-i
2 則留言:
同學你列的式子似乎有點太複雜了, 因為這題題目裡描述的 k 是一個固定的數, 不是變數, 他並不是在討論加總恰 1 個, 恰 2 可, ..., 恰 k 個的情形, 還有就是, 假設我們已經決定哪 k 個數要在自然位置上了, 那麼針對那些在自然位置數的數, 就不需要再去討論他們的排列有幾種 (因為就只有一種), 所以只要討論要選 k 個數有幾種選法即可, 所以這題答案還是 c(n,k) * D_(n-k)
謝謝，
日後會定加思索，了解題意。
張貼留言