n*n的格子 组合问题

wayne

10*10个格子，格子里面的数为0或1，并且每行每列1的数量不超过5个，这样的组合有多少种？
http://www.51nod.com/question/index.html#!questionId=554

刚吃完

这题我怎么好像见过。好像是组合数学里的。

sunwukong

不考虑对称性
$(C_10^0+C_10^1+C_10^2+C_10^3+C_10^4+C_10^5)^10$

sunwukong

没注意题目中，“每行每列”的限制，上面的回答错了。

题目可以转化为：

15×15个格子，格子里面的数为0或1，并且每行每列1的数量都是5个，求组合数。

hujunhua

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

现在，如果要求计数时消除等价重复，共有多少个满足要求的解？

wayne

5# hujunhua
额,这么简化难度应该更大了吧.

hujunhua

呵呵，难度可能会更大，但是数值大为变小，我觉得更精炼，更好看。
我不大喜欢那种爆炸式增长的数列，没几项就长得没边、超出人脑的想象力，就没什么感觉了。

上古猿人对超出3的数字就觉得茫然了，可怜我也强不了多少。

hujunhua

第1类初等矩阵共有10!个，构成10阶置换群，且记为G。GS（左乘）为行变换，SG（右乘）为列变换，GSG为混合变换。

对于S中的非奇异矩阵s, |Gs|=|sG|=10!, 但是|GsG|<=10!². 所以消除等价重复的过滤率应该在10!~10!²之间。

KeyTo9_Fans

试试动态规划算法呀～

每添加$1$行，记录：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

……………………………………………………

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

每列之和分别为$5555555555$的有几种方案。

最多有$6^10$个不同的“每列之和”。

算法的时间复杂度分析：

一共要添加$10$行，对于每$1$行：

有$C(10,0)+...+C(10,5)=638$种添加方案，对于每种添加方案：

最多更新$6^10$种“每列之和”的方案数。

所以该算法的时间复杂度是$10\times 638\times 6^10$，

空间复杂度是$6^10\times 100bits$。

KeyTo9_Fans

使用蒙特卡罗算法求近似值，结果如下：

方案数为$(1.2729\pm 0.0004)e+27$，置信度为$95%$

或者

方案数为$(1.2729\pm 0.0006)e+27$，置信度为$99.5%$