棋盘多项式

✍ dations ◷ 2025-08-24 07:28:02 #组合数学

组合数学的核心是解决计数问题,其中很重要的即为n个元素的排列方案的计数。一个常见的将排列问题抽象的方法就是将其抽象为棋盘多项式。首先看一个 n × n {\displaystyle n\times n} 的棋盘,n个元素的排列可以看成在这个棋盘上落下n个棋子,其中每一个横行、每一个竖列只允许有一个棋子。而其中棋盘的格子是可以任意的 n × n {\displaystyle n\times n} 的棋盘的子集,这对应了存在一定限制的排列方案。

每一个棋盘对应着一个母函数代表该棋盘中描述无法攻击的棋子排列数。这个母函数即为棋盘多项式。

设C为一棋盘,称 k = 0 n r k ( C ) x k {\displaystyle \sum _{k=0}^{n}{r_{k}}(C){x^{k}}} 为C的棋盘多项式,其中 r k ( C ) {\displaystyle {r_{k}}(C)} 表示k个棋子布到棋盘C的方案数。

结合容斥原理解决受限排列问题。

r i {\displaystyle {r_{i}}} 为 i个棋子布入禁区的方案数,i =1,2,3,…,n。有禁区的布子方案数(即禁区内不布棋子的方案数)为 n ! r 1 ( n 1 ) ! + r 2 ( n 2 ) ! . . . + ( 1 ) n r n {\displaystyle {n!}-{r_{1}}{(n-1)!}+{r_{2}}{(n-2)!}-...+{(-1)^{n}}{r_{n}}}

设事件 A i {\displaystyle A_{i}} 为棋子 i {\displaystyle i} 落入禁区且其余棋子不限定是否落入禁区。那么布子方案数即可用 | A 1 ¯ A 2 ¯ A 3 ¯ A n ¯ | {\displaystyle |{\overline {A_{1}}}\cap {\overline {A_{2}}}\cap {\overline {A_{3}}}\cap \cdots \cap {\overline {A_{n}}}|} 进行表示。该排列数可以用容斥原理求解。即 | A 1 ¯ A 2 ¯ A 3 ¯ A n ¯ | = | A 1 A 2 A 3 A n ¯ | {\displaystyle |{\overline {A_{1}}}\cap {\overline {A_{2}}}\cap {\overline {A_{3}}}\cap \cdots \cap {\overline {A_{n}}}|=|{\overline {A_{1}\cup A_{2}\cup A_{3}\cup \cdots \cup A_{n}}}|} 其中,在棋盘上的不受限排列数为 n ! {\displaystyle n!} ,那么有

其中,至少有一个棋子落入禁区的方案数为 i = 1 n | A i | = r 1 ( n 1 ! ) {\displaystyle \sum _{i=1}^{n}|A_{i}|={r_{1}}(n-1!)} ,至少两个棋子落入进去的方案数为 | i = 1 n j > i A i A j | = r 2 ( n 2 ! ) {\displaystyle |\sum _{i=1}^{n}\sum _{j>i}A_{i}\cap A_{j}|={r_{2}}(n-2!)} ,以此类推,可以得到等式 | A 1 ¯ A 2 ¯ A 3 ¯ A n ¯ | = n ! r 1 ( n 1 ) ! + r 2 ( n 2 ) ! . . . + ( 1 ) n r n {\displaystyle |{\overline {A_{1}}}\cap {\overline {A_{2}}}\cap {\overline {A_{3}}}\cap \cdots \cap {\overline {A_{n}}}|={n!}-{r_{1}}{(n-1)!}+{r_{2}}{(n-2)!}-...+{(-1)^{n}}{r_{n}}}

1.如下图所示,在 4 × 4 {\displaystyle 4\times 4} 的棋盘上,打叉的地方为禁区,求棋子无一落入禁区的排列数。

首先通过排列多项式的性质得到禁区的棋盘多项式为 1 + 6 x + 11 x 2 + 7 x 3 + x 4 {\displaystyle 1+6x+11x^{2}+7x^{3}+x^{4}} 。这样,该棋盘在受限情况下的方案数为 4 ! 6 × 3 ! + 11 × 2 ! 7 × 1 ! + 1 = 4 {\displaystyle 4!-6\times 3!+11\times 2!-7\times 1!+1=4}

2.错排问题,即 n {\displaystyle n} 个元素组成的排列中标号为 i {\displaystyle i} 的元素不排在第 i {\displaystyle i} 位的方案数。

该问题即为受限排列问题。具体到棋盘中,即为在 n × n {\displaystyle n\times n} 的棋盘上,所有的对角线元素都是禁区。对于禁区的棋盘多项式的计算,由于该棋盘中所有元素均不在同一行同一列,根据棋盘多项式的性质容易得到为 ( 1 + x ) n {\displaystyle (1+x)^{n}} 。那么,根据受限排列的性质,得到错排方案数为 n ! C ( n , 1 ) ( n 1 ) ! + C ( n , 2 ) ( n 2 ) ! + + ( 1 ) n 1 C ( n , n ) {\displaystyle n!-C(n,1)(n-1)!+C(n,2)(n-2)!+\cdots +(-1)^{n-1}C(n,n)}

相关

  • HFO次氟酸指化学式为HOF的化合物。实际上,该名称并不准确,由于电负性的缘故,“次氟酸”中的氟仍为-1氧化态。参考其他含氟酸的名称,命名为“氟氧酸”似更为恰当。它可由水/冰以氟气
  • 汀州片本文属于客家系列的一部分汀州客语,或称客家语汀州片,是客家语的一个支系,主要分布在中国福建省西部的古汀州府区域。对于客家语的划分一般有两个版本,新的分片则加入不少福建客
  • 富时250指数富时250指数(FTSE 250 Index,/ˈfʊtsiː/ FUUT-see)是一个基于市值加权的指数,由伦敦证券交易所市值第101名至第350名的公司组成。指数的成分每季度决定一次,指数值实时计算。其
  • 苏联共产党中央政治局苏联主题苏联共产党中央政治局 (俄语:Политбюро ЦК КПСС,罗马化:Politbyuro TsK KPSS),1952至1966年间称为“苏共中央主席团”,为苏联共产党的中央决策和领导机构。
  • 322国道322国道(或“国道322线”、“G322线”)是在中国的一条国道,起点为浙江瑞安,终点为广西凭祥友谊关。这条国道经过浙江、福建、江西、湖南和广西5个省份。在国家公路网规划(2013年-2
  • 锝的同位素 锝(原子质量单位:98.9072(4))共有57个同位素,没有一种是稳定的。备注:画上#号的数据代表没有经过实验的证明,只是理论推测而已,而用括号括起来的代表数据不确定性。
  • 加州月桂加州月桂,又名伞桂,是属于樟科加州月桂属的一种大乔木。原产于美国加利福尼亚州的海岸森林,小部分延伸至俄勒冈州内,在俄勒冈州称它为俄勒冈香桃木(Oregon Myrtle)。加州月桂属,又
  • 联洋新社区联洋新社区是中华人民共和国上海市浦东新区花木街道下属的一个大型社区。有十多年的历史。其辖区范围为南邻花木路、北靠杨高中路、西起张家浜、东至罗山路,紧靠世纪公园,占地
  • 徐述虔徐经(1788年-1856年),原名徐荣,后更名徐述虔,再改名徐经,字桓生,号拜庚,上海嘉定人。 徐经自幼究心汉学,诗文俱有法度,与钱师康、毛岳生、葛其仁、陈瑑、庄尔保、黄穆之合称“嘉定七生
  • 骇客文化骇客文化(英语:Hacker culture),又译为黑客文化,是一种次文化,在程式员之中特别盛行。这种文化,鼓励重视智力与技术能力的个人,用创意来克服系统中的环境限制,做出杰出与亮眼的成果。