棋盘多项式

✍ dations ◷ 2025-04-26 13:56:45 #组合数学

组合数学的核心是解决计数问题,其中很重要的即为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)}

相关

  • NEMA美国电气制造商协会(National Electrical Manufacturers Association),简称NEMA,是美国电气设备及医学影像制造商组成的协会,在1926年创立,总部在华盛顿附近的维吉尼亚州罗斯林(英
  • 小舌挤喉音(Uvular ejective)是辅音的一种,用于一些口语中。表示此音的国际音标(IPA)是⟨qʼ⟩。小舌挤喉音的特征包括:几乎所有的东北高加索语系、南高加索语系与部分德内语支的
  • 半次元浙江省杭州市滨江区长河街道南环路1672号4幢513室 (登记注册地址) 浙江省杭州市滨江区滨和路998号中赢国际505(实际办公地址)半次元是王耀网络旗下运营的一个定位于二次元爱好
  • 战地风云3《战地3》(英语:Battlefield 3)是由DICE制作、艺电发行的一款第一人称射击游戏。游戏采用了新一代的寒霜2引擎,展现了更强大的3D细节效果,把动画、环境破坏、光照、地图和音效提
  • 杭州亚运会第十九届亚洲运动会(英语:Hangzhou 2022 Asian Games)将于2022年9月10日至25日在杭州举行,原定于2012年11月3日举行的亚奥理事会全体大会上连同2018年亚运会主办城市一并表决,但
  • 对丁基苯胺对丁基苯胺,又称4-正丁基苯胺或4--正丁基苯胺(英语:4-Butylaniline),是一种有机化合物,属于芳香胺类化合物,常温下为黄色液体,有氨的难闻气味,不溶于水,但溶于醇、醚、酮、卤烃、苯等
  • ISUCA依丝卡电视动画宣传图《ISUCA依丝卡》(日语:イスカ)是高桥脩的日本青年漫画作品,于〈YOUNG ACE〉2009年Vol.1中开始连载。2012年改为隔月连载。2014年6月决定改编成电视动画,同年10月宣
  • 田中亚弥田中亚弥(たなか あや、1979年7月30日-)是日本的AV女优。出身于日本山口县周南市。田中亚弥亦是他的本名。徳山女子短期大学经营情报学科肄业。
  • 国家行为国家是国际关系中最重要的行为者,其构成要素为人民、领土、主权政府及外交之能力。人口是基本要件,但人口的多寡将影响到国家能力,而人民的品质也是影响国力之要素。领土是国家
  • Keroro军曹商品列表Keroro军曹商品列表为动漫作品《Keroro军曹》周边商品的介绍,漫画及动画DVD除外。