整数分割

数論と組合せ論において、非負整数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 は}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 つのパーティションの図を以下に示します。

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

一方、同じパーティションのフェラーズ図は

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

パーティション関数は、 非負の整数 のパーティションをカウントします。たとえば、整数 には、、、、および の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 }$

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

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

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

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

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

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

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

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) − ...

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

共役をとると、 nを正確にk個の部分に分割する数p _k ( n )は、 nの最大部分のサイズがkである分割の数に等しい。関数p _k ( n )は、再帰性を満たす。

pk ( n ) = _pk ( n − k ₎ + pk ₋₁ ( 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 )は、最大でM個の部分を持つnの分割の数を表し、各部分は最大で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;nM)}$$${\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です。たとえば、パーティション 4 + 3 + 3 + 2 + 1 + 1 は、3 以上の部分が 3 つ含まれますが、4 以上の部分が 4 つ含まれないため、ランクは 3 です。ランクrのパーティションの Ferrers 図または Young 図では、左上のr × rの要素の正方形はDurfee 正方形として知られています。

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

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

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

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

ウィキメディア・コモンズには、整数分割に関連するメディアがあります。

• アブラモウィッツ、ミルトン、ステグン、アイリーン(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.ZBL0697.10023  。​ (ラデマッハーの公式の現代的な教育的紹介については第 5 章を参照してください)。
• ボナ、ミクローシュ(2002)。組合せ論のウォークスルー: 列挙とグラフ理論入門。ワールドサイエンティフィック出版。ISBN 981-02-4900-4。(フェラーズグラフの議論を含む整数分割のトピックの初歩的な紹介)
• ハーディ、GH ;ライト、EM (2008) [1938].数論入門. DR ヒースブラウンとJH シルバーマンによる改訂.アンドリュー・ワイルズによる序文. (第6版). オックスフォード:オックスフォード大学出版局. ISBN 978-0-19-921986-5MR 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.ZBL0487.20007  。​（セクションI.1を参照）
• ネイサンソン、MB (2000)。数論における初等的方法。数学の大学院テキスト。第195巻。​​シュプリンガー出版。ISBN 0-387-98912-9.ZBL0953.11002  .​
• ラードマッハー、ハンス(1974)。ハンス・ラーデマッハーの論文を集めました。 Vol. v II. MITプレス。 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-02-24 にオリジナルからアーカイブ(PDF)され、2021-02-28に取得
• 整数列のオンライン百科事典への参照表を使用したパーティションによるカウント
• FindStat データベースの整数パーティション エントリ
• CPANの Integer::Partition Perl モジュール
• 整数パーティションを生成するための高速アルゴリズム
• すべてのパーティションの生成: 2 つのエンコードの比較
• グライム、ジェイムス (2016年4月28日). 「Partitions - Numberphile」(ビデオ) .ブレイディ・ハラン. 2021年12月11日時点のオリジナルよりアーカイブ。 2016年5月5日閲覧。