自然数前段的均衡样本 - 第6页 - 编程擂台 - 数学研发论坛

wayne 发表于 2010-4-28 12:01:22

50# hujunhua
嗯，明白了，是我刚才忘了更改表达式f里面的ii的上限了

这么一来，那么K=8也就出来了：
也是 (x-1)Y8(x)

hujunhua 发表于 2010-4-28 15:03:16

证明的思路。提供两条我要试探的思路，供参考。我自己五一前可能没时间去探索这两条路了。

为了避免枝节，第1 )问先返回到第一版的形式，即只考虑奇数项：

Range(2n-1):={1, 2, 3, ..., 2n-1}的总体平均值为n, 对于的k∈Range{2n-1}, 证明k元均衡样本数序列ak(n)的特征多项式Sk(x)=(x-1)Yk(x).

思路1、按Yk(x)的展开式构造bk(n), 得到常数数列，给这个构造一个组合解释。（参考30#）

思路2、按xk-1-1构造bk(n), 即bk(n)=ak(n+k-1)-ak(n),得到的bk(n)与k-1元样本数序列ak-1(n)具有相同的特征多项式。给这个构造一个组合解释。

mathe 发表于 2010-4-28 18:45:57

我算到了37个
{0, 0, 0, 1, 4, 24, 94, 289, 734, 1656, 3370, 6375, 11322, 19138, 30982, 48417, 73316, 108108, 155646, 219489, 303748, 413442, 554256, 733005, 957332, 1236222, 1579666, 1999265, 2507780, ...
wayne 发表于 2010-4-27 09:00 http://bbs.emath.ac.cn/images/common/back.gif
K=7的Pari/Gp数值计算结果:
(18:44) gp > V=vector(50,X,S(7,X))
%17 = [0, 0, 0, 1, 4, 24, 94, 289, 734, 1656, 3370, 6375, 11322, 19138, 30982, 4
8417, 73316, 108108, 155646, 219489, 303748, 413442, 554256, 733005, 957332, 123
6222, 1579666, 1999265, 2507780, 3119876, 3851588, 4721127, 5748298, 6955424, 83
66614, 10008857, 11911188, 14105854, 16627422, 19514081, 22806570, 26549686, 307
91082, 35582861, 40980304, 47043624, 53836482, 61427973, 69890996, 79304338]

mathe 发表于 2010-4-28 18:46:44

K=8的数值计算结果
(18:44) gp > V=vector(50,X,S(8,X))
%18 = [0, 0, 0, 0, 1, 13, 73, 289, 910, 2430, 5744, 12346, 24591, 46029, 81805,
139143, 227930, 361384, 556834, 836618, 1229093, 1769773, 2502617, 3481445, 4771
508, 6451232, 8614108, 11370764, 14851235, 19207395, 24615603, 31279561, 3943336
6, 49344790, 61318804, 75701312, 92883137, 113304279, 137458401, 165897591, 1992
37422, 238162256, 283430856, 335882312, 396442239, 466129301, 546062077, 6374662
17, 741681952, 860171966]

mathe 发表于 2010-4-28 18:47:39

S(K,n)=
{
local(V,L,s);
L=K*n;
V=matrix(K,L);
V=1;
for(u=2,2*n-1,
   for(h=1,K-1,
      for(v=1,L,
         s=V;
         if(v>u,s=s+V);
         V=s
      )
   );
   V=1
);
V
}
V(K,N)=
{
vector(N,X,S(K,X))
}

mathe 发表于 2010-4-28 19:14:26

稍微修改后高效一些的代码
S(K,n)=
{
local(V,L,s,R);
L=K*n;
V=matrix(K,L);
R=vector(n);
V=1;
R=0;
for(u=2,2*n-1,
   for(h=1,K-1,
      for(v=1,L,
         s=V;
         if(v>u,s=s+V);
         V=s
      )
   );
   V=1;
   if(bitand(u,1)==1,
         s=(u+1)/2;
         R=V
   )
);
R
}(19:14) gp > S(8,100)
%6 = [0, 0, 0, 0, 1, 13, 73, 289, 910, 2430, 5744, 12346, 24591, 46029, 81805, 1
39143, 227930, 361384, 556834, 836618, 1229093, 1769773, 2502617, 3481445, 47715
08, 6451232, 8614108, 11370764, 14851235, 19207395, 24615603, 31279561, 39433366
, 49344790, 61318804, 75701312, 92883137, 113304279, 137458401, 165897591, 19923
7422, 238162256, 283430856, 335882312, 396442239, 466129301, 546062077, 63746621
7, 741681952, 860171966, 994529582, 1146487322, 1317925859, 1510883299, 17275648
63, 1970352985, 2241817760, 2544727816, 2882061630, 3257019208, 3673034221, 4133
786599, 4643215521, 5205532877, 5825237216, 6507128110, 7256321012, 8078262628,
8978746723, 9963930445, 11040351191, 12214943919, 13495059014, 14888480710, 1640
3445986, 18048664034, 19833336311, 21767177085, 23860434577, 26123912711, 285689
93380, 31207659328, 34052517670, 37116823944, 40414506807, 43960193389, 47769235
203, 51857734721, 56242572636, 60941435694, 65972845224, 71356186370, 7711173792
1, 83260702859, 89825239635, 96828494063, 104294631954, 112248872506, 1207175223
32, 129728010248]

mathe 发表于 2010-4-28 19:14:57

(19:14) gp > S(9,100)
%7 = [0, 0, 0, 0, 1, 5, 43, 227, 910, 2934, 8150, 20094, 45207, 94257, 184717, 3
43363, 610358, 1043534, 1724882, 2767118, 4323349, 6596639, 9853759, 14438535, 2
0790704, 29463920, 41150848, 56706832, 77182439, 103853847, 138264239, 182262067
, 238052726, 308245978, 395919498, 504676796, 638724335, 802941377, 1002972487,
1245310885, 1537408202, 1887772950, 2306099636, 2803384052, 3392073839, 40862024
57, 4901563471, 5855865091, 6968930556, 8262875230, 9762335578, 11494670966, 134
90223763, 15782548007, 18408703437, 21409513285, 24829894988, 28719149540, 33131
331832, 38125574010, 43766498505, 50124577927, 57276593963, 65306036531, 7430361
1736, 84367683000, 95604831582, 108130342498, 122068821011, 137554726349, 154733
047799, 173759889219, 194803208474, 218043455828, 243674380584, 271903726648, 30
2954110225, 337063775827, 374487549227, 415497657279, 460384760198, 509458838774
, 563050310290, 621510986676, 685215278491, 754561227653, 829971804023, 91189601
6583, 1000810307130, 1097219743726, 1201659516408, 1314696216830, 1436929440719,
1568993157857, 1711557426281, 1865329856709, 2031057443580, 2209528128118, 2401
572751432, 2608066720660]

hujunhua 发表于 2010-4-28 23:49:53

关于线性递推序列(整数)的两个定理，明确地列出来，可以澄清一些问题，亡羊补牢吧。

一、最简特征多项式
1、线性递推序列{a(n)}存在最简递推公式，即所需初值最少的递推公式。最简递推公式对应着最简特征多项式，即次数最低的特征多项式。设最简特征多项式为f(x).
2、非最简的递推公式所对应的特征多项式必包含因式f(x).
3、对任意非零整系数多项式g(x), f(x)g(x)都能成{a(n)}的完全递推公式（即适用于所有n），只要给足与次数相当的初值。
一般不作特殊说时，默认的都指最简公式和最简特征多项式，所以反而让人忘了最简这个前缀。

二、特征根的分离与组合
1、若有因式分解f(x)=g(x)h(x),如30#那样按g(x)组合a(n)构造b(n), 则{b(n)}亦为线性递推序列，并且以h(x)为最简特征多项式。
2、若按某个多项式g(x)组合a(n)构造的b(n)仍为线性递推序列，并且具有最简特征多项式h(x)，那么f(x)=g(x)h(x).

wayne 发表于 2010-4-29 09:24:46

56# mathe

mathe，你太帅了！

======================================
根据你的代码，我把奇数的情况算到了15次，即 S(15,250)
然后利用Mathematica进行公式推导，发现，31楼的猜想仍然成立，即
对奇数k一致地成立Sk(x)=(x-1)Yk(x)

hujunhua 发表于 2010-4-29 13:30:38

56# mathe
mathe，你太帅了！
======================================
根据你的代码，我把奇数的情况算到了15次，即 S(15,250)
然后利用Mathematica进行公式推导，发现，31楼的猜想仍然成立，即

wayne 发表于 2010-4-29 09:24 http://bbs.emath.ac.cn/images/common/back.gif

k=10, 12, 14都验证了吗？

页: 1 2 3 4 5 [6] 7 8 9 10 11 12 13

数学研发论坛's Archiver