习题2与答案.doc

习 题 二 第 1 页 共 14 页 习题二 母函数及其应用 习题二 母函数及其应用 1 求下列数列的母函数 0 1 2 n 1 1 n a n 2 5 n 3 1 n n 4 2 n n 解 1 母函数为 00 1 1 nnna nn aa G xxxx nn 2 母函数为 22 000 554 5 5 1 1 1 nnn nnn xx G xnxnxx xxx 方法二 方法二 000 1 0 22 5 14 414 1 111 1454 1 1 1 nnn nnn n n G xnxnxx x xxx x xx x 3 母函数为 2 323 000 222 1 1 2 1 1 1 nnn nnn xxx G xn nxn nxnx xxx 方法二 方法二 22 02 222 00 2 222 0 2 3 1 001 21 1 2 1 nn nn nn nn n n G xn nxxn nx xnnxxx x xxx x x x 4 母函数为 习 题 二 第 2 页 共 14 页 2 323 000 23 2 1 1 1 1 nnn nnn xxxx G xn nxn nxnx xxx 方法二 方法二 0000 2121 0000 2 32 2 3 2 121 11 11 1211 1111 11 3 1 nnnn nnnn nnnn nnnn G xn nxnnxnxx xxxx xx xx xxxx xx xx x 2 证明序列的母函数为 1 2 C n n C nn C nn 1 1 1 nx 证明 因为 1 1 1 C nk nC nknC nkn 令 23 0 1 2 3 k n k G xC nk n xC n nC nn xC nn xC nn x 则 23 1 2 n x G xC n n xC nn xC nn x A 23 1 1 1 1 1 1 2 1 n GxC nnC n nxC nnxC nnx 而 1 1 0 nn x G xGx 故 1202 111 1 11 nnnn GxGxGxGx x xx 又 23 0 23 0 0 1 0 2 0 3 0 1 1 1 G xCCxCxCx xxx x 所以 1 1 1 n n x xG 方法二 方法二 已知的 k 组合数为 12n Seee 1 C nkk 习 题 二 第 3 页 共 14 页 其母函数为 23 0 1 1 1 1 nk n k nk A xxxxx kx 序列的母函数为 1 2 C n n C nn C nn 23 00 0 1 1 2 3 11 1 1 kk kk k k n G xC n nC nn xC nn xC nn x C nk n xC nk k x C nkk x x 3 设 求序列的母函数 1234 Seeee AAAA n a 其中 是 S 的满足下列条件的 n 组合数 n a 1 S 的每个元素都出现奇数次 2 S 的每个元素都出现 3 的倍数次 3 不出现 至多出现一次 1 e 2 e 4 只出现 1 3 或 11 次 只出现 2 4 或 5 次 1 e 2 e 5 S 的每个元素至少出现 10 次 解 1 4 35214 2 1 r x G xxxxx x 2 4 3634 3 1 1 1 r G xxxx x 3 232 2 1 1 1 1 x G xxxxx x 4 311245232 31124535678131516 22 1 2 1 1 G xxxxxxxxxx xxxxxxxxxxxxxx xx 5 4 10 10114 1 x G xxx x 4 投掷两个骰子 点数之和为 r 其组合数是多少 212 r 解 用表示骰子的点数为 i i x 1 若两个骰子不同 则问题等价于 r 的特殊有序 2 分拆 12 16 1 2 i rrr ri 习 题 二 第 4 页 共 14 页 故相应的母函数为 234562 23456789101112 234565432 G xxxxxxx xxxxxxxxxxx 则点数之和为 r 的方案总数就是的系数 r x 212 r 2 若两个骰子相同 则问题等价于 r 的特殊无序 2 分拆 12 12 61 rrr rr 而此问题又可转化为求 r 的最大分项等于 2 且项数不超过 6 的分拆数 即求方程的非负整数解的个数 12 1212 12 0 1 6 xxr xxxx 相应的母函数为 2 2522342 3456 2322222 23456789101112 11 111 2233323 G xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx 其中点数之和为 r 的方案数就是的系数 r x 5 投掷 4 个骰子 其点数之和为 12 的组合数是多少 解 参考第 4 题 第二版第 5 题 居民小区组织义务活动 号召每家出一到两个人参加 设该小区共有 n 个 家庭 现从中选出 r 人 问 1 设每个家庭都是 3 口之家 有多少种不同的选法 当 n 50 时 选法 有多少种 2 设 n 个家庭中两家有 4 口人 其余家庭都是 3 口人 有多少种选法 解 1 122 33 n G xC xC x 2 22 122122 3344 n G xC xC xC xC x 第二版第 6 题 把 n 个相同的小球放入编号为的 m 个盒子中 使得每个盒子内1 2 3 m 的球数不小于它的编号数 已知 求不同的放球方法数 2 2 mm n g n m 解 对应母函数为 习 题 二 第 5 页 共 14 页 1 2323412 1 23 1 1 1 1 2 1 1 2 3 1 1 1 1 m m mmm m m m n m m x G xxxxxxxxxx x mm mm mm xxxx m mmnm m x nm m 故 2 1 1 1 1 1 1 1 m mmnm mm mnm g n m nm mnm m 6 红 黄 蓝三色的球各 8 个 从中取出 9 个 要求每种颜色的球至少一个 问有多少种不同的取法 解 对应的母函数为 2345678 3 32345673 32345678910 11121314234567 1 12345678765 432 1 G xxxxxxxxx xxxxxxxx xxxxxxxxxxx xxxxxxxxxxx 从中取 9 个对应的组合数为的系数 即 9 x 种 1 12 1 3 14 1 5 1 6 1 7 128 方法二 方法二 原问题等价于从集合中取出 9 个元素 且每个元素 8 8 8Sabc AAA 至少取一个 现在先把元素 a b c 各取一个 然后再随意选出 6 个 则问题 转变为从集合中取出 6 个元素 且每个元素个数不限 1 7 7 7Sabc AAA 求重复组合的方案数 又由于每个元素的个数大于 6 故从中取 6 个元素与 1 S 从集合中取出 6 个元素的组合数一样多 因此不同的 1 Sabc AAA 取法为 种 62 3 6 18 28CC 7 将币值为 2 角的人民币 兑换成硬币 壹分 贰分和伍分 可有多少种兑换 方法 解 该题用 1 分 2 分 5 分的硬币组成 20 分 是可重复的无序拆分 习 题 二 第 6 页 共 14 页 其母函数为 224510 510 2 510 2 510 000 510 0 1 1 1 1 1 1 1 111111 1 4 14 12 1 111 1 1 1 442 1 1 1 2 1 1 4 iiii iii ii i G xxxxxxx xx xx xx xxx xxixxx ixxx AAA A 则不同的兑换方法为的系数 即 20 x 2015 1050 1 1 1 2 20 1 11 1 2 15 1 1 4 1 1 2 10 1 11 1 2 5 1 11 1 2 0 1 1 29 AA AAA 即有 29 种兑换方法 8 有 1 克重砝码 2 枚 2 克重砝码 3 枚 5 克重砝码 3 枚 要求这 8 个砝码只 许放在天平的一端 能称几种重量的物品 有多少种不同的称法 解 该题属于有限重复的无序拆分问题 对应的母函数为 224651015 23456789101112 1314151617181920212223 1 1 1 12223322233 22233222 G xxxxxxxxx xxxxxxxxxxxx xxxxxxxxxxx 所以能称 1 23 克等 23 种重量的物品 总共的称法为母函数的各项系数之和 再减去常数项 即总共有 种 不同的称法 1 13 4 4 147G 其中 称 1 3 20 22 23 克重量各有 1 种称法 称 2 4 5 8 9 10 13 14 15 18 19 21 克重量各有 2 种称 法 称 6 7 11 12 16 17 克重量各有 3 种乘法 若要枚举出各种方案 则可作母函数 224651015 1 1 1 G x y zxxyyyzzz 项即为 55511222 0 nnnnnnnn iii x xy yyz zzn nni 或 称克重量的一种方案 1222555 nnnnnnnn 习 题 二 第 7 页 共 14 页 9 证明不定方程的正整数解组的个数为 12n xxxr 1 1 C rn 解 该问题即 求正整数 r 的 n 有序分拆 问题可转换为 将 r 个无区别的球 放入 n 个不同的盒子中 每盒至少 1 个的组合问题 可以先在每个盒子中放 1 球 再将个无区别的球 放rn 入 n 个不同的盒子中 每盒球数不限 则其方案数为 1 1 1 C nrnrnC rn 故该不定方程的正整数解组的个数为 1 1 C rn 方法二 方法二 问题可以视为将 r 个相同的 1 放入 n 个盒子 由于将之间的值互换 对 i x 应不同的解 所以盒子不同 设共有个解 则的母函数为 r a r a 23 1 1111 0000 1 n n nrrrn rk nknk n rn rkk rrkk x G xxxx x xCxCxCxCx 所以 1 1 r aC rn 10 求方程的大于 1 的整数解的个数 24xyz 解 该题相当于将 24 的 3 有序分拆 并且要求每个分项大于 1 其母函数为 3 2 23355 3 0 121 1 12 1 2 k k xx G xxxxxk kx xx 所求的整数解的个数即为的系数 24 x 1 19 19 1 190 2 AA 11 设 其中 试证 0 2 n n k aC nkk 0 21 n n k bC nkk 0 1a 0 0b 1 11nnn aab 1nnn bab 2 求出 的母函数 n a n b A x B x 习 题 二 第 8 页 共 14 页 证明 1 1 1 0 1 1 11 11 00 1 0 1 1 2 1 0 1 2 0 2 21 2 1 21 1 22 0 1 21 11 23 0 n n k n k nn kk nn kk n n k nn aC nkk C nC nkk C nC nkkC nkk C nkkC nkkC nnn aC nkkC nnn ab 00 0 1 0 1 2 21 1 21 1 21 22 23 0 nn nn kk n k n k n abC nkkC nkk C nkk C nkkCnn b 2 因为 01 011 1 11 1 0 00 1 1 1 0 1 nnn nnnn nnn nn nn nn nn nn nn A xa xaa xab x axb x a xb xb xA xB x 所以 1 1xA xB x 同理 011 011 11 11 11 00 nnn nnnn nnn nn nn nn nn nn nn B xb xbb xabx axbx a xb x xA xxB x 所以 1 0 xA xxB x 习 题 二 第 9 页 共 14 页 解联立方程组 即可得 1 1 1 0 xA xB x xA xxB x 2 1 1 3 x A x xx 2 1 3 x B x xx 12 设 求序列的母函数 12 k Seee AA A n p 其中是 S 的满足下列条件的 n 排列数 n p 1 S 的每个元素都出现奇数次 2 S 的每个元素至少出现 4 次 3 至少出现 i 次 i e 1 2 ik 4 至多出现 i 次 i e 1 2 ik 解 1 母函数为 35 1 3 5 2 kk xx e xxxee G x 2 母函数为 45623 1 4 5 6 2 3 kk x e xxxxx G xex 3 母函数为 21 11 1 2 1 jikk x e j iii xxx G xex ji 4 母函数为 2 011 1 1 2 jikk i e jii xxxx G x ji 13 把 23 本书分给甲乙丙丁四人 要求这四个人得到的书的数量分别不超过 9 本 8 本 7 本 6 本 问 1 若 23 本书相同 有多少种不同的分法 2 若 23 本书都不相同 又有多少种不同的分法 解 1 对应的母函数为 2928 2726 2345678 9101112131415 2345678 9101112131415 1 1 1 1 123456777 765432 123456788 765432 G xxxxxxx xxxxxx xxxxxxxx xxxxxxx xxxxxxxx xxxxxxx 所求的分法数就是的系数 即 23 x 种 7 1 7 26 35 44 53 62 7 1 8119 AAAAAAAA 习 题 二 第 10 页 共 14 页 2 对应的母函数为 2928 2726 23 1 1 1 2 9 1 2 8 1 1 1 2 7 1 2 6 111111111 1 1 1 2 1 1 2 3 1 2 2 1 3 1111111 8 1 7 2 6 3 5 4 4 5 3 6 2 e xxxxxx G x xxxxxx xxx 815 23 815 1 9 6 111111111 1 1 1 2 1 1 2 3 1 2 2 1 3 111111111 8 1 7 2 6 3 5 4 4 5 3 6 2 7 1 8 7 xx xxx xx 所求的分法数就是的系数 即 23 23 x 11111111 23 8 1 7 2 6 3 5 4 4 5 3 6 2 8 7 111111111 9 1 8 2 7 3 6 4 5 5 4 6 3 6 8 7 7 111111111 1 9 2 8 3 7 4 6 5 5 6 4 5 8 6 7 7 6 1 2 9 AA A A 11111111 3 8 4 7 5 6 6 5 4 8 5 7 6 6 7 5 111111111 3 9 4 8 5 7 6 6 3 8 4 7 5 6 6 5 7 4 111111111 4 9 5 8 6 7 2 8 3 7 4 6 5 5 6 4 7 3 11 5 9 A A A 1111111 6 8 1 8 2 7 3 6 4 5 5 4 6 3 7 2 111111111 6 9 8 1 7 2 6 3 5 4 4 5 3 6 2 7 1 26 281939980582 A A 14 8 台计算机分给 3 个单位 第一个单位的分配量不超过 3 台 第二个单位 不超过 4 台 第三个单位不超过 5 台 问共有几种分配方案 解 对应的母函数为 习 题 二 第 11 页 共 14 页 232342345 2345672345 1 1 1 1234432 1 G xxxxxxxxxxxxx xxxxxxxxxxxx 所求的分配方案数即的系数 即分配方案数为 8 x 种 4 14 1 3 12 1 1 114 AAAAA 15 用母函数证明下列等式成立 1 222 2 01 nnnn nn 2 11 1 nnnmnm nnnn 证明 1 方法一方法一 根据范德蒙恒等式 0110 mnnmnmnm rrrr 令 即得mrn 222 2 011001 nnnnnnnnnn nnnnn 方法二方法二 因为 两边展开得 2 1 1 1 nnn xxx A 2 2 2222 01201 nnn nnnnnnn xxxxx nnn 比较次方的系数 即得 n x 222 2 011001 nnnnnnnnnn nnnnn 2 方法一方法一 令 1 m aC n nC nnC nm n 则 1 1 1 1 mmm aaC nmnaC nmm 且 0 1aC n n 令 2 012 0 m m m A xa xaa xa x 习 题 二 第 12 页 共 14 页 则 1 0 1 1 1 m m A xxA xC nmmx 即 23 1 1 1 1 2 2 3 3 x A xC nxC nxC nx 因为 23 1 1 1 1 2 2 3 3 1 n C nxC nxC nxx 所以 1 1 1 n x A xx 故 2 23 1 1 1 2 1 3 2 4 3 1 n m A x x C nxC nxC nxC nmm x 所以 证毕 1 1 1 m aC nmmC nmn 方法二 方法二 1 1 1 111 11 1 11 1 11 nnn m m n n mn xxx x x x xx x 比较两边的系数 即可得 n x 11 1 nnnmnm nnnn 方法三 组合意义法 方法三 组合意义法 等式右端 相当于从个不同的球中取个球的组合 1nm 1n 其组合方案数为 1 1 C nmn 等式左端 把这个球编号为 按取出的球中最小的1nm 1 2 1nm 编号 可分为如下的 m 1 类 如果取出的个球中最小编号是 1 其余 n 个球要从去掉 1 号球后1n 剩下的个球中选取 此类组合方案数为 nm C nm n 如果取出的个球中最小编号是 2 则 1 不能被选取 其余 n 个球1n 要从去掉 1 2 号球后剩下的个球中选取 此类组合方案数为1nm 依次类推 1 C nmn 如果取出的个球中最小编号是 m 则不能被选取 其1n 1 2 1m 余 n 个球要从去掉号球后剩下的个球中选取 此类组1 2 1 mm 1n 合方案数为 1 C nn 如果取出的个球中最小编号是 则不能被选取 1n 1m 1 2 m 习 题 二 第 13 页 共 14 页 其余 n 个球