公司活动策划-殷墟博物苑

例1 染色问题: 设A、B、C、D为正方形的四个顶点（如图1.1）所示. 用r(红)，b(蓝)，
g(绿)三种颜色对它们染色，问有多少种染色方式及其方案数？
设P是染色对象的集合，R是颜色的集合，一种染色方式就是对P中每一对象安排一种色. 所
谓方案数是指某种染色方式的方案个数.
分析方法：因为每个顶点都有三种染色方案：或是红色，或是蓝色，或是绿色. 共有四个顶
点，所以染色方案总数为34=81.
各种染色方式及其方案数为:(r+b+g)4
=r4+b4+g4+6r2b2+6r2g 2+6b2g2+4r3b+4r3g+4rb3+4b3g+4rg3+4bg3+12r2bg+12rb2 g+12rbg2
展开式各项系数之和为81，刚好等于染色方案总数. 该展开式共有15项，说明 有15种染色
方式，每一项中的字母部分就是具体的染色方式，其前面的系数是属于这种染色方式的方案
数.
例2 求在1000到9000之间各位数字都不相同，而且由奇数构成的整数个数？

例1.3 从1000到9999的整数中, 问(1)含有5的数有多少个? (2)含有多少个百位和十位数均
为奇数的偶数? (3)各位数都不相同的奇数有多少个?
解 设有数字集合{0,1,2,3,4,5,6,7,8,9}.
(1) 先求不含5的整数的个数. 这时候个位数字,十位数字和百位数字各有9种选择, 而千位
数字只有8种选择, 所以不含5的整数的个数=8*9*9*9=5832, 从1000到9999共有9000个
整数, 所以含有5的的整数=9000-5832=3168.
(2) 当个位数字为0,2,4,6,8的时候对应的该整数为偶数, 因此个位数有5种选择, 十位数字
和百位数字各有5种选择,而千位数字有9种选择, 故含有个百位和十位数均为奇数的偶数
=9*5*5*5=1125.
(3) (3)当个位数字为1,3,5,7,9的时候对应数字为奇数. 如果要求各位数都不相同, 则个位数
有5种选择, 当个位数选定之后, 千位数只有8种选择, 而当千位数选择之后, 百位数可以有
8种选择, 以上三位数都选定之后,剩下的十位数就只有7种选择了. 所以, 从1000到9999
的整数中, 各位数字都不相同的奇数=8*8*7*5 =2240.
设有排列(p) =26385741, 按照字典式排序, 它的下一个排列是谁?
26385741->26387541->26387145
例2.3 设有排列(p) =2763541, 按照字典式排序, 它的下一个排列是谁?
(q) =2764135.
(1) 2763541 [找最后一个正序35]
(2) 2763541 [找3后面比3大的最后一个数]
(3) 2764531 [交换3,4的位置]
(4) 2764135 [把4后面的531反序排列为
135即得到最后的排列(q)]
母函数
若有1克的砝码3枚, 2克的4枚, 4克的2枚.问能称出哪些重量？各有几种方案？

G(x)(1xx
2
x
3
)

(1x< br>2
x
4
x
6
x
8
)(1x
4
x
8
)


1x2x
2
2x
3
3x
4
3x
5
4x
6
4x7

8910111213
5x5x5x5x4x4x


3x
14
3x
15
2x
16
2 x
17
x
18
x
19
.

已经母 函数
3-9x
，求对应的序列{
a
n
}
1-x56x< br>2
G(x)
39xAB(AB)(7A8B)x

< br>(18x)(17x)18x17x(18x)(17x)
A+B=3，7A-8B =-9, A=1, B=2
G(x)
12


18x1 7x
a
n
8
n
2(7)
n

丢掷四颗骰子，求出现的点数和为15的丢掷结果的种数。
解：以an记点数和为n的丢掷结果种数，则{an}的母函数为：
6
234564 4234544

1x

46121824
f(x)(xx xxxx)x(1xxxxx)x


1x


x(14x6x4xx)

4
(C(3,0)C(4,1 )xC(5,2)x
2
C(6,3)x
3
...)

a
15
C(14,11)4C(8,5)


指数性母函数
由1，2，3，4，5 ，6六个数字组成的n位数，求其中4，5出现偶数次，1，2，3，6出现
次数不限的数的个数an。
24


x
2
x
4
x
2< br>x
3


G
e
(
x
)


1
2!

4!


1x

2!

3!



2< br>

e
x

e

x

4< br>x
1
2
x
4
x
6
x

e< br>

e
2
e

e


24


n
1

nnn
x



(22 *46)
4
n
0
n
!

所以
an

1
n
(22*4
n
6
n
)< br>4

例1 由1，2，3，4，5五个数字组成的n位数，求其中4，5出现偶数次 ，1，2，3出现次
数不限的数的个数an。
解：{an}的指数型母函数为
23

2423

xxxx

G(x)< br>
1

1x
e

2! 4!2!3!


2


e
x
e
x

3x
1
x3x5x




ee2ee

2

4



1
nn
n

a1235

1
n
nn
x
4
1235

4
n0
n!

一个凸6边形, 通过不相交于6边形内部的对角线, 把6边形拆分成若干三角形, 不同拆分
的数目用h6表之.
hn+1=(1n)C(2n-2, n-1) h6=14
五边形有如下五种拆分方案, 故h5=5.

容斥原理(1)
8)证明:对任意给定的52个整数，存在其中 的两个整数，要么两者的和能被100整除，要么
两者的差能被100整除。
答：用100分别除这52个整数，得到的余数必为0, 1,„, 99这100个数之一。将余数是 0的
数分为一组，余数是1和99的数分为一组，„，余数是49和51的数分为一组，将余数是
50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分
在了同一 组，设它们是a和b。若a和b被100除余数相同，则ba能被100整除。若a
和b被100除余数 之和是100，则ba能被100整除。
求在1到1000的整数中不能被5,6,8中任何一个整除的整数的个数.


1000

1000


A
5
||

200,|
A

A
|33
56< br>

5

56



< br>1000

1000
|
A

A
|2 5,|
A

A

A
|8
8568
< br>5*8

[5,


5
8]120

6,

|166,|
A
8
|125,|
A
6

A
8
|41< br>
A
6
|
例：求在1到10000的整数中不能被4,5,6中任何一 个整除的整数的个数.
解：令Ai(i=4,5,6)表示1到10000的整数中能被i整除的数的个数，则
< br>
10000

10000

|A|2500,|A A|500
445



4

45



10000

10000


|A
4
A
6
|

833,|AAA|166
456


[4,6]12

[4,5,6]60
< br>

|A
5
|2000,|A
6
|1666,| A
5
A
6
|333

|A
4
I
A
5
I
A
6
|10000(|A
4
||A
5
||A
6
|)


|A
4
I
A
5
||A
4
I
A
6
||A
5
I
A
6
||A
4
I
A
5
I
A
6
|




5334

求由a,b,c,d四个字符构成的n位符号串中a,b,c,d至少出现一次的符号串的数目 。

n
|AAA|4A
1
A
2
 A
4124

nnn

n
4A
i
A
i
A
j
A
i
A
j
A
k


i1i1jii1jikj

n

(1)A
1
A
2
A
n
欧拉函数
例如n=60=2*2*3*5，则ψ（60）=60（1-12)(1-13)(1-15)=16
即比60小且与60互素的数有16个：
1，7，11，13，17, 19, 23，29，31，37，41，43，47，49，53，59。

棋盘多项式



有张、王、李、赵四位教师, 有数学、物理、化学、英语四门课程. 已知张不能教数学, 王
不能教物理和化学, 李不能教化学和英语, 赵不能教英语. 若使每位教师教各自承担力所能
及的一门课程, 问有多少种安排方案？

解 这个问题实际上是有禁位的排列, 其禁区就是刚才图中的阴影部分. 由上面的计算知道
图6.5中的禁区棋盘多项式为
1+6x+10x2+4x3
故有 r1=6, r2=10, r3=4, r4=0.
因此, 由公式(6.5), 所求安排方案数为:
Q4=4!-63!+102!-41!+00!=4.
鸽巢原理
令S是由6个正整数组成 的集合，其中最大的数不超过14，试说明如果将S的所有非空子
集中的元素分别加起来，则所得到的和 不可能彼此不同的。
S={a1,a2,a3,a4,a5,a6}
{a1},{a2},…{a6},
{a1,a2},{a1,a3},…,{a5,a6}
{a1,a2,a3},{a1,a2,a4},…,{a4,a5,a6}

…
{a1,a2,a3,a4,a5,a6}
对于每个子集，计算其和，记为Sum(k), k=1..64
如果Sum(k)互不相等，最多有64种取值可能。
取值范围：1<= Sum(k)<=9+10+11+12+13+14=69
初看有69种取值可能性，是否可以将取 值可能性缩减到63种，这样Sum(k),k=1..64中64
只鸽子，放在63各取值空间里，保 证存在k1,k2,使得Sum(k1)=Sum(k2)？
14+13+12+10+8+5=62
Möbius函数(m)的定义如下：


1,m1;



(m)

(1 )
k
,m是k个不同素数乘积,k1;


0，其他情形.


例如: 30=2*3*5, 121=112. µ(30)=(-1)3=-1,µ(121)=0.
欧拉函数
(n)n(d)d.

d|n





当m=2, n=6,T={a,b}时, 共有多少种个不同的圆排列？

序数法
逆：设p1p2...pn是任意一个n元排列, 则i+1后面比i+1小的数字的个数不超过i, 记为aii=1,2,…,n-1.
例如: 对n= 8 的排列A= 87132564, 排列A中2以后比2小的数的个数为0,记为a1= 0,同理
有a2= 1, a3= 0, a4=1, a5= 1, a6= 6, a7= 7,
例2.1 (1) 4213->(301)
4后面比4小的数的个数a3=3; 3后面比3小的数的个数a2=0; 2后面比2小的数的个
数a1=1.
(2) (301) ->4213
由a3=3知1,2,3都在4的后面; 由a2=0知1,2都在3前面; 由a1=1知1在2后面.
(3) (4213)<->(a3a2a1)=(301).