一个简单的计数问题

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 ... mp;language=english

1. 
   
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. };
    
30. 
    
31. map<key, long long> the_map;
    
32. 
    
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. }
    
63. 
    
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的结果还是对的，哈哈