組み合わせ数体系

数学、特に組合せ論において、k次（ある正の整数kに対して）の組合せ数体系は、組合せ論、あるいは整数のマコーレー表現とも呼ばれ、自然数（0 を含む）Nとk 個の組み合わせとの間の対応関係である。組み合わせは、c _k  > ... >  c ₂  >  c _{1 ≥ 0 という}厳密な減少列として表され 、各c _{i は}、与えられたk個の組み合わせで選択された要素のインデックスに対応する。異なる数は異なるk個の組み合わせに対応し、それらを辞書式順序で生成する。 より小さい数は、{0, 1, ..., n − 1 }のすべてのk 個の組み合わせに対応する。対応関係は、 k 個の組み合わせが取り出される集合のサイズnに依存しない ため、 NからNから取り出されるk 個の組み合わせへの写像として解釈できる。この観点からは、対応関係は一対一である。 ${\displaystyle {\tbinom {n}{k}}}$

( c _k , ..., c ₂ , c ₁ )に対応する数Nは次のように与えられる。

${\displaystyle N={\binom {c_{k}}{k}}+\cdots +{\binom {c_{2}}{2}}+{\binom {c_{1}}{1}}}$。

一意のシーケンスが任意の非負数Nに対応するという事実は、DH Lehmerによって初めて観察されました。^[1]実際、貪欲アルゴリズムは、 Nに対応するk の組み合わせを見つけます。つまり、で最大のc _kを取り、次に で最大のc _{k −1}を取り、というように行います。上記の式を使用して、k の組み合わせ ( c _k、...、c ₂、c ₁ ) から数N を見つけることは、「ランキング」とも呼ばれ、反対の操作 (貪欲アルゴリズムによって行われる) は「アンランキング」と呼ばれます。これらの操作は、ほとんどのコンピュータ代数システムおよび計算数学でこれらの名前で知られています。^{[2] [3]}${\displaystyle {\tbinom {c_{k}}{k}}\leq N}$${\displaystyle {\tbinom {c_{k-1}}{k-1}}\leq N-{\tbinom {c_{k}}{k}}}$

もともと使われていた用語「整数の組み合わせ表現」は、クヌース^{[4]によって「組み合わせ数システム」に短縮されました。クヌース[5]} はさらに古い参考文献も示しています。 「組み合わせ」という用語は、ジェームズ・マカフリー^[6]によって導入されました（以前の用語や研究を参照せずに）。

階乗数システムとは異なり、 k次の組み合わせ数システムは混合基数システムではありません。つまり、数値Nのうち「数字」c _iで表される部分は、単純に位取り値を掛け算することによって得られるものではありません。 ${\displaystyle {\tbinom {c_{i}}{i}}}$

組合せ数システムの主な用途は、辞書式順序で特定の位置にあるk組合せを、その前のk組合せを明示的にリストしなくても迅速に計算できることです。これにより、たとえば、特定のセットのk組合せをランダムに生成できます。 k組合せの列挙には多くの用途があり、その中にはソフトウェア テスト、サンプリング、品質管理、宝くじゲーム の分析などがあります。

集合Sのk組み合わせは、 k個の（異なる）要素を持つSのサブセットです。組み合わせ数システムの主な目的は、n個の要素を持つ集合 S のすべての可能な k 組み合わせを、それぞれ単一の数で表現することです。任意のn、{0, 1, ..., n  − 1 } をそのような集合として選択すると、与えられたk組み合わせCの表現がnの値に依存しないようにすることができます（ただし、n は十分に大きくなければなりません）。言い換えると、 nを増やすことによってC をより大きな集合のサブセットと見なしても、 C を表す数は変わりません 。したがって、組み合わせ数システムでは、n を明示的に指定することなく、C をすべての自然数の集合Nのk組み合わせと見なすだけです。 ${\displaystyle {\tbinom {n}{k}}}$

{0, 1, ..., n  − 1 }のk 個の組み合わせを表す数が、{0, 1, ..., n  − 1 }に含まれないk個の組み合わせを表す数よりも小さくなるようにするには、 k個の組み合わせを、その最大の要素が最初に比較されるように順序付ける必要があります。この特性を持つ最も自然な順序付けは、要素の降順の辞書式順序付けです。したがって、5 個の組み合わせC  = {0,3,4,6,9} とC ′ = {0,1,3,7,9} を比較すると、C はC ′の前に来ます。これは、どちらも最大の部分 9 は同じですが、Cの次に大きい部分 6 は、 C ′の次に大きい部分 7 よりも小さいためです。辞書式に比較したシーケンスは、(9,6,4,3,0) と (9,7,3,1,0) です。

この順序を記述する別の方法は、組み合わせを数値の2進表現におけるkビットの累乗を記述するものと見なすことです。つまり、C  = { c ₁ , ..., c _k }は数値を記述します。

${\displaystyle 2^{c_{1}}+2^{c_{2}}+\cdots +2^{c_{k}}}$

(これにより、すべての有限の自然数の集合に異なる数が関連付けられます)。次に、関連付けられた 2 進数を比較することによって、 kの組み合わせの比較を行うことができます。例では、CとC ′ は、数 1001011001 ₂  = 601 ₁₀と 1010001011 ₂  = 651 ₁₀に対応しており、これもC がC ′ の前に来ることを示しています。ただし、この数は、 k の組み合わせを表すものではありません。多くの 2 進数は、 kとは異なる数の上げられたビットを持つためです。必要なのは、 k の組み合わせ(のみ) の順序付きリスト内でのCの相対的な位置です。

k次組合せ数体系でk組合せCに関連付けられた数は、指定された順序でCより厳密に小さいk組合せの数です。この数は、次のようにc _k  > ... > c ₂ > c _1のC  = { c _k , ..., c ₂ , c ₁ }から計算できます。

順序の定義から、Cより厳密に小さい 各k組み合わせSに対して、  c _iがSに存在せず、c _k、...、c _{i +1が}Sに存在し、 c _iより大きい他の値は存在しないという一意のインデックスi が存在することがわかります。したがって、これらのk組み合わせS をiの可能な値 1、2、...、kに従ってグループ化し、各グループを個別にカウントできます。iの特定の値に対して、 c _k、...、c _{i +1 が}Sに含まれ 、Sの残りのi個の要素はc _iより厳密に小さいc _i個の非負整数から選択する必要があります。さらに、このような選択を行うと、 Cより厳密に小さい k組み合わせSが生成されます。可能な選択の数は であり、これはグループi内の組み合わせの数です。したがって、 Cより厳密に小さいk組み合わせの総数は ${\displaystyle {\tbinom {c_{i}}{i}}}$

${\displaystyle {\binom {c_{1}}{1}}+{\binom {c_{2}}{2}}+\cdots +{\binom {c_{k}}{k}},}$

これは、 k の組み合わせの順序付きリスト内のCのインデックス (0 から始まる) です。

明らかに、すべてのN  ∈  Nに対して、リストのインデックス Nにちょうど 1 つのk組み合わせが存在します( リストは無限であるため、k ≥ 1 と仮定)。したがって、上記の議論は、すべてのNが、指定された形式のk 個の二項係数の和として正確に 1 つの方法で表すことができることを証明しています。

与えられた式により、与えられたk の組み合わせの辞書式順序における位置をすぐに見つけることができます。与えられた位置Nにおけるk の組み合わせを見つける逆のプロセスは、多少手間がかかりますが、それでも簡単です。辞書式順序の定義により、最大要素c _kが異なる 2 つのk の組み合わせは、それらの最大要素の比較に従って順序付けられます。このことから、最大要素の値が固定されているすべての組み合わせは、リスト内で連続していることがわかります。さらに、最大要素がc _kである最小の組み合わせは であり、 すべてのi  <  kに対してc _i  =  i − 1 となります(この組み合わせでは、式内の を除くすべての項はゼロです)。したがって、c _{k は}となる最大の数です。k > 1 の場合、kの組み合わせ の残りの要素は、次数k − 1の組み合わせ数体系の数に対応するk − 1 の組み合わせを形成するため、 Nと k の代わりに、およびk − 1について同じ方法を続けることで見つけることができます 。 ${\displaystyle {\tbinom {c_{k}}{k}}}$${\displaystyle {\tbinom {c_{k}}{k}}}$${\displaystyle {\tbinom {c_{k}}{k}}\leq N}$${\displaystyle N-{\tbinom {c_{k}}{k}}}$${\displaystyle N-{\tbinom {c_{k}}{k}}}$

位置 72 の 5 つの組み合わせを決定したいとします。n = 4、5、6、... の場合の の連続する値は、 0、1、6、21、56、126、252  、... であり、n  = 8 の場合、72 を超えない最大の値は 56 です。したがってc ₅  = 8 となり、残りの要素は位置72 − 56 = 16の4 つの組み合わせを形成します。n = 3、4、5、...の場合のの連続する値は 、0、1、5、15、35、... であり、n  = 6 の場合、16 を超えない最大の値は 15 なので、c _{4 = 6 となります。同様にして位置}16 − 15 = 1 の 3 つの組み合わせの検索を続けると、c ₃ = 3が見つかり 、最後の単位を使い果たします。これにより が成立し、残りの値c _{i は}となる最大値、つまりc _i = i − 1になります。したがって、5 つの組み合わせ{8, 6, 3, 1, 0 }が見つかりました。 ${\displaystyle {\tbinom {n}{5}}}$${\displaystyle {\tbinom {n}{4}}}$${\displaystyle 72={\tbinom {8}{5}}+{\tbinom {6}{4}}+{\tbinom {3}{3}}}$${\displaystyle {\tbinom {c_{i}}{i}}=0}$

それぞれの宝くじの組み合わせc ₁  <  c ₂  <  c ₃  <  c ₄  <  c ₅  <  c ₆には、 0からNまでの リスト番号があり、これは次の式で求められます。 ${\displaystyle {\binom {49}{6}}}$${\displaystyle {\binom {49}{6}}-1}$

${\displaystyle {\binom {49-c_{1}}{6}}+{\binom {49-c_{2}}{5}}+{\binom {49-c_{3}}{4}}+{\binom {49-c_{4}}{3}}+{\binom {49-c_{5}}{2}}+{\binom {49-c_{6}}{1}}.}$

• 階乗数法（階乗数法とも呼ばれる）
• 原始数体系
• 非対称の記数法- 自然数との組み合わせなど、データ圧縮に広く使用されている。

• Huneke, Craig; Swanson, Irena (2006)、「付録 5」、イデアル、環、およびモジュールの積分閉包、ロンドン数学協会講義ノートシリーズ、第 336 巻、ケンブリッジ、英国: Cambridge University Press、ISBN 978-0-521-68860-4、MR  2266432
• カヴィリア、ジュリオ (2005)、「イーキンとササエの定理とグリーンの超平面制限定理」、可換代数: 幾何学、ホモロジー、組合せ論、計算の側面、CRC プレス、ISBN 978-1-420-02832-4
• グリーン、マーク (1989)、「線型級数の超平面への制限、およびマコーレーとゴッツマンのいくつかの結果」、代数曲線と射影幾何学、数学講義ノート、第 1389 巻、シュプリンガー、pp. 76–86、doi :10.1007/BFb0085925、ISBN 978-3-540-48188-1