主题
Search

Katona 问题


找到一个 f(n) 的最小值,即对于一个包含 n 个元素的集合分离族子集 的最小数量,其中分离族是一个集合子集集合,其中每对相邻元素都被分离,每个元素都位于两个不相交子集之一中。例如,字母表的 26 个字母可以用九个族的字母分隔

 (abcdefghi) (jklmnopqr) (stuvwxyz); (abcjklstu) (defmnovwx) (ghipqryz); (adgjmpsvy) (behknqtwz) (cfilorux).

该问题由 Katona (1973) 提出,并由 C. Mao-Cheng 于 1982 年解决,

 f(n)=min{2p+3[log_3(n/(2^p))]:p=0,1,2},

其中 [x]向上取整函数f(n) 是非递减的,并且 n=1, 2, ... 的值为 0, 2, 3, 4, 5, 5, 6, 6, 6, 7, ... (OEIS A007600)。 f(n) 增加的值为 1, 2, 3, 4, 5, 7, 10, 13, 19, 28, 37, ... (OEIS A007601),因此 f(26)=9,如前面的例子所示。


另请参阅

分离族

使用 探索

WolframAlpha

更多尝试

参考文献

Honsberger, R. "蔡茂诚对 Katona 关于分离子集族问题的解法。" Ch. 18 in Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 224-239, 1985.Katona, G. O. H. "组合搜索问题。" In A Survey of Combinatorial Theory (Ed. J. N. Srivasta, F. Harary, C. R. Rao, G.-C. Rota, and S. S. Shrikhande). Amsterdam, Netherlands: North-Holland, pp. 285-308, 1973.Sloane, N. J. A. 序列 A007600/M0456 和 A007601/M0525 在 "整数序列在线百科全书" 中。

在 上引用

Katona 问题

请引用为

Weisstein, Eric W. "Katona 问题。" 来自 Web 资源。 https://mathworld.net.cn/KatonasProblem.html

主题分类