主题
Search

有序分解

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

有序分解是指一种分解 (不一定是素因数分解)，其中 a×b 被认为与 b×a 不同。下表列出了整数 1 到 10 的有序分解。

n#有序分解
111
212
313
422·2, 4
515
632·3, 3·2, 6
717
842·2·2, 2·4, 4·2, 8
923·3, 9
1032·5, 5·2, 10

有序分解的数量 H(n) (对于 n=1, 2, ...) 由 1, 1, 1, 2, 1, 3, 1, 4, 2, 3, ... (OEIS A074206) 给出。这个序列具有狄利克雷生成函数

f(s)=1/(2-zeta(s)),
(1)

其中 zeta(s) 是黎曼 zeta 函数。

递推方程 H(n) 由下式给出

H(n)=sum_(d|n)H(d),
(2)

其中求和是对 n 的除数进行的，并且 H(1)=1 (Hille 1936, Knopfmacher 和 Mays 2006)。Hille (1936) 给出的另一个 n>1 的递推关系由下式给出

H(n)=2[sum_(p_i)H(n/(p_i))-sum_(p_1,p_2)H(n/(p_ip_j))+...+(-1)^(r-1)H(n/(p_1p_2...p_r))],
(3)

其中 H(1)=1/2 并且

n=p_1^(alpha_1)p_2^(alpha_2)...p_r^(alpha_r)
(4)

是 n 的素因数分解 (Knopfmacher 和 Mays 1996)。

MacMahon (1893) 推导出了美丽的双重求和公式

H(n)=sum_(j=1)^qsum_(i=0)^(j-1)(-1)^i(j; i)product_(k=1)^r(alpha_k-j-i-1; alpha_k),
(5)

其中

q=sum_(k=1)^ralpha_k
(6)

(Knopfmacher 和 Mays 1996)。在 n 是两个素数幂乘积的情况下，

n=p_1^(alpha_1)p_2^(alpha_2),
(7)

Chor 等人 (2000) 表明

H(n)=2^(alpha_1+alpha_2-1)sum_(k=0)^(alpha_2)(alpha_1; k)(alpha_2; k)2^(-k)
(8)
=2^(alpha_2-1)_2F_1(-alpha_1,alpha_2+1;1;-1),
(9)

其中 _2F_1(a,b;c;z) 是一个超几何函数。

n 的有序分解数等于 n-1 的完美划分数 (Goulden 和 Jackson 1983, p. 94)。

另请参阅

不同素因数分解, 分解, 完美划分, 素因数分解, 无序分解

使用 Wolfram|Alpha 探索

参考文献

Chor, B.; Lemke, P.; and Mador, Z. "关于自然数的有序分解的数量。" Disc. Math. 214, 123-133, 2000.Comtet, L. 高级组合数学：有限与无限展开的艺术，修订增补版。 Dordrecht, Netherlands: Reidel, p. 126, 1974.Goulden, I. P. and Jackson, D. M. Problem 2.5.12 in 组合计数。 New York: Wiley, p. 94, 1983.Hille, E. "'因数分解数' 中的一个问题。" Acta Arith. 2, 134-144, 1936.Honsberger, R. 数学珍宝 III。 Washington, DC: Math. Assoc. Amer., p. 141, 1985.Knopfmacher, A. and Mays, M. "整数的有序和无序分解。" Mathematica J. 10, 72-89, 2006.MacMahon, P. A. "关于数字组合理论的回忆录。" Philos. Trans. Roy. Soc. London (A) 184, 835-901, 1893.Riordan, J. 组合分析导论。 New York: Wiley, p. 124, 1980.Sloane, N. J. A. 序列 A074206 in "整数序列在线百科全书。"Warlimont, R. "带约束的因数分解数。" J. Number Th. 45, 186-199, 1993.

在 Wolfram|Alpha 中被引用

有序分解

引用为

韦斯坦因，埃里克·W. "有序分解。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/OrderedFactorization.html

主题分类