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

1、组合计数问题中的基本方法和例题选讲王新茂中国科学技术大学基本概念1排列数:m2. 组合数：3. 容斥原理:n1am =- qa;=0设si,s,都是有限集s的子集,则有u.w工i刀21l<i<nl<i<j<nl<i<nsix u u sjk + + （-1）" *si u u4. 二项式定理:（龙 + 9）n .i xnyz=05 多项式定理:nexz 1z一冗1!nirik：=n 基本方法1乘法原理：把一个事件分解为若干独立事件的乘积 形式。2加法原理：把一个事件分解为若干互斥事件的和的 形式。3算两次：从多个方面计算满足条件的元素个数。4

2、对应法：把陌生问题转化为熟悉问题。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,.,切的错位排列共有个。k=0答：0<i+j<nn!(2n

3、-2z-ij(n i j)!26把元素均匀地排在圆周上，称为圆周排列。一个圆 周排列经旋转后仍是同一个圆周排列。冗个不同元素共有种圆周排列方式。答：仇一1)!g的圆周排列共答:设以族为最小正周期的排列个数于伙），以加为周期的排列个数g伙）。d k得屮）=工（扌）g（），所求圆周排列的个数d厶亠 knkmd meuler函数9仇）为不大于冗且与冗互素的正整数个 数。探mobius函数”（冗）=（-1卩，若冗是r个不同素数之积; 否则“（71）= oogn） =称为 f（切之mobius变换,/hdndng（d）称为g（冗）之mobius逆变换。例：°（冗）之mobius变换g（）= n

4、。7把m个不同小球放入冗个不同盒子，允许空盒，共 有种结果。答：nm8.把m个不同小球放入个不同盒子，没有空盒，共 有种结果。n 答：力（-1广k=09把m个不同小球放入冗个不同盒子，盒中的小球数 分别为虹，為，共有种结果。10.把nz个不同小球分成冗组，每组非空且不计次序, 共有种结果。允许空盒，共11把m个相同小球放入冗个不同盒子, 有种结果。答:m + n 1n 1)12把th个相同小球放入冗个不同盒子，没有空盒，共 有种结果。13把th个相同小球分成冗组，每组非空且不计次序, 共有种结果。答：方程组x1+x2 +切=冗 的非负整龙 1 + 2龙 2 + + mx 讥=m数解的个数，或多

5、项式g讥 的刃v项系数。n-z=11 xly14.从1, 2,.,冗到1, 2,., zn的映射共有个,其中单射个，满射个。15.集合1： 2,.，共有 集。答：士 mk=0 '丿个不含相邻整数的子列&亀共有个。l)n mn17在整点网格中,有条。从（00到的最短路径共答：1& 满足 1 < ai < < a7 有个。答：+ 冗1)2 < m的整数序列%=共19.满足1 < ai << an < m并且每个心与2的奇偶性相同的整数帀列©=共有个。答：|_(m + n)/2jn列仏=共有个。答:21.满足v

6、3; di = ±1并且qi + + ©丰0的数列；i共 有个。m (m“(k>n/222.方程+龙2 + +工* - 解。m + n 1n 1二机共有组非负整数23.若龙i hxn = m,其中叼龙仇且都是正整数，则称（龙1；. ,孙）为正整数m的一个冗项分拆。探m的分拆共有个。答：方程龙1 + 2龙2f rnxm = m的非负整数解的个数。探m的ti项分拆共有个。答：同例13。m的冗项分拆个数满足探772的各项龙z < 的分拆共有个。答:方程龙1 + 2龙2 + +=尬的非负整数解的个数,等于m的不超过冗项的分拆个数，也等于m+冗的?2项 分拆个数。24平面

7、上冗条直线至多可把平面分成个区域,至多个是无界区域。答:|(n2 + 71 + 2), 2n25-平面上个圆至多可把平面分成个区域。答：n2 n + 226.球面上ti条圆弧至多可把球面分成个区域。答：n2 - n + 227空间中冗个平面至多可把空间分成个区域,至多个是无界区域。答:|(n3 + 5n + 6), n2 n + 228.空间中冗个球面至多可把空间分成个区域。答:|(n3 3n2 + 8n)29平面凸冗边形的边线和对角线至多有个交点在凸边形的内部，至多有个交点在凸冗边形的外部。30.平面凸边形的边线和对角线至多可把平面分 成个区域，至多可把凸冗边形的内部分成个区域。答：舟（2）

8、2 +（2）+ 2）号（仇-1尸3（ 1） + 2） 3（；） + |（32 5n + 2）；n_2(2)朗=1，ana仇一i+冗一2 + 丁仇1 力)伙1)k=2四例题选讲1. （2008全国联赛）把24个志愿者名额分配给3个学校, 则每校至少有一个名额且各校名额互不相同的分配 方法有种。答:（亍）30 1 = 2222. (2010天津预赛)ai,昭昭05是1，2, 3,4, 5的一个排 列，且血逅+1|弄1 (/ = 1, 2,3,4),则满足条件的 排歹！jai： a2,昭«4,偽的数目为°答：您=1，5各有4种排列,a3 = 2,3,4各有2种排列, 共14种。3

9、给定正整数冗。不有组非负整数解。答：仇+ 1)3 佇)等式卩+ 9 +0 < x.y.z < n4走71级台阶，每步跨13级台阶，共有 法。种走答：a。=如=1，= 2，如=an-i + a冗_2 + 術_3 （冗 > 3）或kj xyn 2x 3y）!/ c/5由数字123构成且不含相邻的1的创立正整数共 有个。答：a0 = 1, ax = 3, an =+ 2an_2 (n > 2)或& （2008天津预赛）满足偶数数目不少于奇数数目 的12加的非空子集的个数为°答：刀 ）（”）=2"t _ 1； n = 2fc + 1;n = 2fc.

10、7. （2009福建预赛）1,2,.,冗的元素和为奇数的非空 子集的个数为o答:多项式几龙）=（1 +龙）（1 + *）（1 +肝）的奇数项 系数和少）/（1）= 2-1& (2008吉林预赛)若集合,刈2满足4i u a2 = a,则记加如是4的一组双子集拆分。规 定加如和血 加是4的同一组双子集拆分。已知 集合a =那么4的不同双子集拆分共有组。答：|(3n + 1)9. （2010全国联赛）一种密码锁的密码设置是在正冗边 形儿禺勺每个顶点处赋值0和1两个数中的一 个，同时在每个顶点处涂染红、蓝两种颜色之一, 使得任意相邻的两个顶点的数字或颜色中至少有一 个相同。问：该种密码锁共有

11、多少种不同的密码设 置？答：4工a.b7n(2a)!(2b)!仇 _2a 2b)!=/(i? !) + /(!)1) +/(1?+1) = 3n + 2 + (l)n,其中 f )讥(1 + 龙 + y)no10. （2008女子数奥）给定个刼x 2冗的棋盘，棋盘上每 个方格的颜色均不相同。在棋盘的每一个小方格中 填入cgw o这4个字母中的个，若棋盘中每 个2 x 2的小棋盘中都有g g,o这4个字母，则称这个棋盘为“和谐棋盘”。问有多少种不同的"和谐 棋盘”?答：每一行或每一列都是某两个字母交替出现。共 有2 （；） 22n - 4! = 12 4n - 24种"和谐棋

12、盘”。11用m种颜色对正冗边形的顶点染色，使相邻顶占的 颜色不同，共有种染色方式。、小'答：。2 = m(m - 1), an = m(m - 1严 _ (n > 3) an - (m - l)n = _仏_1 一(m 1严-1) 或同余叫解的个数 的th倍,乞(-1)；)沪 + (1)% =伽 _ 1)« +12. （2001冬令营）将周长为24的圆周分成24段，从24个 分点中选取8个点，使得其中任何两点间所夹的弧 长都不等于3和&问满足要求的8点组的不同取法 共有多少种？答：满足要求的8个点在循环表 /i 4 7 10 13 16 19 22格9 12 1

13、5 18 21 24 3 6中不相令艮同上 17 20 23 2 5 8 11 14/题m = 3,n = 8,取法种数258。13.甲、乙两队各出71名队员参加擂台赛。负者出局, 胜者接受对方下一名队员的挑战，直至有一方队员 全部出局。若双方队员的出场顺序已经排好，比赛 过程共有种情况。14甲、乙、丙三队各出冗名队员参加擂台赛。负者出 局，胜者接受另一方下一名队员的挑战，直至有两 方队员全部出局。若三方队员的出场顺序已经排 好，甲队和乙队首先比赛，比赛过程共有种胜负情况。答：n, n)种 情 况。当min(z, k) =0时,="需护；当min仏时，= i-ij-i刀(一1)1-皿

14、处)+刀(-1)1%仏/出)+ f=0/=0k1刀(j)f必“)。qm a(l丄 1) = 6, a(2,2,2) = 42, a(3,3,3) = 306, a(4,4,4) = 2280, a(5,5,5) = 17214。15用10种不同颜色、每种颜色10粒、形状相同的i。粒 珠子可串成种样式的项链。答：同上节例6,项链样式个数等于 爲（弓）曲+92何） dllo /其中=罟u以10为周期的排列个数,92）是以10为周期的对称排列个数。化= 501如5） = 0,仍=10 10!,如10） = 50o五参考文献1.高中数学联赛备考手册（预赛试题集锦），中国 数学会普及工作委员会组编，华东师范大学岀版 社。2.走向imo：数学奥林匹克试题集锦，im0中国 国家集训队教练组编，华东师范大学出版社。iii3. 组合恒等式，史济怀编著