合成（組合せ論）

数学において、整数nの合成とは、 n を（厳密に）正の整数の列の和として記述する方法です。項の順序が異なる 2 つの列は、その和の異なる合成を定義しますが、その数の同じ整数分割を定義するものと見なされます。すべての整数には、有限個の異なる合成があります。負の数には合成はありませんが、0 には空の列という 1 つの合成があります。各正の整数n には、 2 ^{n −1 個}の異なる合成があります。

整数nの弱い合成はnの合成に似ていますが、シーケンスの項が 0 になることを許可します。これは、n を非負の整数のシーケンスの和として記述する方法です。結果として、すべての正の整数は、（長さが制限されていない場合）無限個の弱い合成を許容します。弱い合成の末尾にいくつかの項 0 を追加しても、通常は別の弱い合成を定義するとは見なされません。言い換えると、弱い合成は項 0 によって暗黙的に無限に拡張されると想定されます。

さらに一般化すると、 （非負または正の）整数の部分集合Aに対する整数nのA制限合成は、合計がnであるA内の 1 つ以上の要素の順序付き集合である。^[1]

5 つの 16 の構成は次のとおりです。

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

これを 5 の 7 つのパーティションと比較します。

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

構成の部分に制約を課すことも可能です。たとえば、5 つの別個の用語に分割された 5 つの構成は次のとおりです。

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

これを、5 を 3 つの別々の項に分割したものと比較します。

• 5
• 4 + 1
• 3 + 2。

古代サンスクリットの賢者は、フィボナッチより何年も前に、任意の自然数 n を 1 と 2 の合計として構成する数が n 番目のフィボナッチ数であることを発見していたことに注意してください。数字が 1 と 2 のみに制限されているため、これらは上記で定義した一般的な構成ではないことに注意してください。

• 1=1 (1)
• 2=1+1=2 (2)
• 3=1+1+1=1+2=2+1 (3)
• 4=1+1+1+1=1+1+2=1+2+1=2+1+1=2+2 (5)
• 5=1+1+1+1+1=1+1+1+2=1+1+2+1=1+2+1+1=2+1+1+1=1+2+2= 2+1+2=2+2+1 (8)
• 6 の場合は 13 通りの組み合わせになります。

慣例的に、空の合成は 0 の唯一の合成として数えられ、負の整数の合成は存在しません。n ≥ 1の合成は2 ^{n −1}通りあります。 証明は次のとおりです。

 配列の n − 1個のボックスのそれぞれにプラス記号またはカンマを配置する

${\displaystyle {\big (}\,\overbrace {1\,\square \,1\,\square \,\ldots \,\square \,1\,\square \,1} ^{n}\,{\big )}}$

は、 nの一意の合成を生成します。逆に、nのすべての合成は、プラスとカンマの割り当てを決定します。 n − 1 のバイナリ選択肢があるため、結果は次のようになります。同じ議論から、 n を正確にk個の部分に 合成する数( k -合成) は、二項係数 によって与えられることがわかります。すべての可能な部分の数を合計すると、 nの合成の総数として2 ^{n −1}が得られることに注意してください。 ${\displaystyle {n-1 \choose k-1}}$

${\displaystyle \sum _{k=1}^{n}{n-1 \choose k-1}=2^{n-1}.}$

弱い合成の場合、その数は である。なぜなら、 n  +  kの各k合成は、規則により nの弱い合成に対応する からである。${\displaystyle {n+k-1 \choose k-1}={n+k-1 \choose n}}$

${\displaystyle a_{1}+a_{2}+\ldots +a_{k}=n+k\quad \mapsto \quad (a_{1}-1)+(a_{2}-1)+\ldots +(a_{k}-1)=n}$

この式から、 n を正確にk個の部分に弱合成する数は、k − 1 を正確にn + 1 個の部分に弱合成する数に等しいことがわかります。

A制限合成では、 nを正確にk個の部分に合成する数は拡張二項式（または多項式）係数 で与えられ、ここで角括弧はそれに続く多項式におけるの係数の抽出を示す。 ^[2]${\displaystyle {\binom {k}{n}}_{(1)_{a\in A}}=[x^{n}]\left(\sum _{a\in A}x^{a}\right)^{k}}$${\displaystyle x^{n}}$

K体上のn変数のd次同次多項式のベクトル空間の次元は、のn部分への弱合成の数です。実際、この空間の基底は、となる単項式の集合によって与えられます。指数は0 になることが許されるため、このような単項式の数は、 の弱合成の数とまったく同じです。 ${\displaystyle K[x_{1},\ldots,x_{n}]_{d}}$${\displaystyle x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}}$${\displaystyle d_{1}+\ldots +d_{n}=d}$${\displaystyle d_{i}}$

• 星と棒（組み合わせ論）

• Heubach, Silvia; Mansour, Toufik (2009)。「合成と単語の組合せ論。離散数学とその応用。」フロリダ州ボカラトン：CRC Press。ISBN 978-1-4200-7267-9.ZBL1184.68373  。​

• パーティションと構成の計算機