清华大学自招题改编的一道题
本帖最后由 rayfekeeper 于 2021-3-4 12:07 编辑2021.3.3 (清华大学自招题改编)在方格中填入数字，要求:
①只能填入1或2;
②每行每列都至少填入1个数;
②每一行或每一 列的数字均为1、 2、1、2、1... (1和2交替出现，且首尾均是1，只有数字1也算符合要求)
问题1:如果放入4X4的方格中有多少种方法?
问题2:如果放入5X5的方格中有多少种方法?
（不可以翻转或旋转） 这样枚举可行否？
4*4：
1000
0100
0010
0001
4!=24种
0100
1210
0100
0001
4*4=16种
0100
1210
0121
0010
2种
共计42种。 本帖最后由 chyanog 于 2021-3-5 23:09 编辑
相关数列：
1, 1, 2, 7, 42, 429, 7436, 218348, 10850216, 911835460, 129534272700, 31095744852375,......
http://oeis.org/A005130
把同构的算作一种
http://oeis.org/A181388
n = 5;
cond = Compile[{{a, _Integer, 1}},
With[{t = DeleteCases}, Boole],
RuntimeAttributes -> {Listable}];
Tuples[{-1, 0, 1}, n] // RightComposition[
Pick[#, cond@#, 1] &,
Tuples[#, n] &,
Pick[#, Times @@ Transpose@cond@Transpose[#, {1, 3, 2}], 1] &
Length,
AbsoluteTiming
]
{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种。
本帖最后由 王守恩 于 2021-4-1 10:29 编辑
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{\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
页:
[1]