ソリッドパーティション

数学において、立体分割はパーシー・アレクサンダー・マクマホンによって定義された整数分割と平面分割の自然な一般化である。^[1]の立体分割は、負でない整数（添え字） の3次元配列であり、${\displaystyle n}$${\displaystyle n_{i,j,k}}$${\displaystyle i,j,k\geq 1}$

${\displaystyle \sum _{i,j,k}n_{i,j,k}=n}$

そして

${\displaystyle n_{i+1,j,k}\leq n_{i,j,k},\quad n_{i,j+1,k}\leq n_{i,j,k}\quad {\text{and}}\quad n_{i,j,k+1}\leq n_{i,j,k}}$全ての${\displaystyle i,j{\text{ および }}k.}$

を の立体分割の数とします。立体分割の定義には 3 次元の数値配列が含まれるため、平面分割が 2 次元分割、分割が 1 次元分割である表記では、立体分割は3 次元分割とも呼ばれます。立体分割とその高次元一般化については、Andrewsの著書で説明されています。^[2]${\displaystyle p_{3}(n)}$${\displaystyle n}$

立体分割の別の表現は、フェラーズ図の形をとる。 の立体分割のフェラーズ図は、条件を満たす点またはノード、の集合である: [ ^3]${\displaystyle n}$${\displaystyle n}$${\displaystyle \lambda =(\mathbf {y} _{1},\mathbf {y} _{2},\ldots ,\mathbf {y} _{n})}$${\displaystyle \mathbf {y} _{i}\in \mathbb {Z} _{\geq 0}^{4}}$

条件 FD:ノード の場合、すべてのに対して となるすべてのノードも となります。${\displaystyle \mathbf {a} =(a_{1},a_{2},a_{3},a_{4})\in \lambda }$${\displaystyle \mathbf {y} =(y_{1},y_{2},y_{3},y_{4})}$${\displaystyle 0\leq y_{i}\leq a_{i}}$${\displaystyle i=1,2,3,4}$

例えば、フェラーズ図

${\displaystyle \left({\begin{smallmatrix}0\\0\\0\\0\end{smallmatrix}}{\begin{smallmatrix}0\\0\\1\\0\end{smallmatrix}}{\begin{smallmatrix}0\\1\\0\\0\end{smallmatrix}}{\begin{smallmatrix}1\\0\\0\\0\end{smallmatrix}}{\begin{smallmatrix}1\\1\\0\\0\end{smallmatrix}}\right)\ ,}$

ここで各列はノードであり、 の立体分割を表します。 フェラーズ図には順列群の自然な作用があります。これは、すべてのノードの 4 つの座標を順列させることに対応します。 これは、通常の分割における共役によって表される操作を一般化します。 ${\displaystyle 5}$${\displaystyle S_{4}}$

Ferrers 図が与えられた場合、次のようにして実体分割 (主な定義と同じ) を構築します。

はFerrers 図のノードの数で、座標は の形式で、 は任意の値を表します。コレクションは固体分割を形成します。条件 FD は固体分割の条件が満たされていることを意味することが確認できます。${\displaystyle n_{i,j,k}}$${\displaystyle (i-1,j-1,k-1,*)}$${\displaystyle *}$${\displaystyle n_{i,j,k}}$

実体分割を形成する 集合が与えられた場合、対応する Ferrers 図は次のように得られます。${\displaystyle n_{i,j,k}}$

ノードのない Ferrers ダイアグラムから始めます。 0 以外のすべての について、 Ferrers ダイアグラムにのノードを追加します。 構築により、条件 FD が満たされていることが簡単にわかります。${\displaystyle n_{i,j,k}}$${\displaystyle n_{i,j,k}}$${\displaystyle (i-1,j-1,k-1,y_{4})}$${\displaystyle 0\leq y_{4}$

例えば、上記のノード を持つフェラーズ図は、${\displaystyle 5}$

${\displaystyle n_{1,1,1}=n_{2,1,1}=n_{1,2,1}=n_{1,1,2}=n_{2,2,1}=1}$

他のすべては消え去ります。 ${\displaystyle n_{i,j,k}}$

とする。固体分割の生成関数を次のように定義する。 ${\displaystyle p_{3}(0)\equiv 1}$${\displaystyle P_{3}(q)}$

${\displaystyle P_{3}(q):=\sum _{n=0}^{\infty }p_{3}(n)q^{n}=1+q+4q^{2}+10q^{3}+26q^{4}+59q^{5}+140q^{6}+\cdots }$( OEISの配列A000293 )。

整数分割と平面分割の生成関数は、それぞれオイラーとマクマホンのおかげで、簡単な積の公式を持つ。しかし、マクマホンの推測では、6の立体分割を正しく再現できない。^[3]立体分割の生成関数には簡単な公式は存在しないようである。特に、オイラーとマクマホンの積の公式に類似した公式は存在しない。^[4]

明示的に知られている生成関数がないため、より大きな整数の立体分割の数の列挙は数値的に行われてきました。立体分割とその高次元一般化を列挙するために使用されるアルゴリズムは2つあります。Atkinらの研究では、BratleyとMcKayによるアルゴリズムが使用されました。^[5] 1970年に、Knuthは位相シーケンスを列挙するための別のアルゴリズムを提案し、すべての整数の立体分割の数を評価するために使用しました。^[6] MustonenとRajeshは、すべての整数の列挙を拡張しました。^[7] 2010年に、S . Balakrishnanは、すべての整数に列挙を拡張するために使用されているKnuthのアルゴリズムの並列バージョンを提案しました。^[8]${\displaystyle n\leq 28}$${\displaystyle n\leq 50}$${\displaystyle n\leq 72}$

${\displaystyle p_{3}(72)=3464274974065172792\ ,}$

これは 19 桁の数字であり、このような正確な列挙を実行することの難しさを示しています。

^{[9] [7] [10]}のような定数が存在すると推測される。${\displaystyle c}$

$${\displaystyle \lim _{n\rightarrow \infty}{\frac {\log p_{3}(n)}{n^{3/4}}}=c.}$$

• OEISシーケンス A000293 (立体 (つまり、3 次元) パーティション)
• IITマドラスのソリッドパーティションプロジェクト
• ソリッドパーティションに関する Mathworld のエントリ