2015年1月28日 星期三

訓練數學感 50 ─ 不對號入座

http://4rdp.blogspot.com/2015/01/50.html?m=0

有八個座位,依序排列,有八個同學,學號也是 1 排到 8,現在每個人坐一個位置,但是不能坐在跟自己學號同號的座位,請問總共有多少種排列組合?



這題並不簡單,我的直覺它的解法與 8 人合作問題寇克曼 15 個女生問题相關聯。

3 則留言:

  1. 當i=2時,(2C2)*2!-(2C1)*1!+(2C2)=1;
    當i=3時,(3C3)*3!-(3C1)*2!+(3C2)*1!-(3C3)=2;
    當i=4時,(4C4)*4!-(4C1)*3!+(4C2)*2!-(4C3)*1!+(4C4)=9;
    當i=5時,(5C5)*5!-(5C1)*4!+(5C2)*3!-(5C3)*2!+(5C4)*1!-(5C5)=44;
    ...
    當i=n時,sigma(nCi)*[((-1)^i)]*[(n-i)!]=sigma[((-1)^i)]*(nP(n-i))。

    故當i=8時,8P8-8P7+8P6-8P5+8P4-8P3+8P2-8P1+8P0
    =8P5(3-1)+8P3(5-1)+8P1(7-1)+8P0
    =13440+1344+48+1=14833#

    不知這樣答案是否正確?

    回覆刪除
    回覆
    1. 當i=n時,sigma(nCi)*[((-1)^i)]*[(n-i)!],i從0至n
      我的解釋是,
      任選1個人(nC1)坐到自己號碼,其他人隨便坐(n-1)!的排列是情形1;
      任選2個人(nC2)坐到自己號碼,其他人隨便坐(n-2)!的排列是情形2;
      任選3個人(nC3)坐到自己號碼,其他人隨便坐(n-3)!的排列是情形3;
      ...
      任選n個人(nCn)坐到自己號碼,其他人隨便坐(n-n)!的排列是情形n。

      情形1會重複算了2(2C1)次情形2、3(3C1)次情形3、4(4C1)次情形4,...
      情形2會重複算了3(3C2)次情形3、6(4C2)次情形4、10(5C2)次情形5,...
      情形3會重複算了4(4C3)次情形4、10(5C3)次情形5、20(6C3)次情形6,...

      所以

      所有排列方式(n!)-情形1+情形2-情形3+情形4-...
      即是所有排列方式扣除(僅有1人坐自己號碼+僅有2人坐自己號碼+僅有3人坐自己號碼+....)

      至於第2種解釋sigma[((-1)^i)]*(nP(n-i)),我還要想想...
      這題記得高中教過,但現在自己推導還是花了好久時間,哀。

      刪除
    2. 正解,畢業這麼久,還算得出來表示底子很扎實,多數人遇到困難題早就放棄,願意動腦思考的人不多,加油。

      刪除