组合数学补充内容

组合数学补充内容汤可因itstangky@第1页容斥原理在说到加法原理时强调过要求事件独立性当多个事件不再独立时比如：在某一个学校，教A班老师有10人，教B班老师有10人，问教A，B两班老师有多少人？答案不一定是20人。因为可能有一个老师同时教两个班情况，这就是不独立情况加上条件：同时教A，B两班老师有5人容斥原理：第2页容斥原理例题2：1～100内，能被3，5两个数之一整除数有多少个？能被3整除数有100/3=33个，能被5整除数有100/5=20个，所以能被3，5之一整除数有33+20=53个？上述说法是错误。比如15既能被3整除又能被5整除，再上述算法中被计算了2次所以应该减去能同时被3，5即能被15整除数个数6个，正确答案应为33+20-6=47个独立不独立第3页容斥原理例题3：前面我们接触到都是2个事件情况，现在来看一个当事件数为3情况。1～100内，能被2，3，5三个数之一整除数有多少个？能被2，3，5整除数分别有50，33，20个。能被2，3同时整除数有16个；能被2，5同时整除数有10个；能被3，5同时整除数有6个所以答案为50+33+20–16–10–6=71个？考虑能同时被2，3，5整除数，在计算能被一个数整除数时被加了3次，而在计算能被两个数整除数时被减了3次，也就是说最终答案71漏算了这些数！所以，答案应为71+3=74个！第4页容斥原理有了前几题基础，来看一题比较含有普遍意义题：给出n个数a1,a2,…,an，问[1,m]区间内整数有多少个能被这些数之一整除能同时被a1,a2,…,ak整除等价于能被lcm(a1,a2,…,ak)整除，即能被他们最小公倍数整除利用容斥原理：对于这n个数中每一个数，答案加上能被这个数整除数个数对于每两个数，答案减去能被这两个数整除数个数对于每三个数，答案加上能被这三个数整除数个数对于每四个数，答案减去能被这四个数整除数个数……第5页容斥原理上述例题该怎样用程序实现？主要要实现枚举子集方法1：利用回溯法枚举计算方法2：利用位运算，直接For循环得到方法1比较基础，不在这里讨论。接下来要说是比较轻易实现方法2第6页容斥原理上述例题该怎样用程序实现？枚举子集S无非就是看第i个数是否在集合S中，那么即枚举1～2n–1，在二进制下即为000…01～1111…1，右数第i位对应了第i个数是否在所枚举到集合S中比如，n=4时：十进制5对应了二进制0101，表示了a1与a3在集合中。对应到原题，当枚举到这个数时你需要计算能同时被a1,a3整除数有多少个，因为有2个数（1个数为2），则在答案中减去所求结果十进制11对应了二进制1011，表示了a1,a2与a4在集合中。对应到原题，当枚举到这个数时，你需要计算能同时被a1,a2,a4整除数有多少个，因为有3个数（1个数为3），则在答案中加上所求结果第7页容斥原理for

(int

i

=

1;

i

<

(1

<<

n);

i++)

{

int

s

=

1,

c

=

0;

for

(int

j

=

0;

j

<

n;

j++)

if

((i

>>j)&1)

{//假如i第j+1位是1

c

++;

s

=lcm(s,a[i]);//那么求lcm

}

if

(c%2==1)//假如当前计算数个数是奇数

ans

+=

m/s;

else

ans

-=

m/s;

}

第8页容斥原理for

i:=1to1shlndobegin

s

:=

1;

c

:=

0;

forj:=0ton–1do

if

(i

shrj)and1=1thenbegin

inc(c);

s

:=lcm(s,a[i]);

end;

if

cmod2=1then

ans

:=

ans+mdivs;

else

ans

:=

ans+mdivs;

end;

第9页组合数枚举组合数枚举比全排列枚举轻易一些枚举从[1,n]整数中取出r个元素因为组合数是无序，所认为了枚举方便，我们不妨将枚举出来r个元素从小到大定序比如枚举从[1,4]整数中取出3个数，应该有以下4种情况：123134124234经过递归很轻易实现这一枚举，下面我们经过程序来说明第10页组合数枚举voidrecu(intk,intst){//还有k个数要枚举，开始枚举最小数为stif(k==0){output();return;}for(inti=st;i<=n-k+1;i++){//留下k-1个数给接下来枚举

a[r-k]=i;//枚举到第r-k+1个数为irecu(k-1,i+1);}}第11页组合数枚举procedurerecu(k,st:longint);beginif(k=0)beginoutput;exit;end;fori:=stton–k+1dobegin

a[r-k]:=i;recu(k-1,i+1);end;end;第12页来自预赛例题例题1(NOIP普及组)：书架上有4本不一样书A、B、C、D。其中A和B是红皮，C和D是黑皮。把这4本书摆在书架上，满足全部黑皮书都排在一起摆法有_____种。满足A必须比C靠左，全部红皮书要摆放在一起，全部黑皮书要摆放在一起，共有______种摆法。例题1解答：黑皮书排在一起方案有两种，黑皮书摆放位置有3种（2黑2红，1红2黑1红，2红2黑）红皮书相对位置方案有两种，所以能够得到第一问答案为2×3×2=12能够得到只有2红2黑这么一个摆法，而红书黑书相对位置是任意，所以第二问答案为2×2=4第13页来自预赛例题例题2(NOIP普及组)：小陈现有2个任务A，B要完成，每个任务分别有若干步骤以下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何时候，小陈只能专心做某个任务一个步骤。不过假如愿意，他能够在做完手中任务当前步骤后，切换至另一个任务，从上次此任务第一个未做步骤继续。每个任务步骤次序不能打乱，比如……a2->b2->a3->b3……是正当，而……a2->b3->a3->b2……是不正当。小陈从B任务b1步骤开始做，当恰做完某个任务某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其它都忘了。试计算小陈饭前已做可能任务步骤序列共有

种。第14页来自预赛例题例题2解答：因为A，B任务都是定好序，假设做完了k个B任务（不包含b1因为b1位置已经定死，则0<=k<=4)，那么问题等价于将3个a与k个B排成一排，问有多少种方案。那么怎样求将3个a与k个B排成一排方案数呢？等价于有3+k个位置，给这3个a安排3个位置，那么有C(3+k,3)种方案枚举k，得到答案为C(3,3)+C(4,3)+C(5,3)+C(6,3)+C(7,3)=C(8，4)=70第15页来自预赛例题例题3(NOIP提升组)：由3个a，5个b和2个c组成全部字符串中，包含子串“abc”共有（

）个。例题3解答：包含最少一个“abc”子串：即对1个“abc”，2个“a”，4个“b”，1个“c”进行排列，有C(8,1)×C(7,2)×C(5,4)×C(1,1)=840种方案不过包含两个“abc”子串字符串被计算了两次，所以需要减去对2个“abc”，1个“a”，3个“b”进行排列，有C(6,2)×C(4,1)×C(3,3)=60种方案所以答案为840–60=780第16页来自预赛例题例题4(NOIP提升组)：书架上有21本书，编号从1到21，从其中选4本，其中每两本编号都不相邻选法一共有______种。例题4解答：这题有各种方法，这里给出一个利用容斥原了解方法首先从21本书中取4本有C(21,4)

=5985种方案（取4本书）有（最少）一对书编号相邻有20×C(21–2,2)=3420种情况有两对书编号相邻有两种类型：一个是连着3本书，有19×(21–3)=342种情况；一个是分开着两对书，有C(19,2)=171种情况4个书编号相连情况有18种所以答案为5985–3420+(342+171)–18=3060第17页来自预赛例题例题4解答2：建立与18本书取4本一一映射关系18本书取出4本，再编号前3小书之后插入一个编号，并将新21本书从小到大编号，即成21本书取出4本不相邻编号书21本书取出4本不相邻编号书，删除前3本书编号之后那个编号，并将新18本书从小到大编号，即成18本书取出任意4本编号书答案为C(18,4)=3060第18页概率初步古典概型：P(A)=#A/#Ω例题1：硬币抛出正面概率是多少？硬币抛出后结果有两种情况（等可能），而正面是这两种情况之一，所以概率为1/2例题2：扔一枚骰子，扔出点数小等于2概率是多少？扔出后结果有6种情况，而小等于2占了其中两种，所以概率为2/6第19页概率初步例题3：同时扔两枚骰子，点数之和为6概率是多少？错误解法：扔出点数和结果可能为