小弟我也来贴个有关问题，算是头脑风暴
我也来贴个问题，算是头脑风暴~
先上50分，如果有好的解答再加。
Q1：一个由m*n个方格组成的矩形，将其切割为若干个矩形，共有多少种切割方法？记方案数为f(m,n)，一个例子：
例如下面这个3*5的矩形切成右边这种形状就是一种方案，右边相同数字组成一个矩形
##### 11122
##### -> 34445
##### 34446
另有：完全不切割也算一种方案；不考虑旋转、翻转后的重复情况；定义f(0,n) = f(m,0) = 1
Q2：上承Q1，如果问题比较难的话，试求f(1,n)和f(2,n)
Q3：上承Q1，可能是Q1的中间步骤，也可能是扩展问题，即将m*n的矩形切割成k个子矩形有多少种切割方法？
记为f(m,n,k)
------解决方案--------------------
f(1,n)= C(1, n-1)+C(2, n-1)+...+C(n-1,n-1) = 2^(n-1)-1;
------解决方案--------------------
f(1,n)或f(m,1)可以当成是整数分拆的问题……
而且是有序的整数分拆：
http://courseware.ecnudec.com/zsb/zsx/zsx09/zsx096/zsx09601/zsx096011.htm
推广到f(m,n)可能会比较困难……
------解决方案--------------------
f(n,n)=f(1,n-1)*f(1,n)*2 = (2^(n-2)-1)*(2^(n-1)-1)*2
------解决方案--------------------
f(1,n)理解起来比较容易，就是n个块排成一列，有n-1个分割，从1个分割一直取到n-1分割。
------解决方案--------------------
先在矩形中任取一点，然后再取和第一点不同行，不同列的一点，就可以组成一个矩形，这样应该是
f{m,n} = m*n*(m-1)(n-1)/4
不知道是不是符合题意
------解决方案--------------------
n的有序k-分拆数是
k可以取的值为1、2、...、n
所以：
f(1,n)=C(n-1,0)+C(n-1,1)+...+C(n-1,n-1)=2^(n-1)
------解决方案--------------------
f(1,n)=C(n-1,0)+C(n-1,1)+...+C(n-1,n-1)=2^(n-1)
f(m,n)=[2^(n-1)]^m
------解决方案--------------------
又想了想，应该是:
f(n,m)=（f(n,m-1)+f(n,m-2))*f(1,n) n>=3。
解释一下我的想法：
原先是个n*(m-1)的矩阵，那么加一个1*n的矩阵，就变成了n*n。
所以至少有f(n,n-1)×f(1,n)。
在n*m的矩阵中，新增的1*n放在最右边（放在最左边是对称的）。即为第m列，其左边一列为m-1列。
m-1列内（不和其它列组成矩形）的每种分布，m列都会有一种情况和其对应，这时可以把m-1、m2列的行连接在一起，变成一个新的组合。
所以这又增加了f(n,m-2)*f(1,n)。
最后f(n,m)=（f(n,m-1)+f(n,m-2))*f(1,n) n>=3。
------解决方案--------------------
------解决方案--------------------
另(1+x)^n = C(0,n)+C(1,n)x+...+C(n,n)x^n. （10多年以前学的二项式展开定理）
上式可以简化为
f(n,m)=f(n,m-1)*f(1,m)+f(n,m-2)*(((1+2)^m)-1)/2
f(n,m)=f(n,m-1)*f(1,m)+f(n,m-2)*((3^m)-1)/2
有时间的话，写个程序验证一下。
上面的f(1,n)公式写错了，9楼的是对了。
------解决方案--------------------
f(3,2) 应该和 f(2, 3)相等
所以 [2^(n-1)]^m 这种结论不可能相等 因为2^3 != 3^2
------解决方案--------------------
------解决方案--------------------
关于[2^(n-1)]^m有以下的图（m=n=2）：
whg01的递推方法思路很好……
用m=n=2来验证是对的：
f(n,m)=f(n,m-1)*f(1,m)+f(n,m-2)*((3^m)-1)/2
f(2,2)=f(2,1)*f(1,2)+f(2,0)*((3^2)-1)/2【f(2,1)=2，f(1,2)=2，f(2,0)=1】
=2*2+(9-1)/2
=4+4=8
------解决方案--------------------
这题按楼上诸位的思路是无法解出来的，我找到了别人的研究成果，有一个公式可以计算，具体自己去看论文吧
http://www.math.lsu.edu/~verrill/research/rectangles.pdf
------解决方案--------------------
摘自论文中的部分结果，首行和首列分别对应n和m,如f(1,2) = 2 ,f(3,4)= 3164
1 2 3
1 1 2 4
先上50分，如果有好的解答再加。
Q1：一个由m*n个方格组成的矩形，将其切割为若干个矩形，共有多少种切割方法？记方案数为f(m,n)，一个例子：
例如下面这个3*5的矩形切成右边这种形状就是一种方案，右边相同数字组成一个矩形
##### 11122
##### -> 34445
##### 34446
另有：完全不切割也算一种方案；不考虑旋转、翻转后的重复情况；定义f(0,n) = f(m,0) = 1
Q2：上承Q1，如果问题比较难的话，试求f(1,n)和f(2,n)
Q3：上承Q1，可能是Q1的中间步骤，也可能是扩展问题，即将m*n的矩形切割成k个子矩形有多少种切割方法？
记为f(m,n,k)
------解决方案--------------------
f(1,n)= C(1, n-1)+C(2, n-1)+...+C(n-1,n-1) = 2^(n-1)-1;
------解决方案--------------------
f(1,n)或f(m,1)可以当成是整数分拆的问题……
而且是有序的整数分拆：
http://courseware.ecnudec.com/zsb/zsx/zsx09/zsx096/zsx09601/zsx096011.htm
推广到f(m,n)可能会比较困难……
------解决方案--------------------
f(n,n)=f(1,n-1)*f(1,n)*2 = (2^(n-2)-1)*(2^(n-1)-1)*2
------解决方案--------------------
f(1,n)理解起来比较容易，就是n个块排成一列，有n-1个分割，从1个分割一直取到n-1分割。
------解决方案--------------------
先在矩形中任取一点，然后再取和第一点不同行，不同列的一点，就可以组成一个矩形，这样应该是
f{m,n} = m*n*(m-1)(n-1)/4
不知道是不是符合题意
------解决方案--------------------
n的有序k-分拆数是
k可以取的值为1、2、...、n
所以：
f(1,n)=C(n-1,0)+C(n-1,1)+...+C(n-1,n-1)=2^(n-1)
------解决方案--------------------
f(1,n)=C(n-1,0)+C(n-1,1)+...+C(n-1,n-1)=2^(n-1)
f(m,n)=[2^(n-1)]^m
------解决方案--------------------
又想了想，应该是:
f(n,m)=（f(n,m-1)+f(n,m-2))*f(1,n) n>=3。
解释一下我的想法：
原先是个n*(m-1)的矩阵，那么加一个1*n的矩阵，就变成了n*n。
所以至少有f(n,n-1)×f(1,n)。
在n*m的矩阵中，新增的1*n放在最右边（放在最左边是对称的）。即为第m列，其左边一列为m-1列。
m-1列内（不和其它列组成矩形）的每种分布，m列都会有一种情况和其对应，这时可以把m-1、m2列的行连接在一起，变成一个新的组合。
所以这又增加了f(n,m-2)*f(1,n)。
最后f(n,m)=（f(n,m-1)+f(n,m-2))*f(1,n) n>=3。
------解决方案--------------------
------解决方案--------------------
另(1+x)^n = C(0,n)+C(1,n)x+...+C(n,n)x^n. （10多年以前学的二项式展开定理）
上式可以简化为
f(n,m)=f(n,m-1)*f(1,m)+f(n,m-2)*(((1+2)^m)-1)/2
f(n,m)=f(n,m-1)*f(1,m)+f(n,m-2)*((3^m)-1)/2
有时间的话，写个程序验证一下。
上面的f(1,n)公式写错了，9楼的是对了。
------解决方案--------------------
f(3,2) 应该和 f(2, 3)相等
所以 [2^(n-1)]^m 这种结论不可能相等 因为2^3 != 3^2
------解决方案--------------------
------解决方案--------------------
关于[2^(n-1)]^m有以下的图（m=n=2）：
whg01的递推方法思路很好……
用m=n=2来验证是对的：
f(n,m)=f(n,m-1)*f(1,m)+f(n,m-2)*((3^m)-1)/2
f(2,2)=f(2,1)*f(1,2)+f(2,0)*((3^2)-1)/2【f(2,1)=2，f(1,2)=2，f(2,0)=1】
=2*2+(9-1)/2
=4+4=8
------解决方案--------------------
这题按楼上诸位的思路是无法解出来的，我找到了别人的研究成果，有一个公式可以计算，具体自己去看论文吧
http://www.math.lsu.edu/~verrill/research/rectangles.pdf
------解决方案--------------------
摘自论文中的部分结果，首行和首列分别对应n和m,如f(1,2) = 2 ,f(3,4)= 3164
1 2 3
1 1 2 4