一个简单的计数问题
十六个不同高度的人前后排成四排，每排四人，要求后面的比前面高，左边的比右边的高，问你有几种排法？ 如果有这样的两个要求的话，估计只有一种排列方法。 ............................4个数两排，就有2种排列了 本帖最后由 nlrte13 于 2009-7-27 14:55 编辑
我算的结果是 24024 种排列 14 * 13 * 12 * 11 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种
………… 本帖最后由 数学星空 于 2009-7-27 16:44 编辑
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) http://www.research.att.com/~njas/sequences/?q=2%2C42%2C24024&sort=0&fmt=0&language=english
#include <map>
using namespace std;
#define M 5
class key{
int d;
public:
key(int v){
int i;
for(i=0;i<M;i++)d=v;///non-increasing sequence required.
}
bool operator<(const key& k)const{
int i;
for(i=0;i<M;i++){
if(d<k.d)return true;
if(d>k.d)return false;
}
return false;
}
bool operator==(const key& k)const{
int i;
for(i=0;i<M;i++){
if(d!=k.d)
return false;
}
return true;
}
const int *getData()const{return d;}
};
map<key, long long> the_map;
long long calc(int d)
{
int e;
map<key, long long>::iterator it;
it=the_map.find(d);
long long c;
if(it==the_map.end()){
int i;
for(i=0;i<M;i++){
e=d;
}
c=0;
for(i=0;i<M-1;i++){
if(e<e){
e--;
c+=calc(e);
e++;
}
}
if(e>0){
e--;
c+=calc(e);
e++;
}
the_map.insert(pair<key,long long>(d,c));
}else{
c=it->second;
}
return c;
}
int _tmain(int argc, _TCHAR* argv[])
{
int d;
int i;
d=1;
for(i=1;i<M;i++)d=0;
the_map=1LL;
for(i=0;i<M;i++)d=M;
printf("%lld\n",calc(d));
return 0;
}
本帖最后由 数学星空 于 2009-7-27 17:33 编辑
呵呵,真不可思议,表达式太复杂了
f(n)={(n^2)!}/{prod_{k=1}^{2n-1}k^(n-|n-k|)} 呵呵,真不可思议,表达式太复杂了
f(n)={(n^2)!}/{prod_{k=1}^{2n-1}k^(n-|n-k|)}
数学星空 发表于 2009-7-27 17:25 http://bbs.emath.ac.cn/images/common/back.gif
咳。。。你真能搞 - -#
我发现我的算式不对^^
不过4*4的结果还是对的，哈哈
页:
[1]
2