《组合数学》练习题一 参考答案.doc

组合数学练习题一 参考答案一、填空：1. 2. 3. 0. 4. 2675.6.4207.78.9.10.267二、选择：1. 110 A B D D A D A B B C三、计算：1. 解 因为=25, =12, =6, =3, =1, =0,所以, 所求的最高次幂是2(50!)=25+12+6+3+1=47.2. 解 由我们最初观察的式子,有,再利用定理1,我们得到,.所以,.3. 解：设所求为，令，以，分别表示中能被，整除的整数所成之集，则4. 解：记7个来宾为，则7个来宾的取帽子方法可看成是由，作成的这样的全排列：如果（17）拿了的帽子，则把排在第位，于是（1）没有一位来宾取回的是他自己的帽子的取法种数等于7元重排数，即等于1854。（2）至少有一位来宾取回的是他自己的帽子的取法种数等于由，作成的至少有一个元保位的全排列数，为 5. 解：特征方程为特征根为故，其中是待定常数. 由初始条件得解之得所以6. =+.7、解 因为=25, =12, =6, =3, =1, =0,所以,所求的最高次幂是2(50!)=25+12+6+3+1=47.8、 解 由我们最初观察的式子,有,再利用定理1,我们得到,.所以,.9、假设存在满足条件的分划，则不仿令中各数字之和分别为于是即显然此式为矛盾等式,故假设不成立.10、 解：设所求为N，令，以A，B，C分别表示S中能被6，9，15整除的整数所成之集，则，由容斥原理得因为6与9的最小公倍数为8，6与15的最小公倍数为30，6、9、15这3个数的最小公倍数为90，故，从而 11、解：特征方程为，特征根为，所以其中是待定常数，由初始条件得解之得，所以12、解：递推关系为 四、证明：1.证明：=2. 证明：设所给的个正整数为，。令，则，对任一个不大于的正整数，令且除以所得余数为，则且，由鸽笼原理的简单形式，必有正整数（），使得2，设，是中的两个元，则它们除以所得的余数均为，于是能被整除。3、证明：（1）（2）由（1）有所以。4、证明 我们可以将平面上的整数点按坐标数的奇偶性分成4类:型如(2k,2t)的点,型如(2k,2t+1)的点,型如(2k+1,2t)的点,型如(2k+1,2t+1)的点,其中k,t是整数.则由抽屉原理,5个整数点中一定有2个点的型式是相同的,即可设此2点为(),()并且它们的型式均为(2k+,2t+)的点,其中为0或1.于是,此2点连线的中点坐标(,)必是整数点坐标.组合数学练习题二 参考答案一、填空：1. 196 2.7. 3. 4. 0. 5. . 6.-1440 7.8. 9.167 10.0.二、选择：110 D A B B B D D B A B三、计算 1. 在多项式的展开式中的项的系数是 =420.因为在它的展开式中不同项（合并同类项后）的个数等于从5个不同元素中有重复地取出7个元素的方法数，所以不同项的个数为。2.解：设所求为N，令，以，分别表示中能被14和能被21整除的整数所成之集，则 3.解：记7个来宾为，则7个来宾取帽子的方法可看成是由，作成的全排列：如果（17）拿了的帽子，则把排在第位，于是（1）没有一位来宾取回的是他自己的帽子的取法种数等于7元重排数，即等于1854。（2）至少有一位来宾取回的是他自己的帽子的取法种数等于由，作成的至少有一个元保位的全排列数，为 4.解 线段的方程为 .如果n与互素,则不定方程不存在适合的整数解,即如果n与不互素,则n与只能有公因数3,即可以设.则通过解不定方程,有整数点位于线段之上,且中间仅有这二个整数点,即.所以 5.解：特征方程为，特征根为，所以，其中，是待定常数，由初始条件得 解之得，所以 （）6.解 令一元钱币对应的能买物品的形式幂级数为；2元钱币对应的能买物品的形式幂级数为；5元钱币对应的能买物品的形式幂级数为,则该人能买物品对应的形式幂级数为所以,该人可以买价值分别为0,1,2,21,22元的物品,并且付款的方法数分别为0,1,2,2,2,3,2,3,2,2,3,2,3,2,2,3,2,3,2,2,2,1,1.7. 解 由我们最初观察的式子,有 ,再利用定理1,我们得到 , , . 所以,.8.令 .则,.于是由容斥原理有 = =.9.解：记7个来宾为，则7个来宾的取帽子方法可看成是由，作成的这样的全排列：如果（17）拿了的帽子，则把排在第位，于是（1）没有一位来宾取回的是他自己的帽子的取法种数等于7元重排数，即等于1854。（2）至少有一位来宾取回的是他自己的帽子的取法种数等于由，作成的至少有一个元保位的全排列数，为 10.解 线段的方程为 .如果n与互素,则不定方程不存在适合的整数解,即如果n与不互素,则n与只能有公因数3,即可以设.则通过解不定方程,有整数点位于线段之上,且中间仅有这二个整数点,即.所以 11.解：特征方程为特征根为故，其中是待定常数. 由初始条件得解之得所以 12. =+ 四、证明：1. 证明 在牛顿定理中令,则有 (1)对上式两边的求微商,得到 .令t=1,我们就得到第一个结论. 如果我们对(1)式两边的进行次微商,则有.在上式两边同时除以r!,并令t=1,即可得到第二个结论.2.证明：令，其中则，对任一个非负整数（01997），令 且除以1998所得余数为，则（，1，2，1997）且，如果，设是，则，由鸽笼原理的简单形式，必有正整数（11997），使得2，设和（）是中的两个元，则它们除以1998所得余数均为，从而能被1998整除，即能被1998整除。3.证明 在牛顿定理中取=1,=t,则有 = = =.比较上式两边的系数即知本定理的第一个结论成立.现在在第一个结论中令n=2n1,r=n1,m=n1,并且利用,则得到第二个结论. 4.证明：令，其中则，对任