定理
设 为 i个棋子布入禁区的方案数,i =1,2,3,…,n。有禁区的布子方案数(即禁区内不布棋子的方案数)为
定理证明
设事件 为棋子 落入禁区且其余棋子不限定是否落入禁区。
那么布子方案数即可用 进行表示。该排列数可以用容斥原理求解。
即
其中,在棋盘上的不受限排列数为 ,那么有
-
其中,至少有一个棋子落入禁区的方案数为 ,至少两个棋子落入进去的方案数为 ,以此类推,可以得到等式
举例
1.如下图所示,在 的棋盘上,打叉的地方为禁区,求棋子无一落入禁区的排列数。
首先通过排列多项式的性质得到禁区的棋盘多项式为 。
这样,该棋盘在受限情况下的方案数为 。
2.错排问题,即 个元素组成的排列中标号为 的元素不排在第 位的方案数。
该问题即为受限排列问题。
具体到棋盘中,即为在 的棋盘上,所有的对角线元素都是禁区。
对于禁区的棋盘多项式的计算,由于该棋盘中所有元素均不在同一行同一列,根据棋盘多项式的性质容易得到为 。
那么,根据受限排列的性质,得到错排方案数为 。