中科大夏令营——组合计数问题

《中科大夏令营——组合计数问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、组合计数问题中的基本方法和例题选讲王新茂中国科学技术大学基本概念1•排列数:m2.组合数：3.容斥原理:n—1Am=-QA;=0设Si,S^,都是有限集S的子集,则有u・.W工⑸I—刀⑸21l

2、个数。4•对应法：把陌生问题转化为熟悉问题。5.递推法：利用递推关系计数。6.母函数：利用生成函数计数。三基本例题1.从m个不同元素中有序地选出？2个可重复元素，共有种选取方式。答:mn2.从TH个不同元素中有序地选出72个不同元素,有种选取方式。答：A3•从m个不同元素中无序地选岀71个不同元素，共有种选取方式。口•4•把冗1个1，个2；%个A;排成一行，共有种排列方式。沁(冗1+…+Tlk)合：iinil…口讣5.设（ab•••,為）是（九…，％）的一个排列。若％ai丰bi，则称（九…®）是…，仏）的一个错位排列。（1,2,...,切的错位排列共有

3、个。k=0答：0

4、）称为g（冗）之Mobius逆变换。例：°（冗）之Mobius变换g（〃）=n。7•把m个不同小球放入冗个不同盒子，允许空盒，共有种结果。答：nm8.把m个不同小球放入〃个不同盒子，没有空盒，共有种结果。n答：力（-1广k=09•把m个不同小球放入冗个不同盒子，盒中的小球数分别为虹…，為，共有种结果。10.把nz个不同小球分成冗组，每组非空且不计次序,共有种结果。允许空盒，共11•把m个相同小球放入冗个不同盒子,有种结果。答:m+n—1—1)12•把TH个相同小球放入冗个不同盒子，没有空盒，共有种结果。13•把TH个相同小球分成冗组，每组非空且不计次

5、序,共有种结果。答：方程组X1+X2+…+切=冗的非负整龙1+2龙2+•••+mx讥=m数解的个数，或多项式g讥的刃V项系数。n-Z=11—xly14.从｛1,2,...,冗｝到｛1,2,...,zn｝的映射共有个,其中单射个，满射个。15.集合｛1：2,...，〃｝共有集。答：士mk=0'丿个不含相邻整数的子列｛&｝亀共有个。l)n―mn17•在整点网格中,有条。从（00到的最短路径共答：1&满足1

6、

7、_(m+n)/2jn列仏｝=共有个。答:21.满足V£di=±1并且Qi+•••+©丰0的数列｛@｝；i共有个。m((m“(k>n/222.方程+龙2+•…+工*-解。m+n—1n—1二机共有组非负整数23.若龙iHxn=m,其中叼＞＞龙仇且都是正整数，则称（龙1；.••,孙）为正整数m的一个冗项分拆。探m的分拆共有个。答：方程龙1+2龙2Frnxm=m的非负整数解的个数。探m的Ti项分拆共有个。答：同例13。m的冗项分拆个数满足探772的各项龙z<的分拆共有个。答:方程龙1+2龙2+・•・+=尬的非负整数解的个数,等于m的不超过冗项的分拆个数，也等于m

8、+冗的?2项分拆个数。24•平面上冗条直线至多可把平面分成个区域,至多个是无界区域。答:

9、(n2+71+2),2n25-平面上〃个圆至多可把平面分成个区域。答：n2—n+226.球面上Ti条圆弧至多可把球面分成个区域。答：n2-n+227•空间中冗个平面至多可把空间分成个区域,至多个是无界区域。答:

10、(n3+5n+6),n2—n+228.空间中冗个球面至多可把空间分成个区域。答:

11、(n3—3n2+8n)29•平面凸冗边形的边线和对角线至多有个交点在凸〃边形的内部，至多有个交点在凸冗边形的外部。30.平面凸〃边形的边线和对角线至多可把平面分成个区域，至多可

12、把凸冗边形的内部分成个区域。答：⑴舟（（2）2+（2）+2）—号（仇-1尸—3（