有八個座位,依序排列,有八個同學,學號也是 1 排到 8,現在每個人坐一個位置,但是不能坐在跟自己學號同號的座位,請問總共有多少種排列組合?
這題並不簡單,我的直覺它的解法與 8 人合作問題、寇克曼 15 個女生問题相關聯。
圓冪定理
-
圓冪定理包括相交弦定理,割線定理,切割線定理。 相交弦定理 切割線定理 資料來源:
https://zh.wikipedia.org/zh-tw/%E5%9C%86%E5%B9%82%E5%AE%9A%E7%90%86
14 小時前
當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#
不知這樣答案是否正確?
當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)),我還要想想...
這題記得高中教過,但現在自己推導還是花了好久時間,哀。
正解,畢業這麼久,還算得出來表示底子很扎實,多數人遇到困難題早就放棄,願意動腦思考的人不多,加油。
刪除