自然数前段的均衡样本

无心人

月底要出去，待一个多月

计算下，
月底是25号以后概率为50%，因为一般人20号后才叫月底
一个半月，45天概率是50%
那么，5月25号+45天>7月1日
所以，hujunhua 在苏州概率25%，或者说，很有可能还在苏州

wayne

无心人 发表于 2010-7-1 09:19
月底要出去，待一个多月

计算下，

偶是来挖坟的.
值得推进,搜藏.

Lwins_G

依照本楼习惯，设特征多项式为$S_k(x)$。
现阶段可以断定的是，$S_k(x) \ \text{|} \ \prod_{j=1}^k (x^j - 1)$。
然而我的拙证比较晦涩，暂不给出。（使用了q-模拟和复分析的知识）

Lwins_G

@wayne 版主，
你在111#给出的对应于奇数项的母函数的展开式为
$$ \frac{x^2 (1+x)^2}{(1-x)^2 (1-x^2)} = x^2 + 4x^3 + 9x^4 + 16x^5 + \cdots. $$
似乎和数值计算所得的答案不符。是不是哪里写错了？


补充内容 (2014-1-5 17:52):
@mathe

wayne

刚才把所有的帖子都重新编辑了一下,  
论坛搬迁所引起的 换行问题导致的.

hujunhua

这个帖子沉寂快十年了，但我一天都不曾忘记过它的存在。
因为我感兴趣的真正重要的问题——第3）问和第4）问尚未开始。
而据初步计算，后两问会产生两个新的有趣数列。

我曾编写了一个M10小程序计算过第3）问，由于计算机比较跛，程序算法也不是很高效，所以只计算到了前28项：

{1, 1, 2, 2, 3, 3, 6, 6, 11, 13, 20, 26, 41, 55, 74, 116, 141, 241, 258, 472, 473, 873, 828, 1576, 1447, 2821, 2472, 5072}

在OEIS上未搜到上述有限序列，应该是个新数列。

将奇数项和偶数项分开，得到两个单调递增数列：

{1, 2, 3, 6, 11, 20,  41, 74, 141, 258, 473, 828, 1447, 2472, ...}

{1, 2, 3, 6, 13, 26, 55, 116, 241, 472, 873,1576, 2821, 5072, ...}

在OEIS上也未搜到上述片段，看来还是新数列。

hujunhua

说说我的算法。
为了减小复杂度，代码中将自然数的前段 Range[n] 变换为正负对称的 N(n)=Range[-(n-1), n-1, 2], 例如
N(6)={-5, -3, -1, 1, 3, 5}
N(7)={-6, -4, -2, 0, 2, 4, 6}【程序中将0去掉了】
这样一来和与平均数皆为0，均衡样本即零和子集，不可约均衡样本即不含零和真子集的样本。
最重要的是，均衡样本具有了遗传性和继承性：例如N(6)的均衡样本也是N(8)的均衡样本，N(7)的均衡样本也是N(9)的均衡样本.
遗传性和继承性显示了奇偶之分，故上楼分开为两个序列是有道理的。
N(Odd)可以将其中的数除以2，下表为3-11的奇数按此处理的数据展示。可以与1#和4#的数据进行一下对照。

n	既约均衡样本数	既约均衡样本（省略0）
3	2	{±1}
5	3	{±1},{±2}
7	6	{±1},{±2},{±3}
		±{1,2,-3}
9	11	{±1},{±2},{±3},{±4}
		±{1,2,-3},±{1,3,-4}
		±{1,-2,-3,4}
11	20	{±1},{±2},{±3},{±4},{±5}
		±{1,2,-3},±{1,3,-4},±{1,4,-5},±{2,3,-5}
		±{1,-2,-3,4},±{1,-2,-4,5},±{2,-3,-4,5}

N(n+2)的不可约均衡样本可分为4种：
    1、继承自N(n)的,
    2、{-n-1,n+1},
    3、包含 -(n+1)而不包含 n+1 的,
    4、包含 n+1 而不包含 -(n+1) 的.
其中后两种是负对称的，计算其一即可。

hujunhua

继续交代我那简陋的算法。以奇数前段为例。
前面说了，N(n+2)的不可约均衡样本可分为4种, 记第4类的计数为d(n+1), 4类之和计数为a(n+2)，则

        a(n+2)=a(n)+1+2d(n+1)=a(n-2)+2+2d(n-1)+2d(n+1)=...=a(5)+(n-3)/2+2d(6)+2d(8)+...+2d(n+1)=(n+3)/2+2d(6)+2d(8)+...+2d(n+1).

我们的程序就是搜索计数d(k), 然后累加得到各a(n).
1. 生成一个长为(n-1)/2的对称三进数位表, 如{0,1,-1,-1,0,0,...,1}. 函数为Tuples[{-1, 0, 1}, (n-1)/2]
2. 将上述位表与序列{2,4,6,...,n-1}对位相乘，滤掉零元素。得到对序列的选取和赋号，然后将n+1加入得表最后。
3. 滤取得表集中的零和列表（第一步中的函数得到的其实是所有的位表集）。
4. 构造一个检验函数， 检验所得表列是否包含零和真子集。用此函数滤掉包含零和真子集者。

n	极大划分数	既约样本数	既约均衡样本(n为奇数时省略中数）	极大划分模型	极大划分(n为奇数时省略中数）
13		41	{±1},{±2},{±3},{±4},{±5},{±6}
			±{1,2,-3},±{1,3,-4},±{1,4,-5},±{1,5,-6},
			±{2,3,-5},±{2,4,-6},
			±{1,-2,-3,4},±{1,2,3,-6},±{1,-2,-4,5},±{1,-2,-5,6},
			±{1,-3,-4,6}±{2,-3,-4,5},±{2,-3,-5,6},±{3,-4,-5,6}
			±{1,-2,3,4,-6},±{1,2,-4,-5,6},±{2,3,-4,5,-6}

hujunhua

对于分奇偶后得到的四个新数列：
最大划分数，       奇{1, 1, 1, 2, 4, 14, 64, ...},
                          偶{1, 1, 1, 2, 5, 19, ...}
既约均衡样本数：奇{1, 2, 3, 6, 11, 20,  41, 74, 141, 258, 473, 828, 1447, 2472, ...}，
                          偶{1, 2, 3, 6, 13, 26, 55, 116, 241, 472, 873,1576, 2821, 5072, ...}，
以及不分奇偶的两新数列，
           {1, 1, 1, 1, 1, 1, 2, 2, 4, 5, 14, 19, 64, ...},
           {1, 1, 2, 2, 3, 3, 6, 6, 11, 13, 20, 26, 41, 55, 74, 116, 141, 241, 258, 472, 473, 873, 828, 1576, 1447, 2821, 2472, 5072, ...}
我一直觉得不可能是简单的线性递推序列，都懒得用Mathematica的FindSequenceFunction[]和FindLinearRecurrence[]函数去一试。
今天看到wayne又在群里推了按这个贴子整理的Blog的分享，我终于想到万一是的呢，何不一试，一个命令的事。
结果不出所料，算不出来！
对于第4)问最大划分数，我还没有找到好的算法，又不想手算更多的项。有时间了再琢磨，我会回来的...