申请免费qq-好段摘抄200字

2021年1月6日发(作者：路锦程)

棋盘多项式

棋盘多项式是解决一类计数问题的一个强有力地组合数学工具. 本讲我们的目的要理解什么叫棋
盘，棋盘多项式的定义和性质，以及如何计算棋盘多项式.至于如何运用 棋盘多项式解决计

数问题，将排在后续的课中.


棋盘

考虑这样一个计数问题：要将桃、梨、李、桔四种水果各 1 个，分给 A、B、C、D 四个小朋
友，每个小朋友恰好分得 1 各水果.其中 A 不要李，B 不要李和桃，C 不要桔.那 么符合要求的
分法共有多少种？该问题本身是简单的，可以用多种方法求解.这里我们并不打算解决这个 问
题，而是将该问题转换成另一种表达形式.

如图 1，作一个4  4 的表格，一个朋友拿了某个水果

就在相应的行和列的交叉处打上“√”.则分水果的每一种

方案，就等价于在这个表格上打 4 个“√”的一种方案.

根据问题的要求可知：“√”不能打在阴影方格中，并且

任何两个“√”都不能同行或者同列.

称允许打“√”的全体方格为问题容许棋盘，简称棋盘.例如图 2 即为上述问题的棋盘.

以后则将“√”称为棋子，且总是约定（且不再申明）：棋盘上任意一行或者一列，都最多只

能放入一枚棋子.基于显而易见的理由，这个约定有时也被称作“车不互吃原则”.

因而，上述问题可以重新表述为：在图 2 所示的棋盘中放入 4 枚棋子的方法有多少种？一般

来说，所有的限位问题都可以像这样转化为在棋盘放棋子的问题.

为了理论上的方便，允许棋盘不包含任何方格，这样的棋盘称为空棋盘，记作∅ .
棋盘多项式

棋盘多项式的定义：对任意棋盘
C


∅ ，记在棋盘 C 上放入 K 枚棋子的方案总数为r
k
(C) ，
其

中k  1,2,3 ，称

234
R(C)  1 r
1
(C)x  r
2
(C)x  r
3
(C)x  r
4
(C)x 

为棋盘 C 的棋盘多项式，简称棋盘 C 的多项式.并规定 R (∅ )=1.

例如，若棋盘 C=




，通过简单的分析易知：在 C 上放入 1 枚棋子的方案共有 5 种，放入
2 枚棋子的方案共有 4 种，放入 3 枚或 3 枚以上的棋子的方案都为 0 种.因而
r
1
(C)  5 , r
2
(C)  4, r
3
(C)  r
4
(C) 

0.R()  1 5x  4x .
2
由上面的例子可以看出，在棋盘多项式的定义中，虽然形式上有无限项相加，但从某一项起
都为 0，即实质上仅为有限项相加.

练习题 1.根据棋盘多项式的定义，写出下列棋盘的多项式.

(1)













(2) (3)
展开定理和分离定理
如果只能通过定义来求棋盘多项式，那么可想而知，棋盘多项式的概念也就毫无用武之地了.

实际上，棋盘多项式有一些重要的性质，可以用来计算更复杂的棋盘的棋盘多项式.

定理 1（展开定理）.对任意棋盘
C


∅ ，在 C 中任意选定一个方格，设棋盘C
i
是将棋盘 C 中

与选定的方格同行 或同列放入所有方格（包括选定的方格本身）都去掉之后剩下的棋盘，棋盘C
e

是将 C 中仅去掉选定的方格之后剩下的棋盘.那么 R(C)  xR(C
i
)  R(C
e
) .

定理 2（分离定理）.若在棋盘C
1
和棋盘C
2
各任取一个方格，取出的两个方格都既不同行也不

同列，那么称C
1
和C
2
是分离的或独立的.若棋盘 C 由两块棋盘C
1
和C
2
组成，并且C
1
和C
2
分
离，

那么 R(C)  R(C
1
)R(C
2
) .

一些说明：

1、以图 3 的棋盘 C 为例，若在该棋盘上选定一个方格（即其中标有黑点的方格），则由此

得到的棋盘C
i
和C
e
如图 3 所示.















2、“分离”一词不可望文生义，不能理解为两块棋盘没有挨在一起.例如图 2 的棋盘虽然
由两块没有挨在一起的棋盘组成，但这两块并不分离.实际上，在英文文献里，这里用的是
indenpent 一词，因而翻译为“独立（互不影响）”是更准确的.

3、这里不打算严格证明这两个定理（可以参考课后作业 6 和 7），但给出相对通俗而啰
嗦的解释.实际上，这两个定理的实质不过是加法原理和乘法原理，以及多项式的运算法则（即
所谓拆括 号、合并同类项等）.

首先看定理 1，要说明 R(C)  xR(C
i
)  R(C
g
) ，只需要说明 R(C) 和 xR(C
i
)  R(C
g
) 这两个多

项式 x 项的系数、x 项的系数、x 项的系数....分别对应相等，以 x 项的系数为例，R(C) 的 x 项

2344
的系数（即r
4
(C) ）表示棋盘 C 中放入 4 枚棋子的方案数目，这些方案可以分为两类：一类是有

1 枚棋子放在黑点（以图 3 为例）所在的方格，另一类是 4 枚棋子都不放在黑点所在的方格.对


于前一类，还有 3 枚棋子需要放入棋盘C
i
，因而这一类的方案数目为r
3
(c
i
) ，即 R(C
i
) 的 x 项的
系数，它进一步等于 xR(C
i
)的x 项的系数，对于后一类，4 枚棋子都应要放入棋盘C
e
，因而这一类
的方案数目为r
4
(C
e
),即R(C
e
)的x 项的系数.所以，根据加法原理， R(C
e
)的x 项的系数，等于
xR(C
i
)的x 项的系数与 R(C
e
)的x 项的系数与 R(C
e
)的x 项的系数之和，即等于 xR(C
i
)  R(C
e
) 的
444
44
4
3
x 项的系数，一般的， R(C)和xR(C )  R(C ) 同次项的系数都相等，即 R(C)  xR(C )  R(C ) .
对于定理 2，可以作类似的解释.同学们，你能结合例子进行解释吗？


4

棋盘的等价

称对称棋盘的以下 3 中操作为等价操作：（1）交换任意两行的所有方格（但保持每个方格

所在的列不变），或者交换任意两列的所有方格（但保持每个方格所在的行不变）；（2）去掉

任意一空行（即没有方格的行）或空列；（3）将棋盘顺时针或逆时针旋转 90°摆放.

如果棋盘C
1
能够经过有限等价操作变为棋盘C
2
，则很显然C
2
也能够经过有限步等价操作变

为C
1
，此时，称棋盘C
1
和C
2
是等价棋盘，或者称C
1
和C
2
等价.









例如，以下 3 个棋盘C
1
、C
2
、C
3
两两等价，但都不与棋盘C
4
等价.
对任意两个棋盘C
1
和C
2
，若C
1
和C
2
等价，则易证：对任意k  1,2,3 ，有r
k
(C
1
)  r
k
(C
2
) .

进而显然有：






定理 3.对任意两个棋盘C
1
和C
2
，若C
1
和C
2
等价，则 R(C
1
)  R(C
2
) .
根据性质计算棋盘多项式

对于简单的棋盘，可以直接通过定义写出它的棋盘多项式，而运用定理 1~3，则可以将求复

杂棋盘的棋盘多项式转化为求若干简单棋盘的棋盘多项式.





练习题 2.求











棋盘的多项式

练习题 3.求





的空白部分的棋盘多项式.
练习题 4.求







棋盘的多项式
思考题

试运用棋盘多项式证明二项式定理：对任意a和b ，以及正整数 n，有





(a  b)  a  c
n
a
nn2n1
b 

c
n
n1
ab
n1
.
课后作业.
求棋盘 1~4 的多项式.

1、







2、
3、









4、

5、画出下述问题的棋盘，并求出它的棋盘多项式.


将四种水果桃、梨、李、桔各 1 个分给四个小朋友 A、B、C、D，已知 A 不要桔，B 不要桃，C
只要李或桃，D 只要桔.










6、在定理 1 中，证明:对任意k  1,2,3
, 有r
k
(C)  r
k

1
(C
i
)  r
k
(C
e
) .











7、在定理 2 中，证明：对任意k  1,2,3 , 有 r
k
(C)  r
k
(C
1
)  r
k1
(C
1
)r
1

(C
2
)  r
k

2
(C
1
)r
2
(C
2
)  r
1
(C
1
)r
k1
(C
2
)  r
k
(C
2
)

中国女排夺冠-数米粒

基督教对联-儿童节黑板报

毛笔字帖-七律长征教学反思

好听的手机信息铃声-护士简历表格

四面楚歌的近义词-郭沫若屈原

会议会务-辅导班招生广告

审时度势的拼音-大学英语精读第二册

虎门唐会-洋洋得意