清华大学：《组合数学》课程教学资源（PPT课件讲稿）第一章 习题

第一章习题 1证任一正整数n可唯一地表成如下形式: n=>a0≤a≤i=1 解 2证nC(n-1)=(r+1)C(n,r+1)并给出组合 意义。解 3证∑kC(nk)=n2"。解 4.有n个不同的整数,从中取出两组来, 要求第一组数里的最小数大于第二组的 最大数。问有多少种方案?解

第一章习题 • 1.证任一正整数n可唯一地表成如下形式： n=∑aii!,0≤ai≤i,i＝1,2,…。 解 • 2.证 nC(n-1,r) = (r+1)C(n,r+1).并给出组合 意义。解 • 3.证∑kC(n,k)=n2 。解 • 4.有n个不同的整数，从中取出两组来， 要求第一组数里的最小数大于第二组的 最大数。问有多少种方案？解 i≥1 i≥1 k n-1

5六个引擎分列两排,要求引擎的点火的 次序两排交错开来,试求从一特定引擎 开始点火有多少种方案。解 6.试求从1到100000的整数中,0出现了 多少次?解 7n个男n个女排成一男女相间的队伍,试 问有多少种不同的方案?若围成一圆桌 坐下,又有多少种不同的方案?解 ·8n个完全一样的球,放到r个有标志的盒 子,n2r,要求无一空盒,试证其方案数为 n r-1

• 5.六个引擎分列两排，要求引擎的点火的 次序两排交错开来，试求从一特定引擎 开始点火有多少种方案。解 • 6.试求从1到1000000的整数中，0出现了 多少次？解 • 7.n个男n个女排成一男女相间的队伍，试 问有多少种不同的方案？若围成一圆桌 坐下，又有多少种不同的方案？解 • 8.n个完全一样的球，放到r个有标志的盒 子,n≥r,要求无一空盒，试证其方案数为 ( ).解 n-1 r-1

9设n=pp2p,p、p2、…、p是1个不同 的素数,试求能整除尽数n的正整数数目 10试求n个完全一样的骰子掷出多少种不 同的方案?解 ·11凸10边形的任意三个对角线不共点, 试求这凸10边形的对角线交于多少个点? 又把所有对角线分割成多少段?艉 12试证一整数是另一个整数的平方的必 要条件是除尽它的数目为奇数。解

• 9.设 n=p1 p2 …pl ,p1、p2、…、pl是l个不同 的素数，试求能整除尽数n的正整数数目. 解 • 10.试求n个完全一样的骰子掷出多少种不 同的方案？解 • 11.凸10边形的任意三个对角线不共点， 试求这凸10边形的对角线交于多少个点？ 又把所有对角线分割成多少段？解 • 12.试证一整数是另一个整数的平方的必 要条件是除尽它的数目为奇数。解 a1 a2 al

13统计力学需要计算r个质点放到n个盒 子里去,并服从下列假定之一,问有多少 种不同的图象。假设盒子始终是不同的。 (a) Maxwell-Boltemann假定:r个质点是不同 的,任何盒子可以放任意数个 (b)Bose- einstein假定:r个质点完全相同, 每一个盒子可以放任意数个 (c) fermi-Dirac假定:r个质点都完全相同, 每盒不超过一个解

• 13.统计力学需要计算r个质点放到n个盒 子里去,并服从下列假定之一，问有多少 种不同的图象。假设盒子始终是不同的。 (a)Maxwell-Boltzmann假定：r个质点是不同 的，任何盒子可以放任意数个. (b)Bose-Einstein假定：r个质点完全相同， 每一个盒子可以放任意数个. • (c)Fermi-Dirac假定：r个质点都完全相同， 每盒不超过一个.解

14从26个英文字母中取出6个字母组成 字,若其中有2或3个母音,问分别可构 成多少个字(不允许重复)?解 15给出()()+(m)(1)(m2)(2)+ (0D)(m)=(m)的组合意义。解 16给出()(r1)+()++(-(叶)的组 合意义。解

• 14.从26个英文字母中取出6个字母组成一 字，若其中有2或3个母音，问分别可构 成多少个字(不允许重复)？解 • 15.给出( )( )+( )( )+( )( )+…+ ( )( )= ( )的组合意义。解 • 16.给出( )+( )+( )+…+( )=( )的组 合意义。解 n m r 0 n-1 m-1 n-2 m-2 n-m 0 n+r+1 m r+1 1 r+2 2 r+m m r r r+1 r r+2 r n r n+1 r+1

17证明:艉 )()(m)(2)(n2)++()(m)2(a 18从n个人中选r个围成一圆圈,问有多少种 不同的方案?解 19分别写出按照字典序由给定排列计算其 对应序号的算法及由给定序号计算其对应排 列的算法。(解略) 20(a)按照第19题的要求,写出邻位对换法 (排列的生成算法之二)的相应算法。 b)写出按照邻位对换法由给定排列生成 其下一个排列的算法。(解略)

• 17.证明：解 ( )( )+( )( )+( )( )+…+( )( )=2 ( ) • 18.从n个人中选r个围成一圆圈，问有多少种 不同的方案？解 • 19.分别写出按照字典序由给定排列计算其 对应序号的算法及由给定序号计算其对应排 列的算法。(解略) • 20.(a)按照第19题的要求，写出邻位对换法 (排列的生成算法之二)的相应算法。 (b)写出按照邻位对换法由给定排列生成 其下一个排列的算法。(解略) m 0 m n m 1 m 2 m n m n m-1 n-1 m-2 n-2 m-n 0 n

21.对于给定的正整数n,证明当 n-1n+1 若n是奇数 若n是偶数 时,C(nk)是最大值。解 22(a)用组合方法证明2和2y都是整数 (b)证明(mm是整数,解 23.(a)在2n个球中,有n个相同,求从这2n个 球中选取n个的方案数 (b)在3n+1个球中,有n个相同,求从 这3n+1个球中选取n个的方案数。解

• 21.对于给定的正整数n,证明当 • 22.(a)用组合方法证明 和 都是整数. (b)证明 是整数. 解 • 23.(a)在2n个球中,有n个相同,求从这2n个 球中选取n个的方案数。 (b)在3n+1个球中，有n个相同，求从 这3n+1个球中选取n个的方案数。解 k= n-1 2 n 2 , n+1 2 时，C(n,k)是最大值。解 若n是奇数 若n是偶数 (2n)! (3n)! 2 2 · 3 n n n (n )! (n!) n+1 2

24证明在由字母表{0.,1,2}生成的长度为n 的字符串中 (a)0出现偶数次的字符串有31个 (b)(0)2+(2)2++()2=3 其中q=22」 解 25.5台教学机器m个学生使用,使用第1 台和第2台的人数相等,有多少种分配方 案?解

• 24.证明在由字母表{0,1,2}生成的长度为n 的字符串中. (a)0出现偶数次的字符串有——个； (b) ( )2 +( )2 +…+( )2 = —— ， 其中q=2 — . 解 • 25. 5台教学机器m个学生使用，使用第1 台和第2台的人数相等，有多少种分配方 案？解 n 0 n 2 n q 3 +1 2 3 +1 2 n n-1 n-q n n n 2

26在由n个0及n个1构成的字符串中,任 意前k个字符中,0的个数不少于1的个数 的字符串有多少?解 27在1到n的自然数中选取不同且互不相 邪的k个数,有多少种选取方案?解 28(a)在5个0,4个1组成的字符串中,出 现01或10的总次数为4的,有多少个? (b)在m个0,n个1组成的字符串中,出 现01或10的总次数为k的,有多少个?解

• 26.在由n个0及n个1构成的字符串中，任 意前k个字符中，0的个数不少于1的个数 的字符串有多少？解 • 27.在1到n的自然数中选取不同且互不相 邻的k个数，有多少种选取方案？解 • 28.(a)在5个0，4个1组成的字符串中，出 现01或10的总次数为4的，有多少个？ (b)在m个0，n个1组成的字符串中,出 现01或10的总次数为k的，有多少个？解

习题解答 1证:对n用归纳法。题 先证可表示性: n=0,1时,命题成立 假设对小于n的非负整数,命题成立。 对于n,设k!sn<(k+1),即0≤n-k!<kk! 由假设对n-k!命题成立, 设nkai,其中ask-1, n∑ai!+k!,命题成立

习题解答 • 1.证：对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!，命题成立。 i=1 k i=1 k