棋盘多项式

✍ dations ◷ 2025-08-02 21:27:51 #组合数学

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

相关

  • (4-)4-氨基喹啉是喹啉环上4号位被氨基取代的有机化合物。4-氨基喹啉可以4-羟基喹啉为原料,经三氯氧磷将羟基转化为氯原子,再氨解得到。
  • 乳杆菌属见内文乳杆菌属(Lactobacillus)即为乳酸杆菌,是一群存在于人类体内的益生菌。乳杆菌因能够将碳水化合物发酵成乳酸而得名,可用于制造液态酸奶、固态奶酪、德国酸菜、啤酒、葡萄
  • 永定县坐标:24°49′0″N 116°46′0″E / 24.81667°N 116.76667°E / 24.81667; 116.76667永定区是中国福建省龙岩市下辖的一个区,位于福建省西南部,北纬24°23′-25°06′,东经116
  • 指代指代(coreference)为语言学中为了避免已经出现的字词重复出现在文章的句子上,导致语句结构过于赘述和语意不够清晰,所以使用代词(pronouns)或是普通名词(common nouns)来代替已经出
  • NHsub4/subOCl盐酸羟胺,化学式NH2OH·HCl。无色单斜结晶,易溶于水,溶于乙醇、甘油,不溶于乙醚。吸湿性强,受潮后逐渐分解。加热至151°C以上亦分解。氯化羟胺可以还原蓝色的铜氨溶液,生成无色的
  • 堂子堂子(满语:ᡨᠠᠩᠰᡝ,穆麟德:tangse)是满人祭天祭神的场所。早在清朝崛起之前,女真民间即设堂子。《两世罕王传》作侠倡唐舍,亦能称堂色、堂涩,乾隆朝始改定堂子为汉译,原称祭堂子为
  • 吉尔福德坐标:51°14′12″N 0°34′13″W / 51.236538°N 0.570309°W / 51.236538; -0.570309吉爾福德(Guildford,i/ˈɡɪlfərd/)是英国的一座城市,位于萨里郡。
  • 蓝吉富蓝吉富,(1943年-),台湾南投县人,佛教史学者 。毕业于东海大学历史系、历史研究所硕士班。著有《隋代佛教史述论》、《中国佛教泛论》、《二十世纪的中日佛教》、《佛教史料学》等
  • 德尔茨巴赫德尔茨巴赫(德语:Dörzbach)是德国巴登-符腾堡州的一个市镇。总面积32.36平方公里,总人口2434人,其中男性1213人,女性1221人(2011年12月31日),人口密度75人/平方公里。
  • 阮攸阮攸(越南语:Nguyễn Du/阮攸;1766年1月3日-1820年9月16日),字素如(越南语:Tố Như/素如) ,号清轩(越南语:Thanh Hiên/清軒),又号鸿山猎户(Hồng Sơn lạp hộ)、南海钓徒。诗人,作家。越南后