この題名だと何のことかわかりませんが、以下の例題を解くために必要な考え方なので順を追って説明していきます。
【例題】 自然数nの約数の集合をDとしたとき、その要素の中でお互いに約数にならない数 （antichain） の集合Sの最大値を求めよ
たとえばn=6ならD={1,2,3,6}で最大のS={2,3}なので答えは ２となる
この問題を見て「簡単だね、素因数の集合でいいんじゃない」と思った人は是非この記事を読むことをおすすめします。
Antichainとは
「半順序集合の部分集合でどの２つの要素も比較不能なもの」
例として全体集合が$X=\lbrace 1,2,3 \rbrace $のべき集合（power set）の集合を$P$とすると
\begin{align}
& P = \{ \phi, \{1\}, \{2\}, \{3\}, \{1,2\}, \{2,3\}, \{1,3\}, \{1,2,3\}, \} \\ \\
& この場合\mathbf{Antichain}が最大になるのは \\ \\
& \{ \{1\}, \{2\}, \{3\}, \} と \\
& \{ \{1,2\}, \{2,3\}, \{1,3\} \} の2つがあります \\
\end{align}
Spernerの定理
この例を見てピンと来たと思いますが$n$個の集合のべき集合のAntichainは
- 同じ数$k$個の要素を含む部分集合を集めたものはAntichain
- $k=\lfloor \frac{n}{2} \rfloor$、または$k=\lceil \frac{n}{2} \rceil$のときに最大となりその数は$\Large \binom{n}{k}$
となるかなと推測できます。まさしくこれがSpernerの定理 (Wikipadia（英語）)です。
\begin{align}
& したがってX = \{ 1, 2, 3, 4\}ならば\\
& その部分集合の\mathbf{Antichain}が最大になるのは \\
& k=\lfloor \frac{n}{2} \rfloor = 2 で\\
& 4個から2個を選ぶ組み合わせとなるので\\
& \{ \{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\} \} の6個です \\
\end{align}
自然数の約数に適用
自然数を素因数分解するとその約数は、素因数のべき集合と考えられるのでSpernerの定理を例題に適用することができそうです。
\begin{align}
& n = 30のとき素因数の集合は \{ 2, 3, 5\}\\
& べき集合は \{\phi, \{2\}, \{3\}, \{5\}, \{2,3\}, \{2,5\},\{3,5\},\{2, 3, 5\} \} \\
& でその要素の積が約数になる \\
& \mathbf{Antichain}が最大になる約数の集合は \\
& \{ 2,3,5 \} と \{ 6,10, 15\} で共に3個となります \\
\end{align}
ただこれだと素因数に平方数を含まないいわゆる無平方数にしか適用できません。
たとえば$n=12=2\times 2\times 3$ではどうすればよいかを考えていきます。
multiset（多重集合）に適用する
自然数の素因数分解は同じ数が含まれるので多重集合(multiset) (Wikipedia)という考え方を使います。
\begin{align}
& n = 12 のとき 素因数の\mathbf{multiset}は \{ 2, 2, 3\}\\
& べき集合は \{\phi, \{2\}, \{3\}, \{2,2\}, \{2,3\},\{2, 2, 3\} \} \\
\end{align}
実はSpernerの定理はmultisetにも部分的に適用できます。それを確認しましょう。
\begin{align}
& n = 3, \lfloor n/2 \rfloor = 1, \lceil n/2 \rceil = 2 \\
& k=1: \{\{2\}, \{3\} \}, k=2: \{\{2,2\}, \{2,3\} \}\\
& ともに最大の\mathbf{Antichain}になる \\
\end{align}
ただその時の数は単純に$\Large \binom{n}{k}$とはならないので、multisetの組み合わせの数を求める必要があります。
multisetの組み合せ
これはmultiestの順列（同じものを含む順列の生成と数）と同様に簡単には求まらないのですが、幸い Sympy には multiset_combinationsという関数があり factorintの結果をそのまま入力できます。
import sympy as sp
from sympy.utilities.iterables import multiset_combinations
n = 12
fct = sp.factorint(n)
list(multiset_combinations(fct, 2))
# [[2, 2], [2, 3]]
したがって例題の答えは以下のmaxAntichainで得られます。
def maxAntichain(n):
fct = sp.factorint(n)
return len(list(multiset_combinations(fct, sum(fct.values())//2)))
for n in [6,12,30, 2**3*3**3*5**3]:
print(n, maxAntichain(n))
# 6 2
# 12 2
# 30 3
# 27000 12
multsetの組み合せの数だけ求める
multiset_combinationsはすべての組み合わせを列挙しますが、その数だけを求める方法もあります。OEIS A096825 Maximal size of an antichain in divisor lattice D(n)にその公式が紹介されてます。
\begin{align}
& nの\mathbf{Antichain}の約数の集合の最大値は\\
& n = p_1^{k_1} \times ... \times p_q^{k_q}\\
& k = \lfloor (k_1+...+k_q)/2 \rfloor \ のとき\\
& (1+x+...+x_{k_1})...(1+x+...+x_{k_q})のx^kの係数\\
& \\
\end{align}
やや分かりづらいですがコードを見てください。同じ結果が得られます。
import numpy as np
from functools import reduce
from operator import mul
def maxAntichain1(n):
fv = sp.factorint(n).values()
return reduce(mul, [np.poly1d([1]*(k+1)) for k in fv]).coeffs[sum(fv)//2]
（開発環境：Google Colab）
この考え方はProject Euler, Problem 386: Maximum Length of an Antichainを解くのに役に立ちます。