整数分割

1から8までの正の整数の分割に関連するヤング図。正方形の主対角線を鏡映した像が共役分割となるように配置されています

nを最大部分kで分割する

数論と組合せ論において、非負整数nの分割（整数分割とも呼ばれる）は、 n を正の整数の和として表す方法です。被加数の順序のみが異なる2つの和は、同じ分割とみなされます。（順序が重要な場合、和は合成となります。）例えば、4 は次の5つの異なる方法で分割できます。

4

3 + 1

2 + 2

2 + 1 + 1

1 + 1 + 1 + 1

ゼロの唯一の分割は、部分を持たず、空の合計です。

順序に依存する構成1 + 3は3 + 1と同じ分割であり、 2 つの異なる構成1 + 2 + 1と1 + 1 + 2は2 + 1 + 1と同じ分割を表します。

分割における個々の加数は部分と呼ばれます。nの分割数は分割関数p ( n )によって与えられます。したがって、p (4) = 5 となります。λ ⊢ nという表記は、 λがnの分割であることを意味します。

分割は、ヤング図やフェラーズ図を用いてグラフィカルに視覚化することができます。これらは、対称多項式や対称群の研究、そして一般的な群表現論など、数学や物理学の多くの分野で用いられます。

例

5を7つに分けると

• 5
• 4 + 1
• 3 + 2
• 3 + 1 + 1
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1

一部の著者は、分割をプラス記号付きの式ではなく、非増加の被加数の列として扱います。例えば、2 + 2 + 1 という分割は、(2, 2, 1)という組、あるいはさらに簡潔な(2 ² , 1)という形で表記されることもあります。この場合、上付き文字は部分の繰り返し回数を示します。

この分割の多重度表記は とも表記されます。ここで、m ₁は 1 の数、m ₂は 2 の数などです ( m _i = 0の要素は省略できます)。たとえば、この表記では、5 の分割は、および と表記されます。 ${\displaystyle 1^{m_{1}}2^{m_{2}}3^{m_{3}}\cdots }$ ${\displaystyle 5^{1},1^{1}4^{1},2^{1}3^{1},1^{2}3^{1},1^{1}2^{2},1^{3}2^{1}}$ ${\displaystyle 1^{5}}$

パーティションの図式的表現

分割を表す一般的な図式的手法は2つあります。ノーマン・マクロード・フェラーズにちなんで名付けられたフェラーズ図と、アルフレッド・ヤングにちなんで名付けられたヤング図です。どちらも複数の表記法がありますが、ここでは英語表記法を使用し、図を左上隅に配置します。

フェラーズ図

14の6+4+3+1の分割は、次の図で表すことができます

14個の円は4列に並んでおり、それぞれが区画の一部分の大きさを持っています。数字4の5つの区画の図を以下に示します。

4	＝	3 + 1	＝	2 + 2	＝	2 + 1 + 1	＝	1 + 1 + 1 + 1

ヤング図

整数分割の別の視覚的表現は、ヤング図（フェラーズ図とも呼ばれます）です。フェラーズ図のように点で分割を表すのではなく、ヤング図ではボックスまたは正方形を使用します。したがって、5 + 4 + 1の分割のヤング図は次のようになります

一方、同じ分割に対するフェラーズ図は

この一見些細なバリエーションは特に言及するほどの価値はないと思われるが、ヤング図は対称関数や群の表現論の研究において非常に有用であることがわかった。ヤング図のボックスを様々な規則に従って数字（あるいはより複雑なオブジェクト）で埋めていくと、ヤング・タブローと呼ばれるオブジェクトの族が得られ、これらのタブローは組み合わせ論的および表現論的な重要性を持つ。^{[ 1 ]}隣接する正方形を結合して作られる図形の一種であるヤング図は、特殊な種類のポリオミノである。^{[ 2 ]}

分割関数

オイラー法を用いてp (40)を求める：プラスとマイナスの符号が付いた定規（灰色のボックス）を下にスライドし、該当する部分を加算または減算します。符号の位置は、自然数（青）と奇数（オレンジ）の交互の差で表されます。SVGファイルでは、画像の上にマウスを置くと定規が動きます

パーティション関数は 、非負整数 の分割数を数えます。例えば、整数 には、、、の5つの分割数があるためです。この関数の に対する値は次のとおりです。 ${\displaystyle p(n)}$ ${\displaystyle n}$ ${\displaystyle p(4)=5}$ ${\displaystyle 4}$ ${\displaystyle 1+1+1+1}$ ${\displaystyle 1+1+2}$ ${\displaystyle 1+3}$ ${\displaystyle 2+2}$ ${\displaystyle 4}$ ${\displaystyle n=0,1,2,\dots}$

1、1、2、3、5、7、11、15、22、30、42、56、77、101、135、176、231、297、385、490、627、792、1002、1255、1575、1958、2436、3010、3718、4565、5604、...（OEISのシーケンスA000041）。

の生成関数は ${\displaystyle p}$

${\displaystyle \sum _{n=0}^{\infty }p(n)q^{n}=\prod _{j=1}^{\infty }\sum _{i=0}^{\infty }q^{ji}=\prod _{j=1}^{\infty }(1-q^{j})^{-1}.}$

分配関数の閉形式の表現は知られていないが、正確に近似する漸近展開と、厳密に計算できる漸化式の両方が存在する。分配関数は、その引数の平方根の指数関数として増加する。 ^{[ 3 ]}以下のように表される。

${\displaystyle p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right)}$ として${\displaystyle n\to \infty}$

1937年、ハンス・ラーデマッハーは、収束級数によって分配関数を表す方法を発見しました${\displaystyle p(n)}$

$${\displaystyle p(n)={\frac {1}{\pi {\sqrt {2}}}}\sum _{k=1}^{\infty }A_{k}(n){\sqrt {k}}\cdot {\frac {d}{dn}}\left({{\frac {1}{\sqrt {n-{\frac {1}{24}}}}}}\sinh \left[{{\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}}\,\,\,\right]}\right)}$$ ここで

$${\displaystyle A_{k}(n)=\sum _{0\leq m<k,\;(m,k)=1}e^{\pi i\left(s(m,k)-2nm/k\right)}.}$$ はデデキント和です。 ${\displaystyle s(m,k)}$

その生成関数の逆関数はオイラー関数です。オイラーの五角数定理によれば、この関数はその引数の 五角数冪の交代和です

${\displaystyle p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+\cdots }$

シュリニヴァーサ・ラマヌジャンは、分割関数がモジュラー算術において非自明なパターンを持つことを発見しました。これは現在ラマヌジャン合同式として知られています。例えば、の十進表現が4または9で終わる場合、の分割数は5で割り切れます。^{[ 4 ]}${\displaystyle n}$ ${\displaystyle n}$

制約付き分割

組合せ論と数論の両方において、様々な制約を受ける分割族がよく研究されます。^{[ 5 ]} このセクションでは、そのような制約のいくつかを概観します

共役分割と自己共役分割

6 + 4 + 3 + 1 の分割図を主対角線に沿って反転すると、14 の別の分割が得られます。

	↔
6 + 4 + 3 + 1	＝	4 + 3 + 3 + 2 + 1 + 1

行を列に変換すると、数14の分割4 + 3 + 3 + 2 + 1 + 1が得られます。このような分割は互いに共役であると言われています。 ^{[ 6 ]}数4の場合、分割4と1 + 1 + 1 + 1は共役な対であり、分割3 + 1と2 + 1 + 1は互いに共役です。特に興味深いのは、2 + 2のような分割はそれ自体が共役であるということです。このような分割は自己共役であると言われています。^{[ 7 ]}

主張: 自己共役な分割の数は、異なる奇数部分を持つ分割の数と同じです。

証明（概要） : 重要な観察は、すべての奇数部分を中央で 「折り畳んで」自己共役図を形成できることです。

↔

次の例に示すように、異なる奇数部を持つ分割の集合と自己共役分割の集合の間には 一対一の関係が得られます

	↔
9 + 7 + 3	＝	5 + 5 + 4 + 3 + 2
奇数の距離		自己共役

奇数部分と異数部分

8の22の分割のうち、奇数部分のみを含む分割は 6つあります

• 7 + 1
• 5 + 3
• 5 + 1 + 1 + 1
• 3 + 3 + 1 + 1
• 3 + 1 + 1 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

あるいは、同じ数字が複数回出現しない分割を数えることもできます。このような分割は、異なる部分を持つ分割と呼ばれます。8の異なる部分を持つ分割を数えると、6も得られます。

• 8
• 7 + 1
• 6 + 2
• 5 + 3
• 5 + 2 + 1
• 4 + 3 + 1

これは一般的な性質です。各正の数について、奇数部分を持つ分割の数は、異なる部分を持つ分割の数に等しく、q ( n )で表されます。^{[ 8 ] [ 9 ]}この結果は1748年にレオンハルト・オイラーによって証明され、 ^{[ 10 ]}後にグライシャーの定理として一般化されました

あらゆる種類の制限付き分割には、与えられた制限を満たす分割の数を表す関数が存在します。重要な例としては、q ( n )（異なる部分に分割する）が挙げられます。q ( n )の最初のいくつかの値は（ q (0)=1 から始まる）以下の通りです。

1、1、1、2、2、3、4、5、6、8、10、...（OEISのシーケンスA000009）。

q ( n )の生成関数は^{[ 11 ]}で与えられる。

${\displaystyle \sum_{n=0}^{\infty}q(n)x^{n}=\prod_{k=1}^{\infty}(1+x^{k})=\prod_{k=1}^{\infty}{\frac{1}{1-x^{2k-1}}}}.}$

五角数定理はqに対して再帰的定理を与える：^{[ 12 ]}

q ( k ) = a _k + q ( k − 1) + q ( k − 2) − q ( k − 5) − q ( k − 7) + q ( k − 12) + q ( k − 15) − q ( k − 22) − ...

ここで、a _kは、ある整数mに対してk = 3 m ² − mの場合には(−1) ^mとなり、それ以外の場合には 0 となります。

部品のサイズや部品数が制限されている

共役をとると、 nを正確にk 個の部分に分割する数p _k ( n )は、 nのうち最大部分の大きさがkである部分の分割数に等しい。関数p _k ( n )は、次の再帰式を満たす。

p _k ( n ) = p _k ( n − k ) + p _{k −1} ( n − 1 )

初期値はp ₀ (0) = 1、p _k ( n ) = 0である（ n≤0またはk≤0かつnとkが両方とも0ではない場合） 。 ^{[ 13 ]}

関数p ( n )は次のようにし て復元される。

${\displaystyle p(n)=\sum_{k=0}^{n}p_{k}(n).}$

このような分割の可能な生成関数の1つは、kを固定しnを可変とすると、

${\displaystyle \sum _{n\geq 0}p_{k}(n)x^{n}=x^{k}\prod _{i=1}^{k}{\frac {1}{1-x^{i}}}.}$

より一般的には、T が正の整数の集合である場合、 nの分割数（すべての部分がTに属する）は生成関数

${\displaystyle \prod _{t\in T}(1-x^{t})^{-1}.}$

これは、お釣りの問題（集合Tが利用可能な硬貨を指定する）を解くのに使えます。2つの特別なケースとして、 nをすべての部分が1または2に分割する分割数（または、 nを1または2に 分割する分割数）は、

${\displaystyle \left\lfloor {\frac {n}{2}}+1\right\rfloor ,}$

そして、 nをすべての部分が1、2、または3に分割する分割数（または、 nを最大で3つの部分に分割する分割数）は、( n+3)2/12に最も^{近い整数である。 [ 14 ]}

長方形の分割とガウス二項係数

部分の数と大きさを同時に制限することもできる。p ( N , M ; n )は、 n を最大でM個の部分から構成し、それぞれの部分が最大でN 個の部分から成る分割の数を表すものとする。同様に、これらはヤング図がM × N の長方形に収まる分割である。n を最大でN個の部分から正確にM 個の部分に分割し、そのような分割の各部分から 1 を引くと、 n − Mを最大でM個の部分に分割できるという漸化式が 得られる。^{[ 15 ]}$${\displaystyle p(N,M;n)=p(N,M-1;n)+p(N-1,M;n-M)}$$ ${\displaystyle p(N,M;n)-p(N,M-1;n)}$

ガウス二項係数は次のように定義される。 ガウス二項係数はp ( N , M ; n )の生成関数と次の式で 関係している。$${\displaystyle {k+\ell \choose \ell }_{q}={k+\ell \choose k}_{q}={\frac {\prod _{j=1}^{k+\ell }(1-q^{j})}{\prod _{j=1}^{k}(1-q^{j})\prod _{j=1}^{\ell }(1-q^{j})}}.}$$ $${\displaystyle \sum _{n=0}^{MN}p(N,M;n)q^{n}={M+N \choose M}_{q}.}$$

ランク・アンド・ダーフィー広場

パーティションのランクとは、パーティションに少なくとも k 個の部分（サイズが k 以上）が含まれるような最大の数 k です。たとえば、パーティション4 + 3 + 3 + 2 + 1 + 1 はランク 3 です。これは、3 以上の部分が 3 つ含まれているが、4 以上の部分が 4 つ含まれていないためです。ランクrのパーティションの Ferrers 図または Young 図において、左上のr × rの要素の正方形はDurfee 正方形と呼ばれます。

ダーフィーの正方形は、様々な分割恒等式の証明における組合せ論の分野で応用されている。^{[ 16 ]}また、 h指数 の形で実用的な意味も持っている。

分割のランク（またはダイソンランク）と呼ばれる別の統計量もあります。これは、 k個の部分から最大部分を分割した場合の差です。この統計量（上記の統計量とは無関係です）は、ラマヌジャン合同性の研究で用いられます。 ${\displaystyle \lambda _{k}-k}$ ${\displaystyle \lambda _{k}}$

ヤング格子

ヤング図式を包含することで、分割には自然な半順序が与えられる。この半順序集合はヤング格子として知られている。この格子はもともと表現論の文脈で定義され、任意のnに対する対称群S _nの既約表現とその分岐特性を、標数ゼロにおいて記述するために用いられた。また、その純粋に組合せ論的な性質についても重要な研究がなされており、特に微分半順序集合の例として注目されている。

ランダム分割

ロビンソン・シェンステッド対応を介して対称群上の一様確率分布に従って選択されるランダム分割の深い理論があります。1977年、ローガンとシェップ、そしてヴェルシックとケロフは、典型的な大きな分割のヤング図が、特定の汎関数を最小化する特定の解析関数のグラフに漸近的に近づくことを示しました。1988年、バイク、デフト、ヨハンソンはこれらの結果を拡張し、トレーシー・ウィダム分布の観点からランダム順列の最長増加部分列の分布を決定しました。^{[ 17 ]}オクンコフはこれらの結果をリーマン面の組合せ論と表現論に関連付けました。^{[ 18 ] [ 19 ]}

参照

• パーティションのランク、ランクの異なる概念
• パーティションのクランク
• 優勢順序
• 因数分解
• 整数因数分解
• 集合の分割
• 星と棒（組み合わせ論）
• 平面分割
• 連続する整数への分割によって定義されるポライト数
• 乗法分割
• 12倍の方法
• エウェンスの標本抽出法
• ファア・ディ・ブルーノの式
• 多重分割
• ニュートンの恒等式
• 最小部分関数
• ゴールドバッハ分割は、偶数を素数に分割するものである（ゴールドバッハの予想を参照）。
• コスタントの分配関数

注釈

1. Andrews 1976 , p. 199
2. Josuat-Vergès, Matthieu (2010)、「Young図のパターン回避充填間の全単射」、Journal of Combinatorial Theory、Series A、117 (8): 1218– 1230、arXiv : 0801.4928、doi : 10.1016/j.jcta.2010.03.006、MR  2677686、S2CID  15392503。
3. アンドリュース 1976、69ページ
4. ハーディ＆ライト 2008年、380ページ。
5. Alder, Henry L. (1969). 「分割恒等式 - オイラーから現在まで」 . American Mathematical Monthly . 76 (7): 733– 746. doi : 10.2307/2317861 . JSTOR 2317861 . 
6. ハーディ＆ライト 2008年、362ページ。
7. ハーディ＆ライト 2008年、368ページ。
8. ハーディ＆ライト 2008年、365ページ。
9. 表記はAbramowitz & Stegun 1964、p. 825
10. アンドリュース, ジョージ・E. (1971).数論. フィラデルフィア: WBサンダース社. pp.  149–50 .
11. アブラモウィッツ＆ステグン 1964、p. 825、24.2.2 式 I(B)
12. アブラモヴィッツ & ステガン 1964、p. 826、24.2.2当量。 Ⅱ(A)
13. リチャード・スタンレー『列挙的組合せ論』第1巻第2版、ケンブリッジ大学出版局、2012年。第1章1.7節。
14. ハーディ, GH (1920). 『数論のいくつかの有名な問題』 クラレンドン・プレス.
15. アンドリュース 1976、33～34頁。
16. 例えば、 Stanley 1999、p. 58
17. ロミック、ダン (2015).最長増加部分列の驚くべき数学. 数理統計研究所教科書. ニューヨーク: ケンブリッジ大学出版局. ISBN 978-1-107-42882-9。
18. Okounkov, Andrei (2000). 「ランダム行列とランダム順列」. International Mathematics Research Notices . 2000 (20): 1043. doi : 10.1155/S1073792800000532 . S2CID 14308256 
19. Okounkov, A. (2001-04-01). 「無限ウェッジとランダムパーティション」 . Selecta Mathematica . 7 (1): 57– 81. arXiv : math/9907127 . doi : 10.1007/PL00001398 . ISSN 1420-9020 . S2CID 119176413 .  

参考文献

• アブラモウィッツ、ミルトン、ステガン、アイリーン(1964)。『数式、グラフ、数表付き数学関数ハンドブック』。米国商務省、国立標準局。ISBN 0-486-61272-4。
• アンドリュース、ジョージ・E. (1976). 『分割理論』 ケンブリッジ大学出版局. ISBN 0-521-63766-X。
• アンドリュース、ジョージ・E.；エリクソン、キモ（2004年）『整数分割』ケンブリッジ大学出版局、ISBN 0-521-60090-1。
• アポストル、トム・M. (1990) [1976].モジュラー関数と数論におけるディリクレ級数.大学院数学テキスト. 第41巻（第2版）. ニューヨーク他：シュプリンガー・フェアラーク. ISBN 0-387-97127-0. Zbl  0697.10023 .（ラーデマッハーの公式の現代的な教育的入門については第5章を参照）
• ボナ、ミクローシュ(2002). 『組合せ論入門：列挙とグラフ理論入門』 ワールド・サイエンティフィック・パブリッシング. ISBN 981-02-4900-4。（フェラーズグラフの議論を含む、整数分割のトピックへの初歩的な入門）
• ハーディ, GH ;ライト, EM (2008) [1938]. 『数論入門』 . D.R. ヒース＝ブラウンとJ.H. シルバーマンによる改訂.アンドリュー・ワイルズによる序文. (第6版). オックスフォード:オックスフォード大学出版局. ISBN 978-0-19-921986-5. MR  2445243 . Zbl  1159.11001
• Lehmer, DH (1939). 「分配関数の級数の剰余と収束について」 . Trans. Amer. Math. Soc . 46 : 362–373 . doi : 10.1090/ S0002-9947-1939-0000410-9 . MR  0000410. Zbl  0022.20401 .A _k ( n )の主式 (導関数なし)、剰余、および古い形式を提供します。
• Gupta, Hansraj; Gwyther, CE; Miller, JCP (1962).王立数学協会. 表. 第4巻, 分割表.(テキストがあり、参考文献はほぼ完了していますが、彼ら (およびアブラモウィッツ)はホワイトマンにあるA _k ( n )のセルバーグの式を見落としています。)
• マクドナルド、イアン・G. (1979).対称関数とホール多項式. オックスフォード数学モノグラフ.オックスフォード大学出版局. ISBN 0-19-853530-9. Zbl  0487.20007 .（セクションI.1を参照）
• ネイサンソン, MB (2000).数論における初等的方法. 数学大学院テキスト. 第195巻.シュプリンガー・フェアラーク. ISBN 0-387-98912-9 . Zbl  0953.11002
• ラードマッハー、ハンス(1974)。ハンス・ラーデマッハの論文を集めた。 Vol. v II. MITプレス。 pp  . 100–07、108–22、460–75。​​​
• ソートイ、マーカス・デュ（2003年）『素数の音楽』ニューヨーク：ペレニアル・ハーパーコリンズ、ISBN 9780066210704。
• スタンリー、リチャード・P. (1999).列挙的組合せ論. 第1巻および第2巻. ケンブリッジ大学出版局. ISBN 0-521-56069-1。
• Whiteman, AL (1956). 「分配関数の級数と関連した和」 . Pacific Journal of Mathematics . 6 (1): 159–176 . doi : 10.2140/pjm.1956.6.159 . Zbl  0071.04004(セルバーグの公式を提供します。古い形式はセルバーグの有限フーリエ展開です。)

外部リンク

• 「分割」、数学百科事典、EMS Press、2001 [1994]
• パーティションと構成の計算機
• ワイスタイン、エリック・W. 「パーティション」。マスワールド。
• Wilf, Herbert S. Lectures on Integer Partitions (PDF) 、 2021年2月26日にオリジナル(PDF)からアーカイブ、 2021年2月28日取得
• 整数列のオンライン百科事典への参照表を使用した分割によるカウント
• 整数分割 2014年10月22日アーカイブWayback MachineのFindStatデータベースのエントリ
• CPANのInteger::Partition Perl モジュール
• 整数分割を生成するための高速アルゴリズム
• すべてのパーティションの生成：2つのエンコーディングの比較
• グライム、ジェイムス (2016年4月28日). 「Partitions - Numberphile」（ビデオ） .ブレイディ・ハラン.オリジナルより2021年12月11日時点のアーカイブ。 2016年5月5日閲覧。