自然数前段的均衡样本

hujunhua

显然，k元均衡样本数序列跟很多问题有联系，所以应该可以在数列在线中搜到一些现成的，一搜果然
3元序列为A000982
4元序列为A001973
6元序列为A001977

5元序列未见收录

mathe

k=4可以如下分析。
记4个数中中间两个数相邻的排列方案为b(n),中间两个数相隔1的排列数目为c(n),总排列数目为a(n)
那么a(n+1)=a(n)+b(n+1)+c(n+1)
b(n+1)-b(n)和c(n+1)-c(n)都很容易计算
这种方法应该可以扩充到更加大的k,只是这时数列b和c需要更加复杂的分析

wayne

14# hujunhua

要想继续走下去就很难了，这个需要在算法上作进一步的榨取。。。

我目前用的方法是chyanog 的改进版，即先生成整数n的所有K元不重复划分，然后再统计符合条件的划分的个数。

不知大大能否提供更优秀的算法来？

wayne

设自然数n分拆成K个互不相同的正整数之和，有P(n,K)种情况，那么
P(n,1)=1
P(n,2)=Floor[n/2]
P(n,3)=If[EvenQ, 0,Ceiling[(n-1)^2/8]]

自然数分拆为互异的整数之和的个数有
f(n)=P(n,1)+P(n,2)+P(n,3)+...+P(n,floor(2*n))

而f(n)又可以通过展开式 (1+x)(1+x²)...(1+xⁿ)的xⁿ系数得到

qianyb

EvenQ是什么东西?

hujunhua

我曾以为这是业余爱好者容易做出成果的问题，看来是过于乐观，对问题的难度估计不足，特别是对计算量估计不足。
第1）问就这么难搞，后面3问岂不是更没戏呀？我最想进攻的是第4）问，但现在还没有着手。按顺序一步步来的做法是否必要还不得而知，有时间了准备试跳一下，直接攻第4)问。

我计算的7元序列前24项，记录一下：0,0,0,1,4,24,94,289,734,1656,3370,6375,11322,19138,30982, 48417,73316,108108,155646,219489,303748,413442, 554256,733005

计算起来确实慢，但改进空间很大，因为我是最 P 的计算者。

wayne

我算到了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, 3119876, 3851588, 4721127, 5748298, 6955424, 8366614, 10008857, 11911188}
再大的话就超过了软件默认设置的计算内存。。。

但要推出一个递推公式，这些数据还不够充分

wayne

25# qianyb Q是 Question的缩写，意为 "ask a question" 所以，EvenQ 意思就是 "Is it Even?"-----这是偶数吗 这是Mathematica函数的特点，

qianyb

原来如此,没用过Mathematica软件

hujunhua

用合情猜想的模式来推导递推公式，37项足够了。且记$Y_k(x)=\prod_{i=1}^{k-1}(x^i-1)$，k元均衡样本数序列的特征多项式记为$S_k(x)$。我们的合情猜想是：$Y_k(x)|S_k(x)$
Y₇(x)=1-x-x² +x⁵+2x⁷ -x⁹-x¹⁰-x¹¹-x¹²+2x¹⁴+x¹⁶-x¹⁹-x²⁰+x²¹
构造b_n=a_n-a_1+n-a_2+n+a_5+n+2a_7+n-a_{9+ n}- a_10+n-a_11+n-a_12+n+2a_14+n+ a_16+n-a_19+n-a_20+n+a_21+n

b_n满足的特征多项式就是剩余的因式。

可得到的前16项b_n={3364, 3364,  …, 3364},  b_n无疑是常数序列，特征多项式为x-1, 所以S₇(x)=(x-1)Y₇(x).

这就太好了，又回到了最初的轨道。也许k=奇数时，都是S_k(x)=(x-1)Y_k(x).