文档文本内容
答 案
见解析
解析
证明：若
或，则项链数显然为．当
时，若粒不同珠子的两个圆排列仅有顺时针与
逆时针方向上的区别，则这两个圆排列对应的是同一副项链．故当
时，项链数应为对应的圆
排列数的一半，即为
．
答 案
见解析
解析
解：证明：显然
，
．当
时，不妨设排在了第位，其中
，也就是
．
当排在第位时，除了和以外还有
个数，其错排数为
．
当不排在第位时，那么将第位重新考虑成一个新的“第位”，这时的包括在内的剩下
个
数的每一种错排，都等价于只有
个数时的错排(只是其中的第位会换成第位)．其错排数为
．
所以当排在第位时共有
种错排方法，又有从到
共
种取法，我们可
以得到：
为书写方便，记
，则
．
．
当大于等于时，由
，即
．所以，
．
于是有
．
将上面式子分边系加，得
因此，我们得到错排公式
．
模块
模块1：
1
1
例题1
n = 1
2
1
n ⩾3
n
n ⩾3
n −1 !
2
1 (
)
例题2
D
=
1
0
D
=
2
1
n ⩾3
n
k
k=
n
/
1 ⩽k ⩽n −1
k
n
n
k
n −2
D
n−2
k
n
n
k
k
n −1
n −1
k
n
D
n−1
n
k
D
+
n−2
Dn−1
k
1
n −1
n −1
D
=
n
n −1
D
+ D
(
) (
n−1
n−2)
D
=
n
n!M
n
M
=
1
0
M
=
2
2
1
n
3
D
=
n
n −1
D
+ D
(
) (
n−1
n−2)
n : M
=
n
n −1
n −1 !M
+
(
) (
)
n−1
n −1
n −2 !M
=
(
) (
)
n−2
n!M
−
n−1
n −1 !M
(
)
n−1
nM
−
n
nM
=
n−1
−M
+
n−1
M
n−2
M
−
n
M
=
n−1
−
M
−M
=
n
1 (
n−1
n−2)
⋯=
−
−
⋯
−
M
−M
(
n
1 ) (
n −1
1
)
(
3
1 ) (
2
M
=
n
−1
+
(
)2
2!
1
−1
+
(
)3
3!
1
⋯+ −1
(
)n
n!
1
D
=
n
n!M
=
n
n!
−
+ ⋯+ −1
( 2!
1
3!
1
(
)n
n!
1 )
答 案
见解析
解析
解：将正
边形的顶点沿顺时针方向标号为，，
，
．对以，，为顶点的三角形，定义
，之间的距离为，之间(不含的一侧)正
边形的边数．显然，一个三角形顶点间的个距离之
和为
，其中最小距离不大于
．
当最小距离为偶数
时．中间距离不
小于
且不大于
．这时共有
个
互不全等的三角形；
当最小距离为奇数
时，中间距离不小于
且不大于
，这时共有
个互不全等的三角形．由
，
得互不全等的三角形个
数为
(个)．
答 案
见解析
解析
解：当
时，原方程变为
．
此时，方程的非负整数解的组数是
．
当
时，原方程变为
．
此时，方程的非负整数解的组数是
当
为大于或等于的整数时，产生矛盾．
因此，原方程的非负整数解的组数是
．
1
1
1
例题3
6n
1
2
⋯
6n
i
j
k
i
j
i
j
k
6n
3
6n
2n
1
( )
2k k = 1, 2, ⋯, n
(
)
2k
6n −2k =
2
1 (
)
3n −k
3n −k −
(
)
2k −1 =
(
)
3n −3k + 1
2
( )
2k −1 k = 1, 2, ⋯, n
(
)
2k −1
6n −2k −1
=
[2
1 (
(
))]
3n −k
3n −k −2k −2 =
(
)
3n −3k + 2
1
( )
2
( )
m =
3n −3k + 1 + 3n −3k + 2 =
k=1
∑
n
(
)
6n −6k + 3 =
k=1
∑
n
(
)
6n −
2
6 ⋅
+
2
n n + 1
(
)
例题4
x
=
1
0
x
+
2
x
+
3
⋯+ x
+
9
x
=
10
3
C
=
9+3−1
3
C
11
3
x
=
1
1
x
+
2
x
+
3
⋯+ x
+
9
x
=
10
1
C
=
9+1−1
1
C
9
1
x1
2
C
+
11
3
C
=
9
1
165 + 9 = 174
例题5
答 案
见解析
解析
解：对于正整数，设
，其中
，则称
为正整数的一个
分拆，的所有
分拆的个数称为的
分拆数，记为
．则
则
同理可得
所以
．
答 案
见解析
解析
解：掷硬币所得结果序列可看作是一系列反〔记为(反)〕，正〔记为(正)〕的组合，其次，每一
个“正反”〔记为(正)反〕，“反正”〔记为(反)正〕，因为在掷硬币十五次的结果序列中，“正反”或“反
正”只涉及到括号和括号之间的关系，而与括号内的正的个数或者反的个数无关．
由此可得，满足我们所要求的每个这样的结果序列必有这种形式
(反)(正)(反)(正)(反)(正)(反)(正)
其中有个“正反”，个“反正”．
我们考虑
式的各个组合中，反，正的位置，以便保证每个序列将有个“正正”，个“反反”的顺
序，为了这个目的，假定在
式中最初每个组合只含有一个元素，然后，为满足所求问题的条
件，放个正在(正)里，放个反在(反)里，为此，必须计算方法种数，达到解决问题目的．
根据只相同颜色的球放到个编号不同的盒子中去，在每个盒子中，我们愿意放多少就可以放多少
只球，那么放球的方法种数是
．
在本题的情况下，意味着将个正放到个(正)里，有
(种)；将个反放到个(反)里，
有
(种)．
所以
(种)．
1
1
n
n = n
+
1
n
+
2
⋯+ n
r
n
⩾
1
n
⩾
2
⋯⩾n
⩾
r
1
n
, n
, ⋯, n
(
1
2
r)
n
r−
n
r−
n
r−
p
n
r ( )
p
n =
1 ( )
1
p
n =
2 ( )
[2
n]
p
n =
3 ( )
[
12
n + 3
2
]
⋯
p
n =
r ( )
p
n −r
k=1
∑
r
k (
)
p
20 =
5 (
)
p
15 +
1 (
)
p
15 +
2 (
)
p
15 +
3 (
)
p
15 +
4 (
)
p
15 =
5 (
)
1 + 7 + 19 + p
15 +
4 (
)
p
p
15 =
4 (
)
p
11 +
1 (
)
p
11 +
2 (
)
p
11 +
3 (
)
p
11 =
4 (
)
1 + 5 + 10 + 11 = 27
p
10 =
5 (
)
1 + 2 + 2 + 1 + 1 = 7
p
15 =
5 (
)
30
p
20 =
5 (
)
1 + 7 + 19 + 27 + 30 = 84
例题6
∗
( )
3
4
∗
( )
2
5
∗
( )
2
5
r
n
Cn+r−1
r
2
4
C
=
4+2−1
2
10
5
4
C
=
4+5−1
5
56
10 × 56 = 560
例题7
答 案
见解析
解析
解：我们先把这
个人从低到高排列，然后，选择个人排在第一排，那么剩下的个肯定是在第
二排．用表示对应的人在第一排，用表示对应的人在第二排，那么含有个0，个的序列，就
对应一种方案．
比如
就对应着第一排：
，第二排：
．
就对应着第一排：
，第二排：
问题转换为，这样的满足条件的
序列有多少个．
我们发现的出现前边必须有一个相应的对应，所以从左到右的所有序列中的个数要一直大于
的个数．这就是卡特兰数
．
答 案
见解析
解析
解：对应
模型．注意到观众不同，对拿两种纸币的观众分别进行排列，最终结果
．
答 案
见解析
解析
解：显然满足卡特兰数递推关系．
．
答 案
见解析
解析
解：如果由一个城市可以直接飞往另一个城市，就称相应的空中航线为短
途航线；如果中途需中转一次才能飞到，就称为长途航线．将城市编号，并用
表示由号城市
所连出的航线数目．对于短途航线，我们都在其起点处统计其条数，而对
于“长途航线”，则在进行中转的城市统计其条数．这样一来，如果自一个城市连出了条航线，那
么在该城市就会统计为：有条短途航线和
条长途航线(因为个与其有航线相连的城市
中，每两个城市之间都有双向的可在该城市中转的长途航线)，于是共有
条航
线．如此一来，航线总数为
．由于的任何次幂被除
1
1
1
12
6
6
0
1
6
6
1
000000111111
012345
67891011
010101010101
0246810
1357911
01
1
0
0
1
C
6
例题8
Dyckword
n!
C
(
)2
n
例题9
C
6
例题10
2ni
i
i = 1, ⋯, 2000
(
)
x
x
x x −1
(
)
x
x + x x −1 =
(
)
x2
2
+
2n
1
⋯+ 2
=
2n
2000
4
+
n
1
⋯+ 4π
2000
4
3
的余数都是，所以航线总数被除的余数与
相同，即等于；但是，
被除的余数却
等于．所以统计员统计有误．
答 案
不能表示为一个完全平方数与一个完全立方数之和的数较多．
解析
解：以
表示全体正整数之集．令
，其中，，
，且
．显
然，此时有
和
．所以，这种令我们感兴趣的表达式不会多于
个数对
．而可以表示为一个完全平方数与一个完全立方数之和的数的数目比这种数对的数目还要
少，因为其中有些数对所表示出的已经大于
，而且还可能有些不同的数对表示出相同的
．
1
1
3
2000
2
100000
3
1
例题11
N
n = k +
2
m3
n
k
m ∈N
n ⩽1000000
k ⩽1000
m ⩽100
105
k, m
(
)
n
n
1000000
n
