组合数学第一章习题解答ppt课件

.第一章练习，1.1，1，2，50中查找a，b对以满足：获取这种对的组合数。解决方案：1，后3部分，1-5，6-45，46-50C(5，1) C(40，1)2 C(5，1)/2，解决方案：2，1.3，m男孩，n女孩，排成一行。其中m，n都是正整数，(a)如果男人不相邻(mn 1)；(b)n名女孩构成一切。(c)男孩a和女孩b并排。解决方案：(a)第一个女孩的完整排列是n！第一个男人有n个位置，第二个男人有n个位置，第m个男人有n-m两个位置。男生的不相邻阵列数为n！(n 1)！/(n-m 1)！(b)将n个女孩视为整体。n！(m 1)！(c)男孩a和b成为整体，(m n-1)！*2，求1.5，3000到8000之间的奇怪整数数，没有相同的数字。解决方案：c (5，1) c (10，1) c (10，1) c (5，1)=2500，1.6，计算11！22！33！Nn！解决：(n 1)！-1，重复。1.7，考试证书(n 1)(n 2).(2n)可以由2n删除。解决方案：=(2n)！(2n-1)！/n！=2n！(2n-1)！/n！=2n(2n-1)！c (3，1) c (4，1) c (8，1) c (7，1) c (2，1) c (5，1) c (8，1)、1.8、1040和2030公共元素的数量。解决方案：等于(25)40和(225)30的公共元素数。C (40，1) c (40，1) c (30，1) c (30，1) 1=40 1200 30=1271 c (41，1) c (31，所有组合的数目为偶数，最后加1，偶数加1为奇数，1.10证明了任意正整数n是唯一可以表示为：第一个证明表达式：当n=0，1时，命题成立。假设对于小于n的非负整数，命题成立。对于n，请设置k！ n (k1)！0n-k！kk！根据假设n-k！设定命题，设定n-k！=aii！其中AKk-1，n=aii！k！命题成立。再证据的唯一性：设置n=aii！=bii！1.11证明了以下表达式，提供了组合意义。从n个不同的球上取下r 1，并指定第一个球。1，等式左边：n个不同的球，先去掉1，然后从剩下的n-1中拔出r。2，等式的右侧：在n个其他球中随机移除r 1，并指定其中一个为第一个。显然，两个程序的数量是相同的。1.12试验方程：用多项式(1 x)n证明，推导，1.13，有n个不同的整数，在这里取出两个组，组1的最小数必须大于其他组的最大数。第一个组为a，第二个组为b，第一个组的最小数量必须大于第二个组的最大数量。也就是说，一组m的数量(设置m=a b)作为第一组，从大组到小组a，其馀组是第二组。此时，方案数为C(n，m)。在“m数”下，选择第一组的所有数(m-1)。方案总数是，练习题：1.14将6个引擎分成2列，将引擎的点火顺序错开为2行，并试验一些从特定引擎开始点火的方案。阶段1选择特定引擎对面3个中的1个C(3，1)种；两阶段选择两个特定引擎侧中的一个C(2，1)；三级特定引擎对面的两个中，有一个提取到C(2，1)；其他每个边都用一种方法固定。因此，共有C(3，1)C(2，1)C(2，1)=12个方案。解决方案：，练习题：1.15查找从1到1000000的整数中出现0的次数。解决方案：将1到999999999之间的整数视为6位数字。例如，2被视为000002，000000到9999999。零出现了多少次？6105，一位0，另一位0。必须删除0出现在开头的次数，000000至999999最左边的1位0为105，000000至099999左边的2位0为104，00000至0099999左边的3位0为103，000000至009999因此，无效的0的数量为105 104 103 102 101 1 1=11111111，删除无效的，添加6个整数100000到0，从而在1到1000000之间的整数中出现0的次数为6105-111111 6=48895。问题：在删除不必要的零的过程中，进一步减去某些部分(例如，每次减少000000时发生)。，没有一个空箱子把1.16，n个完全相同的球放在r个有符号的箱子里。有几个方案？这相当于将r个球放入每个长方体，然后将n-r放入r个不同的长方体，从而填充空长方体。C (r n-r-1，n-r)=c (n-1，n-r)=c (n-1，r-1)，1.18，8个箱子排成一行，有标记的5个球放在箱子里，每个箱子最多放1个球，要求空箱子不相邻，问能排列多少5！654，1.19，n m位是由m个0，n个1组成的符号字符串。其中nm 1，2个1相邻符号字符串的个数不存在吗？(m 1)*m*.*(m-n 2)/n！=C(m 1，n)，1.20，a单位有10名男同志，4名女同志，b单位有15名男同志，10名女同志，他们组成了由7人组成的代表团，其中a单位有4人，脸，7人中有5名男同志，有几个方案按甲单位分类：c (10，4) c (15，1) c (10，2) c (10，3) c (4，1) c (15，2) c()，1.20，甲单位有男同志10人，女同志4人，乙单位有男同志15人，女同志10人，其中7人隶属，男同志隶属5人一人，男同志隶属7人，男同志隶属7人，按A单位分类：c (10，4) c (15) (a) c (5，2) c (8，3)，(b) c (5，2) c (7，3)，(c) c (5，2) c ，1.23，s=1，2，n 1，n2，1，z可选2，3，4，n 1，相应的x，y都是1，2，3，n被选中后，可以通过除以，2，x和y来处理a，在相同的情况下，n 1到2，大的为z，小的为x和y，B，不等的情况下，n 1中的3个，z的最大顺序为x和y，数组为2，结果为2。获取以，1.24，(a) x，y平面中的a为顶点的长方形的数目。(b)查找x，y平面中使用a作为顶点的正方形数。1.25，平面上15个点p1，p2，p15。其中p1、p2、p5共线，三点不共线。查找通过1，至少15个点中两点的直线数。求2，15个点中3个点组成的三角形的个数。1，c (10，2) (10，1)C(5，1) 12，C(10，3) c (10，2) c (5，1) c (10，10)，1.26s=1，2，获取、1000、a、b-s、ab=0mod5、偶数的a，b数。解决方案：偶数有500个，200个5个倍数，100个10个倍数。单独5的倍数不是10的倍数为100，偶数减去10的倍数为400，c (100，1) c (400，1) c (100，1) (900，1)，1.276名男宾和5名女宾女宾不相邻的方案有多少？所有女宾在一起的方案有几个？莱文a和两位男性客人相邻几个不同的节目？5！*6*5*4*3*26！5！P(6，2)8！1.28k和n都是正整数，kn名来宾围着k表坐着测试方案数。使用1.29 n个对象中的r作为圆阵列来查找模式数。C(n，r)(r-1)！1.30测试以下等式，1.31表示与任意r个相邻数的连接(n 1)(n 2).(n r)=(n r)！/n！被r打中了！清除干净。n r个元素中的r个组合数，C(n r，r)=(n r)！/n！r！1.32要求在a，b，c，d，e，f，x，x，x，y，y的数组中，y必须夹在两个x之间，然后问这样的数组是多少。7！将Xyxyx视为一个元素。据悉，1.33将r，n，k都是正整数，rnk，r个不可分辨的球放入n个有符号的方框中。如果一个箱子里至少有k个球，有多少个方案？C(n r-nk-1，r-nk)，1.34在r、s、t、u、v、w、x、y、z的对齐中查找y在x和z中间的对齐数。解决方法：2*7！1.35凸面10角的3条对角线不共线，尝试几个此凸面10角对角线相交的点(交点表示内部交点，顶点和外部交点除外)。4点的两条对角线有交点，C(10，4)，1.36是测试整数是其他整数的平方的必要条件是，减去所有这些数字是全部(奇数)数。解决方案：如果可以用一个数字作为另一个整数的平方。m的数量为：1.37表示以下组合语义，路径问题，1.38提供了以下组合语义：解决方案：C(n 1，r 1)是n 1元素a1，a2，an 1到r 1的组合方案数。左：如果必须选择an 1，则方案数为C(n，r)。如果不选择an 1，必须选择an，则方案数为C(n-1，r)。an 1、an、如果未选择ar 2，则方案数为C(r，r)。所有这些可能性加起来就是方案总数。1.39证明，证词：组合意义，右：m球，取其中n个，放入两个盒子，对n个球体中的每一个，用两种方法求出可能的方案数。左：I项的含义是，将I放在一个框中，将n-i放在另一个框中，将所有方案数相加，就应该等于右。1.40从n个人中选择r个来创建圆，并询问有多少不同的数组。解决方案：C(n，r)(r-1)！1.43对于给定正整数n，如果k满足以下表达式，则证明C(n，k)是大值：卡：比较C(n，k)和C(n，k-1)。要比较C (n，k)/c (n，k-1)=(n-k 1)/K. C(n，k) C(n，k-1)，请执行以下操作C(n，k)/C(n，k-1)=(k 1)/(n-k)。要创建C (n，k)c(n，k 1)，必须是k s (n-1)/2，因此必须是(n-1)/2k(n 1)/，1.44(a)通过组合证明以下表达式为整数：(a)将2n个不同的球分别放在n个不同的箱子里。此程序的数量必须是整数。排列2n个球后，情景数为(2n)！即可从workspace页面中移除物件。将两个球放在同一个箱子里，不管顺序如何，要清除全部排序数的重复计算次数，n个箱子内的阵列共重复了2n次。将2n个不同的球放在n个不同的方块中，每个方块有2个场景数(2n)！/如果有2n个不同的球，再放n个不同的箱子，同样(3n)！/(3！)n是整数。1.44(b)通过组合证明以下表达式为整数：n个不同的球，n个相同的框中各放n个框以查找方案数，方案数必须是整数。按前面的(a)方法(N2)！/(n！)n是整数。另外，n个箱子是相同的，所以放入另一个箱子没有区别。必须将n个长方体排列为n！去除。因此得到(N2)！/(n！)n 1是整数。1.45(a) 2n个球体中的n个相同。选择此2n个球体中的n个方案数。(b) 3n 1个球中的n个相同。从这些3n 1球体中选择n个方案的数量。c (n，0) c (n，1) c (n，2).c (n，n)=2n，c (2n，0) c (2n，1) c (2n，2).c (2n，n)相当于从n个不同的小球体中分别移除m个小球(0mn)，然后从n个相同的小球体中移除n-m个小球。联合方案：C(n，0) C(n，1) C(n，n)=2n种。(b)从2n 1个不同的球中各移除m个小球(0mn)，相当于从n个相同的球中移除n-m个小球。总方案：c (2n 1，0) c (2n 1，1).c (2n 1，n)种。1.46在字符0，1，2生成的长度为n的字符串中证明。(a)0是偶数多次出现的字符串(3n 1)/2，卡：(a)归纳法：n=1时，0多次出现的字符串(30 1)/2=2(即1，2)就成立了。假设N=k时，出现几次0的字符串为(3k 1)/2。总字符串有3k种。零中出现奇数的字符串是(3k-1)/2种类。当N=k 1时，出现几次0的字符串由两部分组成。n=k时，0多次添加非零1，总计2(3k 1)/2，0一次添加零，奇数(3k1)/2。共2个(3k1)/2个(3k-1)/2=(3k 1)/2个，证词完成。(b)方程左边的第m项是从0发生m次的字符串数，其和是从0发生几次的字符串数，右边的(a)是从0发生几次的字符串数，两边明显相同。1.475台教学机器m名学生使用，1台和2台的人员相同，有多少分配方案？解法：如果使用一级机器的学生有n个，则使用二级机器的学生也有n个，m个学生中使用二级机器的学生有2n个，剩下的学生可以任意使用机器的组合数为c (m，2n) c (2n) 3 (m-2n)。因此，在1.49 1到n的自然数中，选择不同且不相邻的k数的选项有多少？C(n-k 1，k)，1.50(a) 5个0，4个1组成的字符串中，有多少个字符串01或10的总数为4？(b)在由m个0，n个1组成的字符串中，01或10的总数为k的字符串有多少个？(a)，5个0先排列成一列。00000，1如果在两