习题10

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【习题10:约定】未特别说明时,集合选取不重复、组合不计顺序;数位可重复与否按题设分别说明。同类明信片、同色球视为不可区分。组合数 的上项为非负整数且下项越界时取0;若上项本身为负,不使用普通阶乘式。空选取、空串各计一种。

【10.1】从1至1000中选三个不同数,使和为4的倍数。

按模4的余数分为0、1、2、3四类,每类250个。无序余数组合只有000、013、022、112、233五类,故方法数

同余类重复时要选不同元素,所以用组合数而不是 ;三个不同类时各选一点即可,无需再乘三者排列数。

【10.2】以n边形的顶点为顶点、三条边都是内部对角线的三角形有多少个?

选出的三个顶点不能有相邻者。对 ,先在其中指定一个顶点,环上它的两个邻点不能选,余下 个点成一条线,再从中选两个不相邻点,有 种。共有n种指定点,每个三角形被指定三次,故

时为0。不能直接用 ,其中含有使用多边形边的三角形;也不能把 代入末式得到伪解1。

【10.3】三位十进制数恰有一个8和一个9。

第三位只能来自0至7,先作 种排列;其中以0开头的089、098不为三位数,减去2,得到46。另可按第三数字非零有 种,第三数字为0有4种,合为46。

【10.4】用1、2、3、4组成大于230的三位数。

题目未禁止数字重复,按允许重复解释。百位为3或4,有 种;百位为2时,十位须3或4,个位任选四种,有8种,总计40。若另加“数位不重复”条件,则改为 ;不能默默把两个不同问题混为同一答案。

【10.5】从1至9选不同数字组成七位数,5和6不相邻。

全部为 。坏情况必须同时选中5、6,把二者作为一块,有2个内部次序;再从另外7数字选5个,与该块共6个对象全排,坏数为 。故答案 。只出现5或只出现6的数也合法,已包含在总数中。

【10.6】n个不同整数取出两组,第一组最小值大于第二组最大值。

两组须非空,否则最小、最大值无定义。按“取出”允许其余数不选解释:先选两组合起来的m个数,按大小排序,在相邻两数间选一个切口,低端作第二组,高端作第一组,有 种。因此对 ,

若额外要求n个数全部分完,就只有 种切口;题目是否允许未选元素会改变答案,必须先说明。

【10.7】n元集A,,求所有子集大小之和。

数“元素a及一个含a的子集B”这类关联对:每个a固定后,其余 元素各有选或不选,恰在 个子集中出现。题中子集符号按含空集和全集的 理解;若明确只对真子集求和,应再减去全集贡献n。

【10.8】1至1000中各位数字和小于7的整数数目。

先把0至999写成允许前导0的三个数位,要求 。三个数字自动不超过6,补松弛变量得到四个非负整数和为6,数目 。其中含0要减1,但原区间还包括1000,数字和1,要加1,最终仍为84。

【10.9】由0至5组成不重复且大于34521的五位数。

首位4或5,有 种;首位3时,第二位必须5才可能超过阈值,有 种。前两位34后,剩余能形成的最大数恰是34521本身,不能计入严格大于。合计264,首位0从未计入。

【10.10】大于5400、不含2与7、且数位不重复的整数。

可用数字为 ,最多8位。五至八位全部合格,各长l有 个。四位数分为:首位6、8、9的 个;前两位56、58、59的 个;前两位54的 个,这些尾部不会是重复00,因此都严格大于5400。总计

不能只数四位数,也不能因“整数”无位数上限就误判为无穷;不重复且只有8个可用数字给出了最大位数。

【10.11】k类明信片库存不限,分别寄给n个不同朋友,。

每人一张、类别可重复:。每人一张且所有人类别不同:。每人两张不同类别、不同朋友可选相同类别对:,每人的两张没有先后次序。若给两张还要计顺序,则应改用 的n次方,原题未要求此额外区别。

【10.12】第i类明信片有 张,全部分给n个不同朋友。

设 且同类副本不可区分。每类独立地分配,分给各人的张数满足n元非负整数方程,故总数为

允许朋友收到0张;若要求每人至少收到一张,会有跨类别的总量限制,不能直接沿用。若每张实物都另有可区分编号,则是另一个模型,答案为 。

【10.13】24卷百科全书选5卷,任何两卷不相继。

用不相邻选取公式得 。书架为线形,不把第1卷与第24卷视为相邻。

【10.14】多重集含5个a和各一个b、c、d、e,全排列满足指定不相邻条件。

(1)任意两个a不相邻:先排b、c、d、e,有 ;其周围恰5个空隙,5个a必须每隙一个,得24。(2)b、c、d、e中任何两者不相邻:先放成一串的5个a,提供6个空隙;选4个不同空隙分别放四个字母,得 。第二问允许a相邻,不应把第一问条件也一起加上。

【10.15】在1至 中取有序三元组 ,要求 。

这里允许 ,否则题目后面的分类没有意义。(1)若 ,x、y各有k种,故恰 。(2)当 ,只须从 个数中选较小值与较大值z,得 ;当 ,选三个不同数并按升序确定x、y、z,得 ; 同样多。(3)两种计数相等给出

【10.16】密码长4至6,每位为大写字母或数字,且至少有一个数字。

长度l的全部串为 ,减去全字母串 ,再按长度相加,得

数字可以在首位、也可重复,不应另加“首位不是0”的整数限制。

【10.17】求 中 的系数。

从25个因子选12个提供2x,其余提供 ,系数为 ,由于13为奇数,符号必须为负。

【10.18】用归纳法证明二项式定理。

时成立。设n阶式成立,两边乘 ,某项 的系数来自原来的两个相邻项,为 ;端项系数都为1。于是得到n+1阶式,归纳完成。越界项系数取0可统一处理两端。

【10.19】计算 。

写成 。本例二项式系数1、4、6、4、1都小于10,不需进位;更高次时不能一律把杨辉三角一行直接拼成十进制整数。

【10.20】正整数n,哪个k使 最大?

相邻项比值为 。比值大于1时上升、小于1时下降。因此n偶数时唯一最大项为 ;n奇数时 两项并列最大。范围为 。

【10.21】证明三个二项式恒等式。

(1)。(2)同样 。(3)由 ,

三式均对 成立,第三式起点是1,没有除以0的项。

【10.22】求三个组合数和。

(1)对 ,令 ,用变上项求和得到

(2)对 ,

证明数长 、含n个1的二进制串。它至少含 个0,按第 个0之前有k个1分类:该0前的 位可排成 种,之后剩余m-k位放n-k个1,有 种,分类相加即得。(3)当 ,偶下标项之和为

时此和为1,须另列,不能误写 。

【10.23】证明六个恒等式,并补全必要范围。

(1)对 ,令 ,补齐加权和再减去最高项,得

时左边为空和0,右边也为0。

(2)原题结论0必须要求 。正确的完整形式是

当 时末和为0;当 时只剩一项,答案为 ,不能仍写0。这是对原题缺少边界条件的修正。

(3)对 ,用 后由Vandermonde得

(4)对 ,将 写成 ,再对交错和去掉常数项,得到

(5)对 ,有限多项式恒等式 两边在0至1积分,得到

分式在0处的奇点可消去,实际积分对象是多项式,不涉及发散积分。(6)对 ,

用10.22(2)的二进制串证明,把其中m与n的角色交换即可;此时串长n+r+1、1的数量m,按第r+1个0以前的1数分类。

【10.24】从0、1、2无限库存中取n个排成串,相邻数字不相同。

时首位3选,其后每位只能避开前一位,有2选,故 。 是空串1种;这里是符号串,不禁止首位0。

【10.25】列出多重集 的全部3排列与3组合。

3排列共19个:aab、aac、aba、abc、aca、acb、acc、baa、bac、bca、bcc、caa、cab、cac、cba、cbc、cca、ccb、ccc。每个最多2个a、1个b,不能列aaa或含两个b的串。

3组合共6个,以标准字母顺序代表:aab、aac、abc、acc、bcc、ccc。组合中abc与acb是同一个选择,不重复列出。

【10.26】3蓝、2红、2黄球排成一列,黄球不相邻。

同色球不可区分。先排蓝、红五球,有 种;六个空隙中选两个放黄球,有 种,得150。也可用全部 减去黄球成块的 ,仍得150。

【10.27】有限多重集 各种大小子集总数。

第i类可取0至 个,独立选择后总数为 ,包括空集与全集。子集仍是子多重集,同类副本不区分身份。若某类为无限库存,总数也不再是一个有限整数,应另说明库存条件。

【10.28】前t类各只有1个,其余k-t类库存无限,求r组合数。

设 。若 ,先从前t类选j类各取1个,再将其余r-j个分配给s个无限类别,得到

若 ,没有无限类别,直接为 ;r超过t时为0。 时均为1。也可把答案理解为 的 系数,为下一章生成函数做准备。