棋盘多项式

✍ dations ◷ 2025-04-03 11:32:33 #组合数学

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

相关

  • 血浆蛋白结合大多数药物可以与血浆中的蛋白质(如人血清白蛋白、脂蛋白、糖蛋白和α, β, γ 球蛋白)发生不同程度的结合。弱酸性药物主要与白蛋白结合,弱碱性药物除了与白蛋白结合外,还常
  • 异氰酸甲酯异氰酸甲酯(Methyl Isocyanate),是由光气(Phosgene)与甲胺(Methylamine)作用后合成的化学品,多用于制造农药。这种化学物,与Zyklon B一样亦曾用于在二次大战时屠杀犹太人,也是印度博帕
  • 登录登录可以指:
  • 屈家岭文化屈家岭文化是分布于中国长江中游地区的江汉平原的新石器时代文化,因最早在湖北京山屈家岭遗址发堀而得名。该文化影响范围较广,东到湖北东部的黄冈、鄂州,西至三峡地区,北到河南
  • 萧惟豫萧惟豫,字介石,山东德州人,清朝政治人物。顺治十五年(1658年)戊戌科进士,改庶吉士,授翰林院编修,历任翰林院侍读。著有《但吟草》。
  • 陈岱础陈岱础(1913年1月2日-),福建闽侯人,出生于上海,其父陈模为二次革命烈士。陈岱础从燕京大学毕业后赴欧美留学,获美国哥伦比亚大学政治学硕士、英国伦敦大学国际关系博士。后担任国民
  • GW150914GW150914是由激光干涉引力波天文台(LIGO)于2015年9月14日探测到的引力波现象,是人类首次直接探测到的引力波。相关探测结果由LIGO、处女座干涉仪(Virgo)研究团队于2016年2月11日
  • 翟一我翟一我(1921年12月19日-2007年11月15日),中国英语翻译家,记者,版权专家。翟一我学生时代曾就读于南开中学、武汉大学。曾在当时燕京大学的入学考试中取得第一名。先后在上海大公报
  • 宫城山福松宫城山福松(1895年2月27日-1943年11月19日),原名佐藤福松,日本岩手县西磐井郡(现在岩手县一关市)山目町出身的前大相扑力士,第29代横纲。身高174cm,重113kg,所属的相扑部屋是高田川部
  • 亚尔科·胡尔梅亚尔科·胡尔梅(芬兰语:Jarkko Hurme;1986年6月4日-)是一位芬兰足球运动员。在场上的位置是后卫。他现在效力于挪威足球超级联赛球队奥特足球俱乐部。他也代表芬兰国家足球队参赛