2022年组合数学习题文件 .pdf

《2022年组合数学习题文件 .pdf》由会员分享，可在线阅读，更多相关《2022年组合数学习题文件 .pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、组合数学习题1Show that if n+1 integers are chosen form the set 1,2, ,2n,then there are always two which differ by at most 2. 从1,2, ,2n中选出 n+1个数，在这 n+1个数中，一定存在两个数，其中一个整数能整除另外一个整数。任何一个数都可以写成2k*L，其中 k 是非负数， L 是正奇数。现在从1 到2n之间只有 n个奇数。由于有 n+1个数都能表示成2k*L ， 而 L 的取值只有 n 中，所以有鸽子洞原理知道， 至少有两个数的L 是一样的，于是对应 k 小的那个就可以整除

2、 k 大的另一个数。2Show that for any given 52 integers there are exist two of them whose sum, or else difference, is divisible 100. 设 52 个整数 a1，a2，a52被 100 除的余数分别是r1,r2,r52，而任意一个数被 100 除余数为 0，1，2，99，一共 100 个。他们可以分为 51 个类0,1,99,2,98,49,51,50 。将这 51 个集合视为鸽笼，则将r1,r2,r52放入 51 个笼子中，至少有两个属于同一个笼子，所以要么有rirj，要么有 rir

3、j100，也就是说 aiaj|100或者 aiaj|100。3从 1，2，3， 2n中任选 n+1 个数，证明在这n+1个数中至少有一对数互质。鸽子洞原理，必有两个数相邻，相邻的两个数互质4Prove that Ramsey number R(p,q)R(p,q-1)+R(p-1,q). 令 NR(p,q-1)+R(p-1,q)，从 N 个人中中随意选取一个a，F 表示与 a 相识的人，S表示与 a不相识的人。在剩下的 R(p,q-1)+R(p-1,q)21 个人中，由鸽子洞原理有，或者F 中有R(p,q-1)人，或者 S 中有 R(p-1,q)人。如果 F 中有 R(p,q-1)人，则与 a

4、相识的人为p 个；如果 S中有 R(p-1,q)人，则与 a 不相识的人有 p 个。所以有 R(p,q)R(p,q-1)+R(p-1,q) 5There are 10 people, either there are 3 each pair of whom are acquainted, or there are 4 each pair of whom are unacquainted。从 10 人中随意选一个人p，F 表示与 p 相识的人， S表示与 p 不相识的人若 F 中至少有 4 人， 如果至少有 4 人不相识，则满足题设；如果有 2 人相识，则加上 p 有 3 人相识，也满足题设。若

5、 F 中至多有 3 人，则 S中至少有 6 人，6 人中至少有 3 人相识，或者不相识。如果相识则满足题设， 如果不相识加上 p 不相识的人就有 4 个， 也满足题设。6In how many ways can six men and six ladies be seated at round table if the men and ladies to sit in alternate seats?6 个男的先进行圆排列，然后6 个女的插入空位。7In how many ways can 15 people be seated at round table if B refuses to s

6、it next to A? What if B only refuses to sit on A right?名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - A15个人进行圆排列，减去ab 组成一个元素的 14 人的圆排列，然后减去 ba 组成一个元素的 14 人的圆排列。B15个人进行圆排列，减去ab 组成一个元素的 14 人的圆排列。8Determine the number of 10-combinations of t

7、he multiset S=*a,4.b,5*c,7*d。(1+x+x2+x3+)( 1+x+x2+x4) ( 1+x+x2+x5) ( 1+x+x2+x7)展开9把 n个有编号的球放入m 个有编号的盒子中，不允许有空盒子，有多少种放法。先假设，盒子没有编号， 然后乘上组合与排列的关系：),(!*2mnSm10 证明在 n （n 2）个人中总有两个人， 他们在这群人中所认识的人数目相同。当 n2 时，如果两个人相互认识， 则每个人认识的人只有一个；如果不认识，则每个人认识的人为0 个。当 n2时，设 xi (x=1,2,n)表示，第 i 个人认识的人的数目。（每个人最多只能认识 n-1 个人。

8、 ）A如果每个人都有熟人那么由鸽子洞原理知道至少有两个人i 和 j 认识的人数相同即xixj B如果只有一个人没有认识的人那么对于剩下的n1个人来说能认识的人对多只有n2 个，由鸽子洞原理知道，这n1 个人中至少有两个人i 和 j 认识的人数一样即 xixj C如果至少有两个人都没有熟人，则满足题设。11 一个剧团演出 11周，为保证收入和不至于太累，规定每天至少演出一场，每周不超过 12 场。证明存在连续的若干天，恰好演出21场。设 a1为第一天该剧团的演出的次数，ai表示前 i 天一共的演出次数。可知道 ai是单调递增的。 且有 a1=1,a77=132。于是有 ai21(i=1,2,77

9、)，也是单调递增的。而a7721=n。两堆石头关系等价，所以下面以第一堆为参照。A 考虑第一堆石头都集中在k 类集合里面 （除去单出来的石头外，其他石头都两两在一起）。此时如果第二堆石头里面有分布在k 类集合中的元素，则肯定有满足题意的来自两堆石头的两块石头；如果先让第二堆石头分布满在其他的2/n k 个集合，因为每堆中石块重量不同，那么现在一共有n1 或 n2块石头分布在集合中，第二堆就多出了1 或 2 个石头，那么这1 或 2 个石头肯定是在前面的k 个集合中，所以这也有满足题意的两块石头。B如果第一堆石头分布在i（i 从 k 到 p）个集合中， 同样，显然第二堆石头分布满剩下的2/ni

10、个集合，由于每堆中石块重量都不一样，所以第二堆将会多出q2*i2*2/n块石头， 那么这些多出来的石头，肯定会分布在第一堆石头所在的i 个集合中，所以有满足题意的两块石头。17 在 9 个人中，或者有 3 人相互认识，或者有4 人相互不认识。N(3,4) = N(2,4)+N(3,3) 因为 N(2,4)和 N(3,3)都为偶数，所以有：N(3,4) 1 f(1)=C n=1名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - 设

11、n=2k,C 为常数f(n)=2f(n/2)+C 2f(n/2)=4f(n/4)+2C 4f(n/4)=8f(n/8)+4C 2k-1(n/2k-1)=2kf(n/2k)+2k-1C 将上面的各等式，左右相加得：f(n)=C+2C+2k-1C+2kf(n/2k)= C+2C+2k-1C+2kC =kiiC02*=C*(2K1-1) H(n)=4H(n-1)-4H(n-2) n1H(0)=0，H(1)=1 特征方程为 x2-4x+4=0 解为二重根： q1=q2=2 通解表示为： Hn=C1*2n+C2*n2n由 H(0)=0，H(1)=1 有： C1+0*C2=0 C1*2+C2*2=1 解得

12、:C1=0 C2=1/2 Hn=n*2n-126. 在 r 位二进制序列里，使数字0 不相邻的序列有多少个（用递推方程）？前一位的 0 和 1 都会允许后一位为1，前一位为 1 后一位允许为 0。所以设 f(x) 表示 x 位的满足条件的序列的个数，有：f(x) = f(x-1)+f(x-2) /f(x-1)表示 f(x) 中第 x 位为 1 的序列数/f(x-2)表示 f(x) 中第 x 位为 0 的序列数f(1) = 2 f(2) = 3 Fn27Kn=是 n 个结点的完全图， G1=和 G2=是 Kn的子图，且 E=E1E2，E1E2=。nn)251(10535)251(10535名师资

13、料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 12 页 - - - - - - - - - 证明 n11,若 G1是平面图，则 G2不是。 证明 G1和 G2必有一个是连通图。假设 G2也是平面图。那么有e1=3n-6,e2=3n-6，所以有 e=2(3n-6) 。因为 Kn是完全图所以有 en*(n-1)/2，所以有 n*(n-1)/2=2(3n-6)，n2-13n+2411时，不等式不成立，所以当 n11时，由假设得出得结论是不成立得，所以假设不成立，所以若 G1为平面图

14、， G2肯定不是平面图。化简得：假设两个图都不是连通图。有e1=n-2 和 e2=n-2 成立从而有e=2(n-2) 。因为 Kn是完全图所以有 e=n*(n-1)/2，所以有 n*(n-1)/2=2n-4，解得 n25n80，所以矛盾，所以必有一个图是连通图。28. Let G be a planar graph of order n in which every vertex has the same degree k. Provw that k5. （evdrdi2)()(,e=3r）所有点度的和应该是边数的2倍， 即evd2)(。 由题意由 G的nkvd)(，那么由 nk2e，对于平面

15、图我们有e=3n-6，所以有nk=6n12，k=6-12/n ，因为 k为整数，所以有k(G)。设 a 点时 G中度最小的点， 那么(G)就是与 a 相连的边数，将与 a 相连的边全部去掉，那么G就不在连通，所以 (G)(G)是不可能成立的。所以有 (G)(G)。证(G)(G)：若(G)1，即只需要去掉一条边G就不在连通，此时记这条边为e 这条边的两个端点记为 V1和 V2，则 e 是这个图的桥， 此时有 (G)1，所以(G)(G)成立。若(G)=2，此时若去掉 (G)条边 G就不连通了，如果只去掉 (G)1 条边，则会产生一个桥e(u,v) 。对于 (G)1 条边中的每一条边，都删去一个不同

16、于 u，v 的点，则至少删去 (G)1 条边。若这样产生的图是不连通的则有 (G)(G)1(G)；若仍连通则产生桥e(u,v) ，删去 u 或者 v G 也不在连通，此时 (G)=n ，所以 G一定有 H路径。设此路径为V1,V2, ,Vn。若 V1和 Vn相邻接，则构成 H回路。若 V1和 Vn不相邻接。假定 V1邻接于 Vi1，Vi2， 。 。 。 ，Vik(2=Vik=n-1) ，则 Vn必邻接于 Vi1，Vi2， 。 。 。 ，Vik中一点。若 Vn与 Vi1，Vi2， 。 。 。 ，Vik都不邻接，那么 Vn至多邻接 n-k-1 个点邻接即 d(Vn)=n-k-1 ，而 d(V1)

17、k，那么有 d(V1)+d(Vn)=n-1, 与题设矛盾。所以Vn必与 Vi1，Vi2， 。 。 。 ，Vik中一点邻接，从而构成H回路。V1 V2 Vi Vn 32. Prove that a graph G is bipartite if and only if each of its cycle has even length. 二分图定义： G的点可以可以分成互不相交的两部分X，Y。如果一条边是两个集合间的边， 那么肯定一个点是X另一个点是 Y的；没有一条边是一个集A B P Q 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

18、- - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - 合中的边，两个点都属于一个集合X或者 Y的。A如果 G有奇数长度的回路那么，肯定会有如图所示子图的情况：X Y 。x1。y1。z 此时|E| 为奇数， |V| 也为奇数。若 z 是属于 X集合的点，那么对于边e(x1,z) ，x1和 z 都属于 X，这个与定义不符。若 z 属于 Y，同样不满足。B若每个回路长度都是偶数，那么每个回路肯定会有这种结构。X Y 。x1。y1。此种情况是满足定义的。C对于非回路，可以把每个隔点，归于一类，这样也可以满足定义。33Prove that the

19、 second Stirling number satisfies a recurrence relation S2(n,k)= kS2(n-1,k)+ S2(n-1,k-1) 第二类 stirling 数 S2(n,k)的意义是将 n个有编号的球放入k 个无编号的篮子中的放置方法数。假定，我们将第 n号球先取出来单独放置。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - - - - - - A如果第 n 号球单独占用一个篮子， 那么就是将剩下的

20、n1 个球放入 k1 个篮子中，有S2(n1,k1)。B如果第 n 号球没有单独占用一个篮子，那么就是剩下的n1 个球放入 k个篮子中，有S2(n1,k)。第 n号球可能在 k 个篮子中的任意一个，所以放置方法数为K* S2(n1,k) 所以得到 S2(n,k)= kS2(n-1,k)+ S2(n-1,k-1) 34A、B、C、D 四台机器和 1、2、3、4、5 五种颜色，规定 A 和 D 不能用 1和 4，B 不能用 3，C 不能用 2 和 3，D 不能用 5。为每台机器恰好涂一种颜色的方案数有多少？引入第五个机器 E，并且 E 不能涂任何颜色。1 2 3 4 5 A B C D E 名师资

21、料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 12 页 - - - - - - - - - 35两位教师带 k 位同学外出， 排成一列， 为安全起见， 规定教师必须排在队首和队尾。休息后重排， 每个人都不在原来的位置的排法有多少种？试用有禁区的排列棋盘多项式求解。Dn=K!-C(K,1)(K-1)!+C(K,2)(K-2)!+(-1)KC(K,K)0! 有禁区的棋盘：N=K!-r1(k-1)!+r2(k-2)!+(-1)krkK K R()=R()K=(1+x)K=KiixiKC0),(名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 12 页 - - - - - - - - -