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