n*n的格子 组合问题

wayne

fans大牛。我拜服了

KeyTo9_Fans

使用动态规划算法求精确解，结果如下：

方案数模$2^64$，结果为$4918096979192578860$；

方案数模$2^64-1$，结果为$4918096979261591612$；

根据中国剩余定理，所求方案数为$1273060578884483984898786092$。

恰好在上述蒙特卡罗算法的近似值的置信区间内。

mathe

试试动态规划算法呀～

每添加$1$行，记录：

每列之和分别为$0000000000$的有几种方案；

每列之和分别为$0000000001$的有几种方案；

每列之和分别为$0000000002$的有几种方案；

每列之和分别为$000000 ...
KeyTo9_Fans 发表于 2012-9-12 19:51

" 各列之和"的状态数目相等于要数和为0的列的数目x0,和为1的列的数目x1,...,和为5的列的数目x5,满足
x0+x1+x2+x3+x4+x5=10的解的数目(总共10列)
而这个解的数目是$C_{10+6-1}^{6-1}=3003$呀
倒是每个状态出去的边的数目相当于$y0+y1+y2+y3+y4<=5$的解的数目，相当于$C_9^4+C_8^4+C_7^4+C_6^4+C_5^4+C_4^4=C_10^5=252$

mathe

5楼问题可以通过枚举定理做，计算出总数后，如果能算出每个初等变换不变量的数目即可应用公式。

mathe

且将所有满足要求的10×10矩阵组成集合记为S。S在第1类初等变换下是封闭的。所谓第1类初等变换，即只包含行交换和列交换的初等变换。
S中的2个矩阵如果可以通过行交换和列交换变来变去，就视为等价的。

现在，如 ...
hujunhua 发表于 2012-9-6 08:58

仅考虑行列交换，变换群为$S_10 *S_10$,不过还可以考虑镜像对称（也就是行变成列，列变成行），还需要乘上一个$S_2$

mathe

而这个题目如果也要考虑用Burnside's Lemma来做，我们需要计算在某个变换下保持不变的元素数目。
由于变换由行置换和列置换构成，其中行列置换都可以分解成一些不相交的轮换的乘积。首先我们需要把$S_10$分解成若干个轮换的不同情况都列出来，总数相当于$x_1+2x_2+3x_3+...+10x_10=10$的非负整数解数目，这个不是很大的数值，枚举即可，假设为N(应该小于100）,然后对于行和列的每个置换组合（有$N^2$)，我们查看所有轮换之间的配对，对应10*10中间一个小矩阵，比如行中一个长度为u和列中一个长度为v的轮换。如果(u,v)=1,那么是不变元必然要求这个小矩阵中所有元素都相等，要么都是0，要么都是1.而如果(u,v)=d>1,那么小矩阵中元素相当于被划分成d个等价类，所有等价类中元素取值都要相等。也就是我们需要计算一些情况更加复杂但是总数目更小的问题。这个问题应该需要穷举和动态规划相结合的方法，比如对于那些长度大的轮换，穷举比较快（通过等价类合并已经减少很多情况了），而对于小轮换，采用动态规划比较好，只是这时每次不应该添加1行而是添加轮换的长度对应的行。
当然，我们也可以采用另外一种方案来动态规划，也就是状态数不仅仅记录各列中1的数目，而同时包含行和列中1的数目（当然状态总数要爆增很多，但是应该还在可控范围），而动态规划每次添加一个等价类而不是一行了，而这个方法的好处是所有情况可以统一处理

hujunhua

$x_1+2x_2+3x_3+...+10x_10=10$的非负整数解如下：

1. In[1]:=FrobeniusSolve[Range[10],10]
   
2. Out[1]:={{0,0,0,0,0,0,0,0,0,1},{0,0,0,0,2,0,0,0,0,0},{0,0,0,1,0,1,0,0,0,0},{0,0,1,0,0,0,1,0,0,0},{0,0,2,1,0,0,0,0,0,0},{0,1,0,0,0,0,0,1,0,0},{0,1,0,2,0,0,0,0,0,0},{0,1,1,0,1,0,0,0,0,0},{0,2,0,0,0,1,0,0,0,0},{0,2,2,0,0,0,0,0,0,0},{0,3,0,1,0,0,0,0,0,0},{0,5,0,0,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,1,0},{1,0,0,1,1,0,0,0,0,0},{1,0,1,0,0,1,0,0,0,0},{1,0,3,0,0,0,0,0,0,0},{1,1,0,0,0,0,1,0,0,0},{1,1,1,1,0,0,0,0,0,0},{1,2,0,0,1,0,0,0,0,0},{1,3,1,0,0,0,0,0,0,0},{2,0,0,0,0,0,0,1,0,0},{2,0,0,2,0,0,0,0,0,0},{2,0,1,0,1,0,0,0,0,0},{2,1,0,0,0,1,0,0,0,0},{2,1,2,0,0,0,0,0,0,0},{2,2,0,1,0,0,0,0,0,0},{2,4,0,0,0,0,0,0,0,0},{3,0,0,0,0,0,1,0,0,0},{3,0,1,1,0,0,0,0,0,0},{3,1,0,0,1,0,0,0,0,0},{3,2,1,0,0,0,0,0,0,0},{4,0,0,0,0,1,0,0,0,0},{4,0,2,0,0,0,0,0,0,0},{4,1,0,1,0,0,0,0,0,0},{4,3,0,0,0,0,0,0,0,0},{5,0,0,0,1,0,0,0,0,0},{5,1,1,0,0,0,0,0,0,0},{6,0,0,1,0,0,0,0,0,0},{6,2,0,0,0,0,0,0,0,0},{7,0,1,0,0,0,0,0,0,0},{8,1,0,0,0,0,0,0,0,0},{10,0,0,0,0,0,0,0,0,0}}
   
3. In[2]:=%//Length
   
4. Out[2]=42

复制代码

共计42解

mathe

也就是说对于本题中hujunhua扩张的问题我们需要解决42^2=1764个问题

hujunhua

忽然觉得5楼的提问很搅，因为这根本就是两个不同的问题。等价类的划分自成问题，行（列）中1的数目限制并无实质性的意义。
想通过确定等价类的数目，以及每个类的大小然后去总计S的数目，根本就是笨方法。