棋盘多项式

✍ dations ◷ 2024-12-23 11:00: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)}

相关

  • 范宁县范宁县(Fannin County, Georgia)位美国乔治亚州北部的一个县,北邻田纳西州和北卡罗莱纳州。面积1,014平方公里。根据美国2000年人口普查,共有人口19,798人。县治布卢里奇(Blue Ri
  • 温布利球场温布利球场(Wembley Stadium)是一个位于英格兰伦敦的温布利的专业足球场。球场拥有90,000个座位,容量为欧洲第二大,仅次于诺坎普球场,温布利球场上的天幕所占面积是全球第一大,看
  • 新海布里地板块新海布里地板块(New Hebrides Plate)是太平洋的小型板块,位于岛屿国家瓦努阿图附近,西南面的印度-澳洲板块沉入新海布里地板块。新海布里地隐没带在过去25年发生超过7级或以上的
  • 葛瑞·盖斯葛瑞·保罗·盖斯(英语:Gareth Paul Gates,1984年7月12日-),是英国创作型歌手。他是英国选秀节目Pop Idol第一届的亚军。盖斯的音乐专辑,在英国发行了超过350万张销售量。
  • 第十四第十四航空队(英语:Fourteenth Air Force),是美国空军太空司令部下属的一个编号航空队,指挥部位于加利福尼亚州的范登堡空军基地。该部队于1943年3月5日成立于中国昆明,为第二次世
  • 死魂灵《死魂灵》(有版本译作《死农奴》,俄语:Мёртвые души),是俄罗斯讽刺作家、喜剧家果戈理的主要代表作品。该书的第一卷出版于1842年,创作时间达七年之久;第二卷是在1852
  • 兰布尼 (阿拉巴马州)兰布尼(英文:Ranburne),是美国阿拉巴马州下属的一座城市。面积约为1.59平方英里(约合 4.11平方公里)。根据2010年美国人口普查,该市有人口409人,人口密度为257.88/平方英里(约合99.51
  • 马化龙马化龙(1810年-1871年),宁夏金积堡(今属吴忠)人。清代同治陕甘回变的主要领导人。领导了同治年间中国西北地区对汉族的种族屠杀。生于1810年,经名拖必尔图拉,道号赛义德·束海达依(意
  • 北川景子北川景子(英语:Kitagawa Keiko,日语:きたがわ · けいこ,1986年8月22日-),生于日本兵库县神户市中央区,身高160cm,日本女演员和模特儿,丈夫为日本音乐人Daigo。2003年末到2006年任日本
  • 格奥尔格二世 (萨克森-迈宁根)格奥尔格二世(德语:,1826年4月2日—1914年6月25日),萨克森-迈宁根公爵,1866年—1914年在位。1850年,格奥尔格与普鲁士的夏洛特公主(英语:Princess Charlotte of Prussia (1831–1855)