棋盘多项式

✍ dations ◷ 2025-04-04 11:25:23 #组合数学

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

相关

  • 肾上腺皮质激素肾上腺皮质激素(adrenocortical hormones)是由肾上腺皮质分泌的激素,不同于肾上腺髓质分泌的激素(如肾上腺素)。包括由肾上腺皮质外层的球状带分泌的盐皮质激素,由肾上腺皮质中层
  • 转译后修饰翻译后修饰(英语:Post-translational modification,缩写PTM;又称后翻译修饰)是指蛋白质在翻译后的化学修饰。对于大部分的蛋白质来说,这是蛋白质生物合成的较后步骤。PTM是细胞信
  • 植物组织培养植物组织培养是一种将植物体的部分细胞或组织与母体分离,在适当的条件下加以培养,使它们能够生长、发育、分化与增殖的技术。原理是来自植物细胞的全能性分化能力,也就是植物体
  • 斗门区斗门区是中国广东省珠海市下辖市辖区,曾经是县。斗门区政府驻地位于井岸镇,现任区委书记是周海金,区长是马洪胜。。斗门有很多赵姓的人,因为南宋时皇室曾逃难到这里。斗门区下辖
  • 希腊军队希腊军队(Military of Greece)、为希腊的武装军事力量,以维护国家领土完整与主权独立。其中包括四个组成部分:1.希腊国防参谋本部(Hellenic National Defence General Staff)2.希
  • 金锡玉金锡玉(韩语:김석옥/金錫玉  */?,1939年1月13日-),韩国女演员、配音员,生于日治朝鲜京城府。
  • 超显性超显性是指一对等位基因在异型合子(Heterozygote)中的表现型或生理功能超出其任一同型合子的现象。即假设A与a是一对等位基因,若基因型为Aa的个体的表现型比基因型为AA或aa更突
  • 阿克巴尔·甘吉阿克巴尔·甘吉(波斯语:اکبر گنجی‎,1960年1月31日-),生于加兹温省,是一位伊朗新闻记者和作家。他被描述为“伊朗的杰出持不同政见者” ,和“广受欢迎的民主派记者”,经常“
  • 艾利斯·哈利亚历山大·莫里·帕尔默·“亚历克斯”·哈利(英语:Alexander Murray Palmer "Alex" Haley,1921年8月11日-1992年2月10日),是一位美国作家。他最出名的作品是1976年出版的《根》和
  • 虎姓《百家姓》中无此姓虎姓为中文姓氏之一,是少见的姓,回族也有人此姓。云南虎姓回族人,可能买卖皮货衍生“与虎谋皮”负面感受,遂把姓氏虎音改读为猫,又有一说是虎年与虎姓相冲,虎要