清华大学自招题改编的一道题

rayfekeeper

2021.3.3 (清华大学自招题改编)在方格中填入数字，要求:
①只能填入1或2;
②每行每列都至少填入1个数;
②每一行或每一 列的数字均为1、 2、1、2、1... (1和2交替出现，且首尾均是1，只有数字1也算符合要求)

问题1:如果放入4X4的方格中有多少种方法?
问题2:如果放入5X5的方格中有多少种方法?
（不可以翻转或旋转）

KeyTo9_Fans

这样枚举可行否？

4*4：

1000
0100
0010
0001

4!=24种

0100
1210
0100
0001

4*4=16种

0100
1210
0121
0010

2种

共计42种。

chyanog

相关数列：
1, 1, 2, 7, 42, 429, 7436, 218348, 10850216, 911835460, 129534272700, 31095744852375,......
http://oeis.org/A005130
把同构的算作一种
http://oeis.org/A181388

1. n = 5;
   
2. 
   
3. cond = Compile[{{a, _Integer, 1}},
   
4.    With[{t = DeleteCases[a, 0]}, Boole[t == {1} || t == {1, -1, 1} || t == {1, -1, 1, -1, 1}]],
   
5.    RuntimeAttributes -> {Listable}];
   
6. 
   
7. Tuples[{-1, 0, 1}, n] // RightComposition[
   
8.   Pick[#, cond@#, 1] &,
   
9.   Tuples[#, n] &,
   
10.   Pick[#, Times @@ Transpose@cond@Transpose[#, {1, 3, 2}], 1] &
    
11.   Length,
    
12.   AbsoluteTiming
    
13.   ]

复制代码

{0.975322, 429}

王守恩

KeyTo9_Fans 发表于 2021-3-4 12:31
这样枚举可行否？

4*4：

4*4：

1000
0100
0010
0001

4!=24种

0001   0010   0100   1000
0100   0121   1210   0010
1210   0010   0100   0121
0100   1000   0001   0010

4种

0010   0100
0121   1210
1210   0121
0100   0010

2种

共计24+4+2=30种。

王守恩

chyanog 发表于 2021-3-5 21:04
相关数列：
1, 1, 2, 7, 42, 429, 7436, 218348, 10850216, 911835460, 129534272700, 31095744852375,... ...

1, 2, 7, 42, 429, 7436, 218348, 10850216, 911835460, 129534272700, 31095744852375,... ...

太神奇了！这通项公式还可以这样写的！http://oeis.org/A005130——2021年3月4日

\(\D a(n)=\prod_{k=0}^{n-1}\frac{(3k+1)!}{(k+n)!}=\sqrt[3]{\frac{27^{n}\Gamma(n)\Gamma(n+1/3)^2\BarnesG(3n)\BarnesG(n+1)^3\ \ \ \ \ \ }{3\Gamma(1/3)^2\BarnesG(2n+1)^3}}\)

王守恩

一，主帖。在方格中填入数字，要求:
①只能填入1或2;
②每行每列都至少填入1个数;
②每一行或每一 列的数字均为1、 2、1、2、1... (1和2交替出现，且首尾均是1，只有数字1也算符合要求)

问题1:如果放入4X4的方格中有多少种方法?
问题2:如果放入5X5的方格中有多少种方法?
（不可以翻转或旋转）

二，主帖可以这样解读。
1，角格(4个角共4个)只能是：不填或填1
2，边格(周边的格，不包括角格)只能是：
     不填(角格填1)或填1(角格不填)
3，中格(不包括角格, 边格)只能是：
     从外往内数
     第1层最多填 1, 2, 1
     第2层最多填 1, 2, 1, 2, 1
     第3层最多填 1, 2, 1, 2, 1, 2, 1
     第4层最多填 1, 2, 1, 2, 1, 2, 1, 2, 1