果树问题讨论:这两个问题等价么？

mathe

对第二个问题，就是n个字母，取出x组，每组4个字母，每两组之间最多1个相同的字母。 我写了个简单的程序计算出了$n<=15$时x的最大值$x(n)$，而且得出 $17<=x(16)<=20$ $20<=x(17)<=21$ $21<=x(18)<=22$ 结果惊奇的发现这个序列同 A004037匹配上了。 也就是x(5)是这个序列中第一个数或者说$x(n+4)=A(n,6,4)$

shshsh_0510

这个不惊奇，第二个问题有很多种描述方法，比如：将Kn分解为K4的最大树。 如果再加一点要求，让所有点出现的次数相等，则是一个S(2,4,n)的steiner系统。 上述steiner系统在12|n(n-1)时存在，所以 x(16)=C(16,2)/C(4,2)=20，x(21)=35，x(25)=50 ...... 对于n=20,我觉得zgg差不多了，没找到有效的构造方法，我想只能强搜了。 [ 本帖最后由 shshsh_0510 于 2008-8-6 10:01 编辑 ]

shshsh_0510

呵呵，仔细看了一下， 就是mathe 的连接， Optimal packings of K_4's into a K_n, 那么x(20)应该是42

shshsh_0510

好像数不太队，在想想

shshsh_0510

呵呵，没看清楚，那个“ Optimal packings of K_4's into a K_n, ” 是一个ref，不是对这个数列的描述。 找到那个ref就ok了。我没找到，谁找一下啊

shshsh_0510

对于两个问题等价问题，很容易证明，比如对于n=16时不等价。

mathe

原帖由 shshsh_0510 于 2008-8-6 09:39 发表 呵呵，仔细看了一下， 就是mathe 的连接， Optimal packings of K_4's into a K_n, 那么x(20)应该是42

你不说optimal packing $K_4$'s into $K_n$,我倒没有注意。这个说法倒应该没有错了。 只是这个数列不是从第1项开始的，链接中说是第6项开始，但是我觉得应该是第5项开始。 而x(20)应该是30，而不是42。 里面$A(n,d,w)$的提法也应该是正确的，只是我觉得应该是$A(n,7,4)$而不是$A(n,6,4)$,而且同样是从第5项而不是第6项开始的。 也就是描述成最大的长度为n重量为4的0-1向量集合，其中任何两向量海明距离不小于7。

mathe

关于问题1，网上资料只能查到$n<=11$的值。 我写的一个程序现在计算出了关于问题2中$12<=n<=14$所有不等价的边的数目不小于 $[{[(n-1)/3]n}/4]-3$的组合，总数不多,大家可以看看能否通过它们构造第一个问题的解

mathe

忘了说明数据格式，每一行代表一个组合。其中相邻4个字母代表一条直线

zgg___

对于问题二的x(20)，搜索到一组为27的解： {{5,8,13,20},{3,12,13,17},{1,6,7,13},{1,8,14,15},{4,9,13,16},{9,11,18,19},{7,12,16,19},{2,3,6,20},{2,8,11,12},{3,5,14,19},{5,10,16,18},{1,5,11,17},{7,15,18,20},{1,9,12,20},{2,5,7,9},{4,6,10,11},{4,5,12,15},{6,12,14,18},{2,10,13,19},{1,2,4,18},{2,15,16,17},{4,17,19,20},{7,10,14,17},{11,14,16,20},{3,4,7,8},{6,8,9,17},{3,9,10,15}} 可以看到，其中有8个数出现了6次，有12个出现了5次。我们知道一个数只能最多出现6次（因为只有19个数可以和它配组，[19/3]=6）。如果20个数都恰好出现6次，那么总共有120个数，120/4=30，所以只有每个数都出现6次，才能构成x(20)=30的解。