[理工] 离散 排容

楼主: clonsey1314 (Clonsey)   2017-12-10 20:30:04
1. (台大工科)
26个不同英文字母排列, 有几种排列是没有"USA"和"SAP" pattern的?
答案给: 26! - 2 x 24! + 22!
我写: 26! - 2 x 24! + 23!
想法是, 如果同时有"USA"和"SAP", 表示有"USAP", 所以同时拥有此2个pattern的排列数共26-4+1=23种
而答案是把2个pattern分开, 共26-6+2=22个不同物排列
请问是哪个正确?
2. (102中山电机)
Find the number of permutation of the letter x, x, y, y, z, z so that no x appears
in the first and second positions, no y appears in the third position, and no z
appears in the fifth and sixth positions.
答案:
1/(2!2!2!) x (6! - 10 x 5! + 36 x 4! - 56 x 3! + 36x 2! - 8 x 1!)
括号中是把6个字母当相异物的排列种数, 想问为什么可以直接先求完禁位排列数, 再除以相同物的排列数?
例如当第二项"10 x 5!", 当有一个在禁位, 这样就只剩下2种相同物, 为何还要多除一个2! ?
作者: TampaBayRays (光芒今年拿冠军)   2017-12-10 20:38:00
第一题我的想法跟你一样
作者: winiel559 (大汉天威)   2017-12-10 21:09:00
第一题答案给错了吧
作者: TMDTMD2487 (ㄚ冰)   2017-12-10 21:42:00
他是直接用棋盘多项式干下去吧而且你用排容去算第二项答案是5*5!/(2!2!)这题我自己做的时候还不是很会用rook polynomial所以我是排容硬干的 XD

Links booklink

Contact Us: admin [ a t ] ucptt.com