n*n的格子 组合问题

zgg___

5楼的问题很基本，很好的呀，呵呵。
答案在http://oeis.org/A002724

zgg___

对于5层的问题，感觉上，就是统计某个群的各个元素的置换循环的个数。
比如拿n=4的时候为例：
将4x4的方阵看成16个格子，依次标号。
这样行变换由g1=Cycles[{{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}}]和g2=Cycles[{{1,2},{5,6},{9,10},{13,14}}]生成，列变换由g3=Cycles[{{1,5,9,13},{2,6,10,14},{3,7,11,15},{4,8,12,16}}]和g4=Cycles[{{1,5},{2,6},{3,7},{4,8}}]生成。
这4个生成元（g1-g4）生成一个有576个元素的置换群g。
然后统计循环结的个数，例如：g1的循环结有4个，Cycles[{}]的循环结有16个。
结果如下：ss={{2,96},{4,204},{6,160},{8, 67},{10, 36},{12, 12},{16, 1}}。即：循环结有2个的一共有96个……
最后，Apply[Plus, Map[2^First[#] Last[#] &, ss]]/GroupOrder[g]可得到317的结果。
而当n比较大时，我还没算出。所以可以提出一个问题，即：已知一个置换群g（即已知g的生成元），统计出g的各个元素的循环结长度（即得到ss）。

zgg___

对于22层的最后提出的问题，如果置换群g很特殊，问题就简单些了。5层的问题中涉及的换群g就很特殊，它恰好是Sn乘Sn，是有(n!)^2个元素的群，于是分析其元素的循环结长度就有较有效的算法了，代码如下：

1. 
   
2. c1[s_]:=Map[{First[#],Length[#]}&,Split[Sort[s]]];
   
3. c2[s_,n_]:={s,n!/(Apply[Times,Map[Last,s]!]Apply[Times,Map[First[#]^Last[#]&,s]])};
   
4. c3[a_,b_]:=Module[{a1=First[a],b1=First[b],l},l=LCM[a1,b1];{l,a1 b1 Last[a]Last[b]/l}];
   
5. c4[s_]:={First[First[s]],Apply[Plus,Last[s]]};
   
6. c5[s_]:=Map[c4[Transpose[#]]&,Split[Sort[s],First[#1]==First[#2]&]];
   
7. c6[t1_,t2_]:=c5[Flatten[Outer[c3,t1,t2,1],1]];
   
8. c7[t1_,t2_]:={c6[First[t1],First[t2]],Last[t1]Last[t2]};
   
9. c8[s_]:={Apply[Plus,Map[Last,First[s]]],Last[s]};
   
10. c9[s_]:=c5[Map[c8,c5[Flatten[Outer[c7,s,s,1],1]]]];
    
11. ss[n_]:=c9[Map[c2[#,n]&,Map[c1,IntegerPartitions[n]]]];
    
12. Table[Apply[Plus,Map[2^First[#] Last[#]&,ss[n]]]/(n!)^2,{n,10}]
    

复制代码

其中函数ss返回22层提到的ss，最后输出21层提到的数列。如果矩阵不是方阵，这种算法也可以。
最后，5层问题的答案是105735224248507784。（22层的问题还存在，呵呵。）

zgg___

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

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

呵呵，刚才又看了一下前面的帖子，发现我没有看到5层帖子一开头的“且”字。所以，我21层至23层的帖子都没有考虑一层中的“并且每行每列1的数量不超过5个”的条件，呵呵呵……

litaoye

这个问题我只想了一个状态DP的方法，更深入的研究，靠ls诸位大牛了。

KeyTo9_Fans

25# litaoye

不错的算法。

状态是怎样的呢？

算法的时间复杂度是多少？

#####

我的是$3003$种状态，每种状态出去的边有$638$条，每条边的处理时间是$10$个基本运算，一共转移$10$趟，计算的复杂度是$3003*638*10*10=2e8$。