14、信息学竞赛有关数学知识1

信息学竞赛有关数学知识1

一、加法原理：完成一件事情有n类独立完成方式，第I类方式有Mi种方法，则完成这件

事共有方法N=M1+M2+…+Mn

例1、 从杭州到北京每天直达火车有20个班次，飞机有10个班次，则每天从杭

州出发，中途不转到北京有几种方法？ 20+10=30

二、乘法原理：完成一件事情有n个步骤，第I个步骤有Mi种方法，则完成这件事共有方

法N=M1*M2*…*Mn

例2、某班外出活动，从20个男同学中选出1人当男组长，又从25个女同学中选出1人当女组长，选出的2个组长有几种可能？ 20*25=500 三、排列

1、 线排列：从N个不同的的元素中，取r个按次序排列。

总数为 p(n,r)=n(n-1)(n-2)…(n-r+1)=n!/(n-r)!

例3、确定各位数字不重复的四位八进制数的个数

8*7*6*5-7*6*5=210

2、 圆排列：从N个不同元素中，取出r个元素按照某种次序排成一个圆圈。

总数为 y(n,r)=p(n,r)/r=n!/((n-r)!*r)

例4、有8个人围圆桌就餐，问有多少种就坐方式？有两人不愿坐有一起，又有多

少种就坐方式？

P(8,8)/8=8!/8=7!

P(8,8)/8-2*p(7,7)/7=7!-2*6!

例5、4男4女围圆桌交替就坐有多少方式？

先排男，后排女：（4！/4）*4*3*2*1=144

3、 重排列

(1)无限重排列：从n个不同元素中取出r个按次序排列，若每个元素无限次重

复，则称为无限重排列，其排列数为Nr

例6、无线电收发机有“.” ,“-”(短、长)两种信号，用四个信号代表一个数

码，问可以表示多少个不同码？ 通用明码用0~9十位数码中的四个数码表示一个汉字，可以表示多少

个汉字？ 2^4=16

10^4=10000

(2)有限重排列：从n个不同元素中取出r个按次序排列，若允许元素有限次重复，则称为有限重排列。 特例：

m个元素有t种，每种个数bv分别为m1,m2,…,mt, m1+m2+…mt=m

将这M个元素按次序排成一排有几方案：

m!/(m1!*m2!*…*mt!)

例7、把4只红球，2只蓝球和1只白球放到编号不同的十个盒子中去的

方法总数是多少？ P(10,7)/(4!*2!)

C（10，7）*7！/（4！*2！）=P（10，7）/（4！*2！） C（10，4）*c(6,2)*c(4,1)

例8、某市区中有一处棋盘形街道，有南北方向街道（纵街）5条，东西方

向街道（横街）8条，某甲从东南角走到西北角，要按最短路径走（就是

只能向西或向北走），共有几种走法？

11！/（7！*4！）=330