Question

20．7个人到7个地方去旅游，一人一个地方，甲不去A地，乙不去B地，丙不去C地，丁不去D地，共有多少种旅游方案？

Answer 1

分析 用间接法，先求不满足要求的方案数，分四类，（1）若甲、乙、丙、丁4人分别去A，B，C，D，而其余的人不限，（2）若甲、乙、丙、丁中有3人去各自不能去的地方旅游，（3）若甲、乙、丙、丁4人中有2人去各自不能去的地方旅游，（4）若甲、乙、丙、丁4人中只有1人去了自己不能去的地方旅游，根据分类计数原理，问题得以解决．

解答 解：用间接法，先求不满足要求的方案数．
（1）若甲、乙、丙、丁4人分别去A，B，C，D，而其余的人不限，选法有${A}_{3}^{3}$=6种．
（2）若甲、乙、丙、丁中有3人去各自不能去的地方旅游，有${C}_{4}^{3}$ 种，而4人中剩下1人去的地方是${C}_{3}^{1}$ 种，其余的人有${A}_{3}^{3}$ 种，所以共有=72${C}_{4}^{3}•{C}_{3}^{1}•{A}_{3}^{3}$=72种．                                                                            
（3）若甲、乙、丙、丁4人中有2人去各自不能去的地方旅游，有${C}_{4}^{2}$ 种，余下的5个人分赴5个不同的地方的方案有${A}_{5}^{5}$ 种，但是其中又包括了有限制条件的四人中的两人（不妨设甲、乙两人）同时去各自不能去的地方共${A}_{3}^{3}$ 种，和这两人中有一人去了自己不能去的地方有2${A}_{3}^{1}•{A}_{3}^{3}$ 种，所以共有${C}_{4}^{2}（{A}_{5}^{5}-{A}_{3}^{3}-2{A}_{3}^{1}•{A}_{3}^{3}）$=468种．
（4）若甲、乙、丙、丁4人中只有1人去了自己不能去的地方旅游，有${C}_{4}^{1}$ 种方案，而余下的六个人的旅游方案仍与（3）想法一致，共有
${C}_{4}^{1}$[${A}_{6}^{6}$-A${\;}_{3}^{3}$-${C}_{3}^{2}$（${A}_{4}^{4}$-${A}_{3}^{3}$）-${C}_{3}^{1}$（${A}_{5}^{5}$-${A}_{3}^{3}$-2${C}_{3}^{1}$${A}_{3}^{3}$ ）]=1704种．
所以满足以上情况的不同旅游方案共有${A}_{7}^{7}$-（6+72+468+1704）=2790种

点评 本题考查了分步和分类计数原理，以及利用间接关键是对不满足要求的方案数分四类，属于难题．