平面分割

数学、特に組合せ論において、平面分割とは、負でない整数（正の整数のインデックスiとjを持つ）の2次元配列であり、両方のインデックスが非増加である。これは、 ${\displaystyle \pi_{i,j}}$

${\displaystyle \pi _{i,j}\geq \pi _{i,j+1}}$そしてすべてのiとjに対して。${\displaystyle \pi _{i,j}\geq \pi _{i+1,j}}$

さらに、 のうち、非ゼロとなるものは有限個だけです。平面分割は、整数 の分割の一般化です。 ${\displaystyle \pi_{i,j}}$

平面分割は、平面上の点（i、j ）の上に単位立方体のスタックを配置することで視覚的に表現され、図に示すように3次元立体が得られます。画像は行列形式です。 ${\displaystyle \pi_{i,j}}$

${\displaystyle {\begin{matrix}4&4&3&2&1\\4&3&1&1\\3&2&1\\1\end{matrix}}}$

平面分割は、単位立方体の位置によって記述されることもよくあります。この観点から、平面分割は、内の正の整数格子点 ( i , j , k )の有限部分集合として定義することができ、 ( r , s , t ) が 内にあり、、 、 を満たす場合、 ( i , j , k ) も 内に存在します。 ${\displaystyle {\mathcal {P}}}$${\displaystyle \mathbb {N} ^{3}}$${\displaystyle {\mathcal {P}}}$${\displaystyle (i,j,k)}$${\displaystyle 1\leq i\leq r}$${\displaystyle 1\leq j\leq s}$${\displaystyle 1\leq k\leq t}$${\displaystyle {\mathcal {P}}}$

平面分割の 合計は

${\displaystyle n=\sum _{i,j}\pi _{i,j}.}$

合計は平面分割を構成する立方体の数を記述する。平面分割に関する多くの関心は、さまざまなクラスの平面分割の列挙に関するものである。合計がnである平面分割の数はPL( n )で表される。たとえば、合計が3である平面分割は6つある。

${\displaystyle {\begin{matrix}3\end{matrix}}\qquad {\begin{matrix}2&1\end{matrix}}\qquad {\begin{matrix}1&1&1\end{matrix}}\qquad {\begin{matrix}2\\1\end{matrix}}\qquad {\begin{matrix}1&1\\1\end{matrix}}\qquad {\begin{matrix}1\\1\\1\end{matrix}}}$

したがってPL(3) = 6となる。

平面分割は対称性によって分類できます。平面分割の対称クラスの多くは、単純な積の式で列挙されます。

PL( n )の生成関数は^{[1]である。}

${\displaystyle \sum _{n=0}^{\infty }\operatorname {PL} (n)x^{n}=\prod _{k=1}^{\infty }{\frac {1}{(1-x^{k})^{k}}}=1+x+3x^{2}+6x^{3}+13x^{4}+24x^{5}+\cdots \qquad }$( OEISの配列A000219 )。

この関数はPercy A. MacMahonによって発見されたため、MacMahon 関数と呼ばれることもあります。

この式は、 nの整数分割の数に関するオイラーの積の公式の 2 次元版とみなすことができます。高次元の分割 (つまり、立体分割)については、類似の式は知られていません。^[2]平面分割の漸近解析は、EM Wrightによって初めて計算されました。^{[3] が}大きい については、次の式が得られます^。[a]${\displaystyle n}$

${\displaystyle \operatorname {PL} (n)\sim {\frac {\zeta (3)^{7/36}}{\sqrt {12\pi }}}\ \left({\frac {n}{2}}\right)^{-25/36}\ \exp \left(3\ \zeta (3)^{1/3}\left({\frac {n}{2}}\right)^{2/3}+\zeta '(-1)\right).}$

数値的に評価すると

${\displaystyle \ln \operatorname {PL} (n)\sim 2.00945n^{2/3}-0.69444\ln n-1.4631.}$

1896年頃、マクマホンは平面分割に関する最初の論文で、箱の部分集合である平面分割の生成関数を設定しました。 ^[5]この式は次のように表されます 。${\displaystyle r\times s\times t}$${\displaystyle {\mathcal {B}}(r,s,t)=\{(i,j,k)|1\leq i\leq r,1\leq j\leq s,1\leq k\leq t\}}$$${\displaystyle \sum _{\pi \in {\mathcal {B}}(r,s,t)}q^{|\pi |}=\prod _{i=1}^{r}\prod _{j=1}^{s}{\frac {1-q^{i+j+t-1}}{1-q^{i+j-1}}}}$$

この公式の証明はマクマホンの著書「組み合わせ解析」に記載されている。 ^[6]マクマホンは平面分割の生成関数についても言及している。^[7]生成関数の公式は別の方法でも書け、次のように表される。 $${\displaystyle \sum _{\pi \in {\mathcal {B}}(r,s,t)}q^{|\pi |}=\prod _{i=1}^{r}\prod _{j=1}^{s}\prod _{k=1}^{t}{\frac {1-q^{i+j+k-1}}{1-q^{i+j+k-2}}}}$$

各成分を で乗じ、上記の式でq = 1と設定すると、ボックスに収まる平面分割の 総数は次の積の式に等しくなります。^[8] 平面の場合（t = 1の場合）は、二項係数になります。 ${\displaystyle \textstyle {\frac {1-q}{1-q}}}$${\displaystyle N_{1}(r,s,t)}$${\displaystyle r\times s\times t}$${\displaystyle {\mathcal {B}}(r,s,t)}$ $${\displaystyle N_{1}(r,s,t)=\prod _{(i,j,k)\in {\mathcal {B}}(r,s,t)}{\frac {i+j+k-1}{i+j+k-2}}=\prod _{i=1}^{r}\prod _{j=1}^{s}{\frac {i+j+t-1}{i+j-1}}.}$$

${\displaystyle {\mathcal {B}}(r,s,1)={\binom {r+s}{r}}.}$

一般的な解決策は

${\displaystyle {\begin{aligned}{\mathcal {B}}(r,s,t)&=\prod _{k=1}^{t}{\frac {(r+s+k-1)!(k-1)!}{(r+k-1)!(s+k-1)!}}\\&=\prod _{k=1}^{t}{\frac {{\binom {r+s+k-1}{r+k-1}}{\binom {r+s+k-1}{s+k-1}}}{{\binom {r+s+k-1}{r}}{\binom {s+k-1}{s}}}}\end{aligned}}}$

特殊平面分割には、対称平面分割、巡回平面分割、自己補完平面分割、およびこれらの特性の組み合わせが含まれます。

以降のセクションでは、ボックス内の平面分割の特別なサブクラスの列挙について説明します。これらの記事では、このような平面分割の数を表す表記法を使用します。ここで、r、s、およびt は、検討中のボックスの次元であり、i は検討中のケースのインデックスです。 ${\displaystyle N_{i}(r,s,t)}$

${\displaystyle {\mathcal {S}}_{2}}$は、点の最初の 2 つの座標に作用する順列の群です。この群には、( i , j , k ) をそれ自身に送る恒等変換と、転置 ( i , j , k ) → ( j , i , k ) が含まれます。軌道上の要素の数は で表されます。は、 の作用下にある の要素の軌道の集合を表します。要素 ( i , j , k ) の高さは で定義されます。 高さは、右奥の角から 1 ステップ離れるごとに 1 ずつ増加します。たとえば、角の位置 (1, 1, 1) の高さは 1 で、ht (2, 1, 1) = 2 です。軌道の高さは、軌道上の任意の要素の高さとして定義されます。この高さの表記は、Ian G. Macdonaldの表記とは異なります。^[9]${\displaystyle \eta }$${\displaystyle |\eta |}$${\displaystyle {\mathcal {B}}/{\mathcal {S}}_{2}}$${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {S}}_{2}}$$${\displaystyle ht(i,j,k)=i+j+k-2.}$$

平面分割の Ferrers 図には、置換群の自然な作用があります。これは、すべてのノードの 3 つの座標を同時に置換することに対応します。これにより、整数分割の共役演算が一般化されます。 の作用により、特定の平面分割から新しい平面分割を生成できます。以下に、作用によって生成される 4 の 6 つの平面分割を示します。以下の表現では、最初の 2 つの座標の交換のみが明示されています。 ${\displaystyle {\mathcal {S}}_{3}}$${\displaystyle {\mathcal {S}}_{3}}$${\displaystyle {\mathcal {S}}_{3}}$

${\displaystyle {\begin{smallmatrix}3&1\end{smallmatrix}}\quad {\begin{smallmatrix}3\\1\end{smallmatrix}}\quad {\begin{smallmatrix}2&1&1\end{smallmatrix}}\quad {\begin{smallmatrix}2\\1\\1\end{smallmatrix}}\quad {\begin{smallmatrix}1&1&1\\1\end{smallmatrix}}\quad {\begin{smallmatrix}1&1\\1\\1\end{smallmatrix}}}$

${\displaystyle {\mathcal {C}}_{3}}$巡回置換群と呼ばれ、

${\displaystyle (i,j,k)\rightarrow (i,j,k),\quad (i,j,k)\rightarrow (j,k,i),\quad {\text{and }}\quad (i,j,k)\rightarrow (k,i,j).}$

平面分割は、すべてのi、jに対してπ _i、j = π _j,iである場合に対称的であるといいます。言い換えると、平面分割は の場合に限り対称的です。このタイプの平面分割は、平面x = yに関して対称です。以下は、対称平面分割とその視覚化の例です。 ${\displaystyle \pi }$${\displaystyle (i,j,k)\in {\mathcal {B}}(r,s,t)}$${\displaystyle (j,i,k)\in {\mathcal {B}}(r,s,t)}$

${\displaystyle {\begin{matrix}4&3&3&2&1\\3&3&2&1&\\3&2&2&1&\\2&1&1&&\\1&&&&\end{matrix}}}$

1898年、マクマホンは対称平面分割の母関数に関する予想を定式化した。^[10]この予想はマクマホン予想と呼ばれている。母関数は次のように与えられる。 ${\displaystyle {\mathcal {B}}(r,r,t)}$$${\displaystyle \sum _{\pi \in {\mathcal {B}}(r,r,t)/{\mathcal {S}}_{2}}q^{|\pi |}=\prod _{i=1}^{r}\left[{\frac {1-q^{t+2i-1}}{1-q^{2i-1}}}\prod _{j=i+1}^{r}{\frac {1-q^{2(i+j+t-1)}}{1-q^{2(i+j-1)}}}\right]}$$

マクドナルド^[9]は、パーシー・A・マクマホンの予想は次のように帰着すると指摘した。

${\displaystyle \sum _{\pi \in {\mathcal {B}}(r,r,t)/{\mathcal {S}}_{2}}q^{|\pi |}=\prod _{\eta \in {\mathcal {B}}(r,r,t)/{\mathcal {S}}_{2}}{\frac {1-q^{|\eta |(1+ht(\eta ))}}{1-q^{|\eta |ht(\eta )}}}}$

1972年にエドワード・A・ベンダーとドナルド・E・クヌースは、平面分割の生成関数が最大でr行で行に沿って厳密に減少するという単純な閉じた形式であると予想した^{[11] 。}ジョージ・アンドリュースは、ベンダーとクヌースの予想とマクマホン予想が同等であることを示した^{[12] 。マクマホンの予想は1977年にジョージ・アンドリュースによってほぼ同時に証明され[13]}、後にイアン・G・マクドナルドが別の証明を提示した^[14] 。q = 1と すると、次に示す 計数関数が得られる。${\displaystyle N_{2}(r,r,t)}$

${\displaystyle N_{2}(r,r,t)=\prod _{i=1}^{r}{\frac {2i+t-1}{2i-1}}\prod _{1\leq i<j\leq r}{\frac {i+j+t-1}{i+j-1}}}$

q = 1の場合の証明については、 ジョージ・アンドリュースの論文「対称平面分割に関するマクマホンの予想」を参照してください。^[15]

π は、 i 番目の行がすべての i に対して i 番目の列と共役である場合に、巡回対称と呼ばれます。 i番目の行は通常の分割とみなされます。分割の共役とは、図が分割の転置である分割です。^[9]言い換えると、平面分割は、のときはいつでも ( k , i , j ) と ( j , k , i ) も に属する場合、巡回対称です。以下に、巡回対称平面分割の例とその視覚化を示します。 ${\displaystyle \pi }$${\displaystyle \pi }$${\displaystyle \pi }$${\displaystyle (i,j,k)\in {\mathcal {B}}(r,s,t)}$${\displaystyle {\mathcal {B}}(r,s,t)}$

${\displaystyle {\begin{matrix}6&5&5&4&3&3\\6&4&3&3&1&\\6&4&3&1&1&\\4&2&2&1&&\\3&1&1&&&\\1&1&1&&&\end{matrix}}}$

マクドナルドの予想は、与えられた整数rに対して、周期的に対称な平面分割の数を計算するための公式を提供する。この予想はマクドナルド予想と呼ばれる。 の部分集合である周期的に対称な平面分割の生成関数は、次のように与えられる。 ${\displaystyle {\mathcal {B}}(r,r,r)}$

${\displaystyle \sum _{\pi \in {\mathcal {B}}(r,r,r)/{\mathcal {C}}_{3}}q^{|\pi |}=\prod _{\eta \in {\mathcal {B}}(r,r,r)/{\mathcal {C}}_{3}}{\frac {1-q^{|\eta |(1+ht(\eta ))}}{1-q^{|\eta |ht(\eta )}}}}$

この式は別の方法でも書ける。

${\displaystyle \prod _{\eta \in {\mathcal {B}}(r,r,r)/{\mathcal {C}}_{3}}{\frac {1-q^{|\eta |(1+ht(\eta ))}}{1-q^{|\eta |ht(\eta )}}}=\prod _{i=1}^{r}\left[{\frac {1-q^{3i-1}}{1-q^{3i-2}}}\prod _{j=i}^{r}{\frac {1-q^{3(r+i+j-1)}}{1-q^{3(2i+j-1)}}}\right]}$

1979年、アンドリュースはq = 1の場合のマクドナルド予想を「弱い」マクドナルド予想 として証明した。^[16] 3年後、ウィリアム・H・ミルズ、デイビッド・ロビンズ、ハワード・ラムゼイは論文「マクドナルド予想の証明」でマクドナルド予想の一般ケースを証明した。^[17]の式は「弱い」マクドナルド予想によって与えられる。${\displaystyle N_{3}(r,r,r)}$

${\displaystyle N_{3}(r,r,r)=\prod _{i=1}^{r}\left[{\frac {3i-1}{3i-2}}\prod _{j=i}^{r}{\frac {i+j+r-1}{2i+j-1}}\right]}$

完全に対称な平面分割は、対称かつ巡回対称な平面分割です。これは、図が 3 つの対角平面すべてで対称であることを意味します。言い換えると、 の場合、 ( i、j、k )の 6 つの順列もすべて に含まれます。以下に、完全に対称な平面分割の行列の例を示します。図は、行列を視覚化したものです。 ${\displaystyle \pi }$${\displaystyle (i,j,k)\in {\mathcal {B}}(r,s,t)}$${\displaystyle {\mathcal {B}}(r,s,t)}$

${\displaystyle {\begin{matrix}5&4&4&3&1\\4&3&3&1&\\4&3&2&1&\\3&1&1&&\\1&&&&\end{matrix}}}$

マクドナルドは、 の部分集合である完全に対称な平面分割の総数を発見した。その式は次のように与えられる。 ${\displaystyle {\mathcal {B}}(r,r,r)}$

${\displaystyle N_{4}(r,r,r)=\prod _{\eta \in {\mathcal {B}}(r,r,r)/{\mathcal {S}}_{3}}{\frac {1+ht(\eta )}{ht(\eta )}}}$

1995年にジョン・R・ステムブリッジが初めて^[18]の公式を証明し、その後2005年にジョージ・アンドリュース、ピーター・パウレ、カーステン・シュナイダーによって証明されました。^[19] 1983年頃、アンドリュースとロビンスは独立して、完全対称平面分割の軌道計数生成関数の明示的な積の公式を示しました。^{[20] [21]}この公式は、 1980年に発表されたジョージ・E・アンドリュースの論文「完全対称平面分割」ですでに言及されています。 ^[22]この予想はq-TSPP予想と呼ばれ、次のように与えられます。 ${\displaystyle N_{4}(r,r,r)}$

を対称群とする。その内部に収まる完全対称平面分割の軌道計算関数は、次の式で与えられる。 ${\displaystyle {\mathcal {S}}_{3}}$${\displaystyle {\mathcal {B}}(r,r,r)}$

${\displaystyle \sum _{\pi \in {\mathcal {B}}(r,r,r)/{\mathcal {S}}_{3}}q^{|\pi |}=\prod _{\eta \in {\mathcal {B}}(r,r,r)/{\mathcal {S}}_{3}}{\frac {1-q^{1+ht(\eta )}}{1-q^{ht(\eta )}}}=\prod _{1\leq i\leq j\leq k\leq r}{\frac {1-q^{i+j+k-1}}{1-q^{i+j+k-2}}}.}$

この予想は2011年にクリストフ・コウチャン、マヌエル・カウアーズ、ドロン・ツァイルバーガーによって証明された。^[23]

すべての に対して である場合、平面分割は自己補集合と呼ばれます。積は偶数である必要があります。以下に、自己補集合対称平面分割の例とその視覚化を示します。 ${\displaystyle \pi _{i,j}+\pi _{r-i+1,s-j+1}=t}$${\displaystyle 1\leq i\leq r}$${\displaystyle 1\leq j\leq s}$${\displaystyle r\cdot s\cdot t}$

${\displaystyle {\begin{matrix}4&4&3&2&1\\4&2&2&2&\\3&2&1&&\end{matrix}}}$

リチャード・P・スタンレー^[24]は、自己相補的平面分割の総数に関する公式を推測した。スタンレーによれば、ロビンズもまた、異なるが同等の形式で自己相補的平面分割の総数に関する公式を定式化した。 の部分集合である自己相補的平面分割の総数は、次のように与えられる。 ${\displaystyle N_{5}(r,s,t)}$${\displaystyle {\mathcal {B}}(r,s,t)}$

${\displaystyle N_{5}(2r,2s,2t)=N_{1}(r,s,t)^{2}}$

${\displaystyle N_{5}(2r+1,2s,2t)=N_{1}(r,s,t)N_{1}(r+1,s,t)}$

${\displaystyle N_{5}(2r+1,2s+1,2t)=N_{1}(r+1,s,t)N_{1}(r,s+1,t)}$

r、s、tの積は偶数である必要があります。証明は、スタンレーの論文「平面分割の対称性」に記載されています。 ^{[25] [24]}この証明は、シュア関数 で機能します。スタンレーの自己相補的平面分割の通常の列挙の証明は、を に代入することでq類似体を生成します。^[26]これは、スタンレーのフック内容公式の特別な場合です。^[27]自己相補的平面分割の生成関数は、次のように与えられます。 ${\displaystyle s_{s^{r}}(x)}$${\displaystyle x_{i}=q^{i}}$${\displaystyle i=1,\ldots ,n}$

${\displaystyle s_{\gamma ^{\alpha }}(q,q^{2},\ldots ,q^{n})=q^{\gamma \alpha (\alpha +1)/2}\prod _{i=1}^{\alpha }\prod _{j=0}^{\gamma -1}{\frac {1-q^{i+n-\alpha +j}}{1-q^{i+j}}}}$

この式を

${\displaystyle s_{s^{r}}(x_{1},x_{2},\ldots ,x_{t+r})^{2}\ {\text{ for }}{\mathcal {B}}(2r,2s,2t)}$

${\displaystyle s_{s^{r}}(x_{1},x_{2},\ldots ,x_{t+r})s_{(s+1)^{r}}(x_{1},x_{2},\ldots ,x_{t+r}){\text{ for }}{\mathcal {B}}(2r,2s+1,2t)}$

${\displaystyle s_{s^{r+1}}(x_{1},x_{2},\ldots ,x_{t+r+1})s_{s^{r}}(x_{1},x_{2},\ldots ,x_{t+r+1}){\text{ for }}{\mathcal {B}}(2r+1,2s,2t+1)}$

望ましいq類似ケースを提供します。

平面分割は、周期的に対称かつ自己補完的である場合、周期的に対称な自己補完的と呼ばれます。図は、周期的に対称な自己補完的平面分割を示しており、対応する行列は以下のとおりです。 ${\displaystyle \pi }$

${\displaystyle {\begin{matrix}4&4&4&1\\3&3&2&1\\3&2&1&1\\3&&&\end{matrix}}}$

スタンレーとの個人的なやり取りの中で、ロビンズは、周期的に対称な自己相補平面分割の総数は次のように与えられると推測した。^{[21] [24]}周期的に対称な自己相補平面分割の総数は次のように与えられる。 ${\displaystyle N_{6}(2r,2r,2r)}$

${\displaystyle N_{6}(2r,2r,2r)=D_{r}^{2}}$

${\displaystyle D_{r}}$は交代符号行列の数である。の式は次のように与えられる。 ${\displaystyle r\times r}$ ${\displaystyle D_{r}}$

${\displaystyle D_{r}=\prod _{j=0}^{r-1}{\frac {(3j+1)!}{(r+j)!}}}$

グレッグ・クーパーバーグは1994年にこの公式を証明した。 ^[28]${\displaystyle N_{6}(r,r,r)}$

完全に対称な自己補完的平面分割は、完全に対称かつ自己補完的である平面分割です。たとえば、以下の行列はそのような平面分割であり、添付の図に視覚化されています。

${\displaystyle {\begin{matrix}6&6&6&5&5&3\\6&5&5&3&3&1\\6&5&5&3&3&1\\5&3&3&1&1&\\5&3&3&1&1&\\3&1&1&&&\end{matrix}}}$

この式は、ウィリアム・H・ミルズ、ロビンズ、ハワード・ラムゼイが著書「自己相補的全対称平面分割」で推測した。^[29]完全対称自己相補平面分割の総数は次のように与えられる。 ${\displaystyle N_{7}(r,r,r)}$

${\displaystyle N_{7}(2r,2r,2r)=D_{r}}$

アンドリュースは1994年に論文「平面分割V：TSSCPP予想」でこの公式を証明した。^[30]

• ガウス二項係数
• ボクセル

• G. アンドリュース『分割理論』、ケンブリッジ大学出版局、ケンブリッジ、1998年、ISBN 0-521-63766-X 
• ベンダー、エドワード A.;クヌース、ドナルド E. (1972)、「平面分割の列挙」、組合せ理論ジャーナル、シリーズ A、13 : 40–54、doi :10.1016/0097-3165(72)90007-6、ISSN  1096-0899、MR  0299574
• IG マクドナルド、『対称関数とホール多項式』、オックスフォード大学出版局、オックスフォード、1999 年、ISBN 0-19-850450-0 
• PAマクマホン、「組み合わせ分析」、全2巻、ケンブリッジ大学出版局、1915-16年。

• Weisstein, Eric W.「平面分割」。MathWorld。
• 平面パーティションに関する DLMF ページ