排列组合问题拟编.

1、排列组合问题拟编容斥原理：1. 将八张卡片 AABBCDEF排成一排，相同字母的卡片不许相邻的排法有多少种？映射与配对：2. 有 m 个白球排成一排，要从中取出 n 个染成黑色，若每两个黑球均不能相邻，问有多少 种不同的涂法？3. 把正整数 n 3 写成三个正整数之和，有多少种写法？钱币问题：4. 一元 4张, 一角 3张,五分 6 张,一分 4张,问可以组成多少种不同币值 0元不计？ 解法一： 从最后币值圆角分考虑： （这种解法较好，可以较简捷的对更多不同面值问题作出 解答）解法二：从每种面值考虑：逆向问题：有足够多的五角、二角、一角、五分、二分、一分纸币要凑齐一元，问有多少种方法？寻求递推

2、关系：5. （欧拉全错位排列问题）将自然数1到n从左至右排成一排，求所有 i 均不在第 i 位的排列数 an .解法一： 先考虑递归关系 . n 充分大时，分为两类：其一， n 在第 i n 位且 i 在第 n 位；其 二，n在第i位而i既不在第 n位也不在第 i位.第一类先从 1到n 1中挑出某个 i放在第 n位 且将i在第 n位，再将剩下的 n 2个数全错位排列，其排列数为 Cn11an 2 .第二先将 1到n 1 全错位排列，再从中挑出某个与 n互易位置，其排列数为 Cn1 1an 1. 故而有递归关系：an n 1 an 1 an 2 ， n 2. 显然，初始值 a1 0 ， a2 1

3、. 递归关系可得an nan 1an 1 n 1an 21 a2 2a11 ，继而an 11nn! n 1!n!a1!1k 2 k1!n 1k，故而 an n! k0k!n 1k ，n 3,4, k 0 k!经计算， n 1,2 也符合该通项公式，故ann!k01kk!解法二： 还有另外一种方法处理递归式，即：ann!an 1 an 2n n 2 !ann!an 2n 2!an 1an 2an 1n 1! n n 2! n n 2! n 1! n n 2! n!an 1an 2n n 1! n 2!1n 2a2 a11n2 1 ，也可得到答案 .n n 1 3 2! 1! n!解法三： 本问题

4、用容斥原理也能得到一个简单的解法，而无须涉及递归关系式6. (环状染色问题)把一个圆分为 n( 3)个扇形，用 k( 3) 种颜料给这些扇形染色，每个 扇形用一种颜色，要求相邻的区域用不同的颜色，问不同的染色方案共有多少种？ 解法一： k k 1an an 1.解法二： ank 2 an 1k 1 an 2 .变式题： 用 4 种不同颜色给五角星五个顶点染色， 每个顶点染一色， 有的颜色也可以不 用，要求每条线段上的两个顶点染不同的颜色，则不同的染色方案有 种 .染色问题：7.几何中的问题：7. 在正方体的 8 的顶点， 12 条棱的中点， 6 个面的中点及正方体的中心共 27 个点中，共线 的三点组的个数是多少？可重组合问题：8. 求从 n个互异元素中允许重复的取出 k 个的不同组合数？变式题： 方程 x1 x2xn k(n,k N ) 自然数解一共有 种.初等数论中的问题：9. 从 0到 9这10个数字中选出 3个，使其和为不小于 10 的偶数的取法共有多少种？传球问题：A开始传出(算第10. 五个人站成一圈传球，每人只能将球传给左右相邻的一人，现在球从 一次)，10 次后，球回到 A 手中的不同传球方法有多少种？变式题： 一只青蛙从一个正六边形 ABCDEF的顶点 A开始每一次只能跳到与它