一个简单的计数问题

medie2005

十六个不同高度的人前后排成四排，每排四人，要求后面的比前面高，左边的比右边的高，问你有几种排法？

到处瞎逛

如果有这样的两个要求的话，估计只有一种排列方法。

nlrte13

............................ 4个数两排，就有2种排列了

nlrte13

我算的结果是 24024 种排列

nlrte13

14 * 13 * 12 * 11

nlrte13

2*2的方块有 2*1 种 3*3的有 7*6种 4*4的有 14*13*12*11种 5*5的有 23*22*21*20种 6*6的有 34*33*32*31*30*29种 …………

数学星空

6# nlrte13 不知是否是编程计算出来的?? 若计算无误,通过观察可得到(设f(n)为满足上题条件的n*n方阵数目) $f(2n)=prod_{k=0}^{2n-1}(4n^2-2n-1+k)$ $f(2n+1)=prod_{k=0}^{2n-1}(4n^2+2n+k)$

mathe

http://www.research.att.com/~nja ... =0&language=english

2. #include <map>
3. using namespace std;
4. #define M 5
5. class key{
6. int d[M];
7. public:
8. key(int v[M]){
9. int i;
10. for(i=0;i<M;i++)d[i]=v[i];///non-increasing sequence required.
11. }
12. bool operator<(const key& k)const{
13. int i;
14. for(i=0;i<M;i++){
15. if(d[i]<k.d[i])return true;
16. if(d[i]>k.d[i])return false;
17. }
18. return false;
19. }
20. bool operator==(const key& k)const{
21. int i;
22. for(i=0;i<M;i++){
23. if(d[i]!=k.d[i])
24. return false;
25. }
26. return true;
27. }
28. const int *getData()const{return d;}
29. };
31. map<key, long long> the_map;
33. long long calc(int d[M])
34. {
35. int e[M];
36. map<key, long long>::iterator it;
37. it=the_map.find(d);
38. long long c;
39. if(it==the_map.end()){
40. int i;
41. for(i=0;i<M;i++){
42. e[i]=d[i];
43. }
44. c=0;
45. for(i=0;i<M-1;i++){
46. if(e[i+1]<e[i]){
47. e[i]--;
48. c+=calc(e);
49. e[i]++;
50. }
51. }
52. if(e[M-1]>0){
53. e[M-1]--;
54. c+=calc(e);
55. e[M-1]++;
56. }
57. the_map.insert(pair<key,long long>(d,c));
58. }else{
59. c=it->second;
60. }
61. return c;
62. }
64. int _tmain(int argc, _TCHAR* argv[])
65. {
66. int d[M];
67. int i;
68. d[0]=1;
69. for(i=1;i<M;i++)d[i]=0;
70. the_map[d]=1LL;
71. for(i=0;i<M;i++)d[i]=M;
72. printf("%lld\n",calc(d));
73. return 0;
74. }

复制代码

数学星空

呵呵,真不可思议,表达式太复杂了 $f(n)={(n^2)!}/{prod_{k=1}^{2n-1}k^(n-|n-k|)}$

nlrte13

呵呵,真不可思议,表达式太复杂了 f(n)={(n^2)!}/{prod_{k=1}^{2n-1}k^(n-|n-k|)} 数学星空 发表于 2009-7-27 17:25

咳。。。你真能搞 - -# 我发现我的算式不对^^ 不过4*4的结果还是对的，哈哈