组合数学第一章习题解答.pptxVIP

第一章习题1.1,从{1,2,...,50}中找一双数{a,b},使其满足：求这样的一对数的组合数。解：1分三部分，1-5，6-45，46-50[C(5,1)+C(40,1)×2+C(5,1)]/2解：2分三部分，1-5，6-45，46-50[5+6+7+8+9+C(40,1)×10+9+8+7+6+5]/2

1.3,m个男生，n个女生，排成一行，其中m,n都是正整数，若(a)男生不相邻（m≤n+1)；(b)n个女生形成一个整体；(c)男生A与女生B排在一起。解：(a)首先女生的全排列有n!个，那么第一个男生有n+1个位置可选第二个男生有n个位置，...，第m个男生有n-m+2个位置可选。男生不相邻的排列数有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)=25001.6,计算1×1!+2×2!+3×3!+n×n!解：(n+1)!-1,迭代。1.7,试证(n+1)(n+2)...(2n)能被2n除尽。解：=(2n)!!(2n-1)!!/n!=2nn!(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)C(7,1)=672+560=1232

1.8、求1040和2030的公因数数目。解：等价于求(2×5)40和(2×2×5)30的公因数数目。C(40,1)+C(40,1)C(30,1)+C(30,1)+1=40+1200+30=1271C(41,1)C(31,1)=12711.9、试证n2的整除数的数目是奇数。所有的组合数都是偶数，最后再加上1，偶数加1是奇数

1.10证明任一正整数n可惟一地表示成：先证可表示性：当n=0,1时，命题成立。假设对小于n的非负整数，命题成立。对于n,设k!≤n＜(k+1)!,即0≤n-k!＜k·k!由假设对n-k!,命题成立，设n-k!=∑ai·i!，其中ak≤k-1,n=∑ai·i!+k!，命题成立。

再证表示的唯一性：设n=∑ai·i!=∑bi·i!,

从n个不同的球中取出的r+1个，要求指定第一个球，有两种方式：A等式左边：n个不同的球，先任取出1个，再从余下的n-1个中取r个；B等式右边：n个不同球中任意取出r+1个，并指定其中任意一个为第一个。显然两种方案数相同。C组合意义：1.11证明下式，并给出组合解释

1.12试证等式：用多项式(1+x)n证明，求导

有n个不同的整数，从中取出两组来，要求第1组的最1小数大于另一组的最大数。2设取的第一组数有a个,第二组有b个,而要求第一组数中最小3数大于第二组中最大的，即只要取出一组m个数(设m=a+b),从4大到小取a个作为第一组,剩余的为第二组。此时方案数为5C(n,m)。从m个数中取第一组数共有m-1中取法。6总的方案数为7

习题：1.14六个引擎分列两排，要求引擎的点火的次序两排交错开来，试求从一特定引擎开始点火有多少种方案。01第1步从特定引擎对面的3个中取1个有C(3,1)种取法；02第2步从特定引擎一边的2个中取1个有C(2,1)种取法；03第3步从特定引擎对面的2个中取1个有C(2,1)中取法；04剩下的每边1个取法固定。所以共有C(3,1)·C(2,1)·C(2,1)=12种方案。05解：⊙⊙⊙⊙⊙06

习题：1.15试求从1到1000000的整数中，0出现的次数。解：先将1到999999的整数都看作6位数,例如2就看作是000002，这样从000000到999999。0出现了多少次呢？6×105，某一位取0，其它各位任取。0出现在最前面的次数应该从中去掉000000到999999中最左1位的0出现了105次，000000到099999中左数第2位的0出现了104次，000000到009999左数第3位的0出现了103次,000000到000999左数第4位的0出现了102次,000000到000099左数第5位的0出现了10次,000000到000009左数第6位的0出现了1次。因此不合法的0的个数为105+104+103+102+101+1=111111，不合法的应该去掉，再加整数1000000中的6个0，这样，从1到1000000的整数中0出现的次数为6×105-111111+6=488895。问题：在去掉多余的零的过程中，多减去了一部分，例如：000000这种情况在每