12倍の道

組合せ論において、十二法とは、2つの有限集合に関する12の関連する列挙問題の体系的な分類であり、これには、集合または数の順列、組み合わせ、多重集合、および分割を数える という古典的な問題が含まれます。この分類のアイデアはジャン・カルロ・ロータによるもので、名前はジョエル・スペンサーによって提案されました。^[1]

NとX を有限集合とします。集合の濃度を と とします。したがって、 Nはn個の要素を持つ集合であり、X はx個の要素を持つ集合です。 ${\displaystyle n=|N|}$${\displaystyle x=|X|}$

私たちが考える一般的な問題は、関数の同値類の列挙です。 ${\displaystyle f:N\to X}$

関数には、次の 3 つの制限のいずれかが適用されます。

• 条件なし: N内の各a はfによってX内の任意のbに送信され、各b は複数回出現する可能性があります。
• fは単射です。つまり、 N内のaの各値は他のすべてと異なる必要があり、したがって、X内の各b はfの像に最大で 1 回しか出現できません。${\displaystyle f(a)}$
• fは全射です。つまり、 Xの各bに対して、 Nにはとなるaが少なくとも 1 つ存在しなければなりません。したがって、各b はfの像に少なくとも 1 回出現します。${\displaystyle f(a)=b}$

(条件「fは全単射である」は の場合にのみ選択肢となりますが、その場合「 fは単射である」と「fは全単射である」の両方と同等になります。) ${\displaystyle n=x}$

NからXへの関数fの集合には4 つの異なる同値関係が定義されます。

• 平等;
• Nの順列までの等式。
• Xの順列までの等式;
• NとXの順列までの等式。

関数に関する 3 つの条件と 4 つの同値関係は、3 × 4 = 12通りの組み合わせが可能です。

関数の同値類を数える 12 の問題には、同じ困難さは伴わず、それらを解くための体系的な方法も 1 つもありません。問題のうち 2 つは自明であり (同値類の数は 0 または 1)、5 つの問題はnとxの乗法式で答えられ、残りの 5 つの問題は組み合わせ関数 (スターリング数と、指定された数の部分の分割関数)で答えられます。

この設定に古典的な列挙問題を組み込む方法は次のとおりです。

• Xのn順列（つまり、部分順列または繰り返しのないシーケンス）を数えることは、N → X への入射関数を数えることと同じです。
• Xのn 通りの組み合わせを数えることは、N の順列までの N → X の単射関数を数えることと同等です。
• 集合Xの順列を数えることは、 n = xのときの単射関数N → X を数えることと同等であり、またn = xのときの全射関数 N → X を数えることと同等です。
• X内の要素のサイズnの多重集合 (繰り返しを含むn組み合わせとも呼ばれる) を数えることは、N の順列までのすべての関数 N → X を数えることと同じです。
• 集合NをX個の部分集合に分割することを数えることは、X の順列までのすべての全射関数 N → X を数えることと同等です。
• 数n をx個の部分に合成したものを数えることは、N の順列までのすべての射影関数 N → X を数えることと同等です。

十二の道におけるさまざまな問題は、さまざまな観点から検討することができます。

伝統的に、12 通りの方法の問題の多くは、関数を定義する代わりに、ボールをボックス (または同様の視覚化) に配置するという観点から定式化されてきました。集合N はボールの集合、X はボックスの集合と同一視できます。関数は、各ボールをボックス に入れることによって、ボックスにボールを分配する方法を記述します。関数は、そのドメイン内の各値に一意のイメージを割り当てます。この特性は、どのボールも 1 つのボックスにしか入れられない (ボールがボックスの外に出てはいけないという要件とともに) という特性に反映されていますが、どのボックスも任意の数のボールを収容できます。さらに、が単射であることを要求するということは、1 つのボックスに複数のボールを入れることを禁止することを意味します。一方、が全射であることを要求するということは、すべてのボックスに少なくとも 1 つのボールが含まれることを要求することを意味します。 ${\displaystyle f:N\to X}$${\displaystyle f(a)}$${\displaystyle f}$${\displaystyle f}$

NまたはXの順列を法として数えることは、それぞれボールまたはボックスを「区別できない」と呼ぶことによって反映されます。これは不正確な表現ですが、ボールまたはボックスの交換によって 1 つの構成を他の構成に変換できる場合、異なる構成を別々に数えるべきではないことを示すことを目的としています。この変換の可能性は、順列による動作によって形式化されます。

いくつかのケースを考える別の方法は、統計学におけるサンプリングの観点から見ることです。X 個のアイテム (または人)からなる母集団を想像してください。その中からN 個を選びます。通常、「復元抽出法」と「非復元抽出法」と呼ばれる 2 つの異なる方式が説明されます。前者の場合 (復元抽出法)、アイテムを選択したら、それを母集団に戻して、再度選択できるようにします。その結果、各選択は他のすべての選択から独立しており、標本の集合は技術的には独立同一分布と呼ばれます。ただし、後者の場合、アイテムを選択したら、それを脇に置いて再度選択できないようにします。つまり、アイテムを選択するという行為は、その後のすべての選択に影響を及ぼします (特定のアイテムを再度見ることはできません)。そのため、選択は互いに依存しています。

サンプリング方式の 2 番目の違いは、順序が重要かどうかです。たとえば、10 個のアイテムがあり、そのうち 2 つを選択する場合、順序が重要であれば、選択肢 (4, 7) は (7, 4) とは異なります。一方、順序が重要でない場合は、選択肢 (4, 7) と (7, 4) は同等です。

以下の表の最初の 2 行と 2 列は、置換ありと置換なし、順序の考慮ありと考慮なしのサンプリングに対応しています。置換ありのサンプリングの場合は、「任意」というラベルの付いた列に、置換なしのサンプリングの場合は、「単射」というラベルの付いた列にあります。順序が重要な場合は、「個別」というラベルの付いた行に、順序が重要でない場合は、「S _n軌道」というラベルの付いた行にあります。各表のエントリは、特定のサンプリング スキームで、選択セットがいくつあるかを示しています。これらの表のエントリのうち 3 つは、確率分布にも対応しています。順序が重要な置換ありのサンプリングは、それぞれがX倍のカテゴリ分布を持つN個の個別のランダム変数の結合分布を記述することに相当します。ただし、順序が重要でない置換ありのサンプリングは、各カテゴリの出現数のみが重要な、X 倍のカテゴリからの N 個の抽出の単一の多項分布を記述することに相当します。順序が重要でない置換なしのサンプリングは、単一の多変量超幾何分布に相当します。順序が重要な非復元サンプリングは、確率分布に対応していないようです。^{[2]すべての単射ケース（非復元サンプリング）では、} N ≤ X でない限り、選択セットの数はゼロです。（上記のケースで「比較可能」とは、対応する分布のサンプル空間の各要素が別々の選択セットに対応することを意味し、したがって、適切なボックス内の数字は、特定の分布のサンプル空間のサイズを示します。） ${\displaystyle f}$${\displaystyle f}$

サンプリングの観点から見ると、「全射」というラベルの付いた列はやや奇妙です。基本的に、各アイテムを少なくとも 1 回選択するまで、復元サンプリングを続けます。次に、選択した回数を数え、それがNに等しくない場合は、セット全体を破棄して繰り返します。これは、クーポン収集者の問題に漠然と似ています。この問題では、各クーポンが少なくとも 1 回見られるまで、 X 枚のクーポンのセットを「収集」(復元サンプリングによって) します。すべての全射の場合、選択セットの数は、N ≥ Xでない限りゼロです。 ${\displaystyle f}$

関数は、XまたはNの観点から考えることができます。これにより、異なるビューが生成されます。 ${\displaystyle f:N\to X}$

• 関数はNの各要素にXの要素でラベルを付けます。${\displaystyle f}$
• この関数は、 Nの各要素に対して集合Xの要素を選択します。つまり、選択肢は合計でn個になります。${\displaystyle f}$
• この関数は、Xの同じ要素にマップされるNの要素をグループ化します。${\displaystyle f}$

これらの観点は、すべてのケースに等しく適しているわけではありません。ラベル付けと選択の観点は、 Xの要素の順列とは互換性がありません。これは、これによってラベルまたは選択が変わるためです。一方、グループ化の観点は、Xの要素が自由に順列化されない限り、構成に関する完全な情報を提供しません。ラベル付けと選択の観点は、 Nが順列化されていない場合はほぼ同等ですが、 N が順列化されている場合は、選択の観点の方が適しています。その場合、選択は順序なしの選択と見なすことができます。つまり、 Xからのn要素の (複数) セットから 1 回選択することになります。

Nの要素のラベル付けとして見ると、後者はシーケンスに並べられ、Xからのラベルがそれらに連続的に割り当てられていると考えられます。が単射であるという要件は、ラベルを 2 回使用できないことを意味します。結果は、繰り返しのないラベルのシーケンスになります。このような要件がない場合、「繰り返しのあるシーケンス」という用語が使用され、ラベルは複数回使用できます (ただし、繰り返しのないシーケンスも許可されます)。 ${\displaystyle f}$${\displaystyle f}$

Xの要素の順序付けられていない選択として表示すると、同じ種類の区別が適用されます。が単射でなければならない場合、選択にはXのn 個の異なる要素が含まれる必要があるため、これはサイズnのXのサブセットであり、n組み合わせとも呼ばれます。 この要件がなければ、 Xの同じ要素が選択で複数回出現する可能性があり、結果はXからの要素のサイズnの多重セットであり、n多重組み合わせまたは繰り返しのあるn組み合わせとも呼ばれます。 ${\displaystyle f}$${\displaystyle f}$

全射であるという要件は、 Nの要素にラベルを付けるという観点からは、すべてのラベルが少なくとも 1 回は使用される必要があることを意味します。また、Xからの選択という観点からは、Xのすべての要素が少なくとも 1 回は選択に含まれなければならないことを意味します。全射によるラベル付けは、Nの要素をグループ化し、各グループにXの要素をラベル付けすることと同等であり、したがって数学的に記述するのはやや複雑になります。 ${\displaystyle f}$

Nの要素のグループ化として見ると( Xの順列で同一視されると仮定)、射影的であることが要求されるということは、グループの数がちょうどxでなければならないことを意味します。この要件がない場合、グループの数は最大でxになります。入射的であることが要求されるということは、 Nの各要素がそれ自体でグループでなければならないことを意味します。これにより、有効なグループ化が最大で 1 つ残り、したがってあまり面白くないカウント問題になります。 ${\displaystyle f}$${\displaystyle f}$${\displaystyle f}$

さらに、Nの順列で を識別すると、グループ自体は忘れて、サイズだけを保持することになります。これらのサイズはさらに決まった順序ではなく、同じサイズが複数回出現する場合があります。それらを弱減少する数のリストに並べることを選択できます。その合計は数nです。これにより、数nを正確にx 個(射影の場合) または最大でx 個(任意の場合) の部分 に分割するという組み合わせ論的概念が得られます。${\displaystyle f}$${\displaystyle f}$

12 段階の方法のさまざまなケースの公式は、次の表にまとめられています。各表のエントリは、公式を説明する下のサブセクションにリンクしています。

使用される特定の表記は次のとおりです。

• 階乗の減少 、${\textstyle x^{\underline {n}}={\frac {x!}{(xn)!}}=x(x-1)(x-2)\cdots (x-n+1)}$
• 上昇する 階乗、${\textstyle x^{\overline {n}}={\frac {(x+n-1)!}{(x-1)!}}=x(x+1)(x+2)\cdots (x+n-1)}$
• 階乗​ ${\textstyle n!=n^{\underline {n}}=n(n-1)(n-2)\cdots 1}$
• 第二種スターリング数 。n個の要素の集合をk個の空でない部分集合に分割する方法の数を表す。${\textstyle \left\{{n \atop k}\right\}}$
• 二項係数 ${\textstyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}}$
• アイバーソン括弧[ ] は真理値を0または1としてエンコードします
• nをkに分割する回数​${\textstyle p_{k}(n)}$

これは、さまざまなケースの意味を簡単にまとめたものです。各ケースの詳細については、以下を参照してください。

X 個の番号付きアイテム (1 からxまで番号が付けられている)のセットを考えます。その中からn 個を選択すると、アイテムの順序付きリストが生成されます。たとえば、個のアイテムを選択した場合、結果はリスト (5, 2, 10) になる可能性があります。次に、このようなリストがいくつ存在するかを数えます。その際、場合によっては、最初にリストを変換して、異なる可能性の数を減らします。 ${\displaystyle x=10}$${\displaystyle n=3}$

列の意味は次のようになります。

任意のf

アイテムを選択した後は、再度選択できるように元に戻します。

単射のf

アイテムを選択した後は、それを脇に置いて再度選択することはできません。したがって、 n個の異なるアイテムが存在することになります。したがって、 でない限り、リストをまったく選択することはできません。${\displaystyle n\leq x}$

射影f

項目を選択した後、それを元に戻すので、再度選択することができますが、最終的には、各項目を少なくとも 1 回は選択していることになります。したがって、 でない限り、リストはまったく選択できません。${\displaystyle n\geq x}$

行の意味は次のとおりです。

明確な

リストはそのままにして、直接カウントします。

S _n軌道

数える前に、順序が重要にならないように、選択したアイテムのアイテム番号でリストを並べ替えます。例: (5, 2, 10)、(10, 2, 5)、(2, 10, 5) → (2, 5, 10)。

S _x軌道

数える前に、最初に見たアイテムに 1、2 番目に見たアイテムに 2 というように、見たアイテムに番号を付け直します。アイテムが複数回見られた場合には、番号が重複することがあります。たとえば、(3, 5, 3)、(5, 2, 5)、(4, 9, 4) → (1, 2, 1) ですが、(3, 3, 5)、(5, 5, 3)、(2, 2, 9) → (1, 1, 2) となります。

S _n × S _x軌道

2 つのリストは、上記のように並べ替えとラベル付けの両方を行って同じ結果が生成される場合、同じものとしてカウントされます。たとえば、(3, 5, 3) と (2, 9, 9) は、(3, 3, 5) と (9, 9, 2) に並べ替えることができ、その後両方をラベル付けし直すと、同じリスト (1, 1, 2) が生成されるため、同じものとしてカウントされます。

下の表は上の表に似ていますが、公式を示す代わりに、よく知られているボールとボックスの例を使用して、その意味を直感的に理解できるようにします。行は、ボールとボックスの区別を表します。列は、マルチパック (1 つのボックスに複数のボール) または空のボックスが許可されているかどうかを表します。表のセルには、上の公式表に示されている公式を解くことで回答される質問が表示されます。

以下のケースは、カウントに使用される引数が関連するケースをグループ化するような順序になっていますが、これは表に示されている順序とは異なります。

このケースは、 Xのn個の要素のシーケンスを制限なしで数えることと同じです。関数f  : N → X は、 Nの要素のn 個のイメージによって決定され、各イメージはxの要素の中から独立して選択できます。これにより、合計x ⁿの可能性が得られます。

例：

${\displaystyle X=\{a,b,c\},N=\{1,2\}{\text{、すると }}}$

${\displaystyle \left\vert \{(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)\}\right\vert =3^{2}=9}$

この場合は、 Xのn個の 異なる要素のシーケンスを数えることと同等です。これは、Xのn順列、または繰り返しのないシーケンスとも呼ばれます。このシーケンスも、 Nの要素のn個のイメージによって形成されます。この場合は、 2 番目の要素の選択肢が 1 つ少なく、 3 番目の要素の選択肢が 2 つ少ないなど、無制限のシーケンスの場合と異なります。したがって、xの通常の累乗ではなく、値はxの階乗乗で与えられ、各因数は前の因数より 1 つ少なくなります。式は次のとおりです。

${\displaystyle x^{\underline {n}}=x(x-1)\cdots (x-n+1).}$

n > xの場合は因数 0 が得られることに注意してください。したがって、この場合はN → X への入射関数はまったく存在しません。これは単に鳩の巣原理を言い換えただけです。

例：

${\displaystyle X=\{a,b,c,d\},N=\{1,2\}{\text{, then }}}$

${\displaystyle \left\vert \{(a,b),(a,c),(a,d),(b,a),(b,c),(b,d),(c,a),(c,b),(c,d),(d,a),(d,b),(d,c)\}\right\vert =4^{\underline {2}}=4\times 3=12}$

この場合は、Xのn個の要素を持つサブセットを数えることと等価です。これは、 Xのn個の組み合わせとも呼ばれます。 Xのn個の異なる要素のシーケンスのうち、項の順序のみが異なるシーケンスは、 Nの順列によって識別されます。すべての場合において、これはちょうどn ! 個の異なるシーケンスをグループ化するため、このようなシーケンスの数をn ! で割ると、 Xのn個の組み合わせの数が得られます。この数は二項係数と呼ばれ、次のように表されます。 ${\displaystyle {\tbinom {x}{n}}}$

${\displaystyle {\binom {x}{n}}={\frac {x^{\underline {n}}}{n!}}={\frac {x(x-1)\cdots (x-n+2)(x-n+1)}{n(n-1)\cdots 2\cdot 1}}.}$

例：

${\displaystyle X=\{a,b,c,d\},N=\{1,2\}{\text{, then }}}$

${\displaystyle \left\vert \{\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}\}\right\vert ={\frac {4^{\underline {2}}}{2!}}={\frac {4\times 3}{2}}=6}$

このケースは、 Xからn個の要素を持つ多重集合( n多重組み合わせとも呼ばれる)を数えることと同等です。その理由は、Xの各要素に対して、 fによってNの要素がいくつマッピングされるかが決定されるのに対し、 Xの各要素に同じ「多重度」を与える 2 つの関数は、Nの順列によって常に別の関数に変換できるためです。N → Xのすべての関数を数える式は、 Nの順列によってグループ化される関数の数が関数ごとに異なるため、ここでは役に立ちません。むしろ、組み合わせで説明したように、 x個の要素を持つ集合からのn多重組み合わせの数は、x + n − 1個の要素を持つ集合からのn組み合わせの数と同じであると見なすことができます。これにより、問題は 12 倍の方法で別の問題に縮小され、結果として次のようになります。

${\displaystyle {\binom {x+n-1}{n}}={\frac {(x+n-1)(x+n-2)\cdots (x+1)x}{n(n-1)\cdots 2\cdot 1}}={\frac {x^{\overline {n}}}{n!}}.}$

例：

${\displaystyle X=\{a,b,c\},N=\{1,2\}{\text{, then }}}$

${\displaystyle \left\vert \{\{a,a\},\{a,b\},\{a,c\},\{b,b\},\{b,c\},\{c,c\}\}\right\vert ={\frac {3^{\overline {2}}}{2!}}={\frac {4\times 3}{2}}=6}$

この場合は、Xの各要素が少なくとも 1 回出現するn個の要素を持つ多重集合をXから数えることと同じです。これは、 xの要素の多重度を順にリストすることによって、nとx個の(非ゼロ) 項の合成を数えることにも相当します。関数と多重集合の対応は前の場合と同じであり、全射性要件はすべての多重度が少なくとも 1 であることを意味します。すべての多重度を 1 減らすと、これは前の場合に短縮されます。変更によりnの値がxだけ減少するため、結果は次のようになります。

${\displaystyle {\binom {n-1}{n-x}}.}$

n < xのとき、N → X への全射関数はまったく存在しないことに注意する(一種の「空の鳩の巣」原理)。これは、下側のインデックスが負の場合、二項係数は常に 0 であるという慣例によって、式で考慮されている。同じ値は、次の式でも与えられる。

${\displaystyle {\binom {n-1}{x-1}},}$

ただし、極端な場合n = x = 0では、前者の式では正しく となり、後者の式では誤って となります。 ${\displaystyle {\tbinom {-1}{0}}=1}$${\displaystyle {\tbinom {-1}{-1}}=0}$

結果の形式から、n − 1 個の要素から選択されたn − x個の要素のサブセットに、一連の全射関数N → Xを直接関連付ける方法を探す必要があることがわかります。これは、次のように実行できます。まず、NとX の集合の全順序を選択し、 Nの適切な順列を適用することで、すべての全射関数N → Xを一意の弱増加(もちろん依然として全射) 関数に変換できることに注目してください。Nの要素をn − 1 個の弧で順番に接続して線形グラフを作成し、次にn − x個の弧のサブセットを任意に選択して残りを削除すると、x 個の接続コンポーネントを持つグラフが得られ、これをXの連続する要素に送信することで、弱増加全射関数N → Xが得られます。また、接続コンポーネントのサイズによって、 nがx個の部分に合成されます。この議論は基本的にstars and barsで示されているものですが、 x − 1 個の「分離」の補完的な選択が行われます。

例：

${\displaystyle X=\{a,b\},N=\{1,2,3\}{\text{, then }}}$

${\displaystyle \left\vert \{\{a,a,b\},\{a,b,b\}\}\right\vert ={\binom {3-1}{3-2}}={\binom {2}{1}}={\frac {2!}{1!\times (2-1)!}}=2}$

この場合、Xからのn 個の異なる要素のシーケンスを考えますが、各要素にXの順列を適用することによって、互いから得られたシーケンスを識別します。 2 つの異なるシーケンスを常に識別できることは簡単にわかります。順列は、最初のシーケンスの項i を2 番目のシーケンスの項iにマッピングする必要があり、どちらのシーケンスにも値が 2 回出現しないため、これらの要件は互いに矛盾しません。残っているのは、最初のシーケンスに出現しない要素を、任意の方法で 2 番目のシーケンスに出現しない要素に全単射にマッピングすることです。結果がnとxにまったく依存する唯一の事実は、鳩の巣原理によ​​り、そのようなシーケンスが存在するには、まずn ≤ x が必要であるということです。したがって、この数は、アイバーソン括弧を使用してと表されます。 ${\displaystyle [n\leq x]}$

このケースは前のケースに簡略化されます。Xのn個の異なる要素のすべてのシーケンスは、各項にXの順列を適用することで相互に変換できるため、項の並べ替えを許可しても新しい識別は行われず、数は のままです。 ${\displaystyle [n\leq x]}$

このケースは、Nをx個の（空でない）部分集合に分割することを数えること、またはN上でちょうどx個のクラスを持つ同値関係を数えることと同等です。実際、任意の全射関数f  : N → Xについて、 f の下で同じ像を持つ関係はそのような同値関係であり、その後Xの順列を適用しても変化しません。逆に、 Xの要素を何らかの方法でx個の同値クラスに割り当てることで、そのような同値関係を全射関数に変えることができます。そのような分割または同値関係の数は、定義により第 2 種スターリング数S ( n , x ) であり、 とも表記されます。その値は再帰関係または生成関数を使用して記述できますが、二項係数とは異なり、これらの数には合計を含まない閉じた式はありません。 ${\displaystyle \textstyle \{{n \atop x}\}}$

各全射関数f  : N → Xについて、Xの順列によるその軌道にはx ! 個の要素があります。これは、 Xの 2 つの異なる順列との合成 (左側) がN上の同じ関数を与えることはないからです(順列はXの何らかの要素で異なる必要があり、これは常にi ∈ Nに対してと書くことができ、その場合合成はiで異なります)。したがって、この場合の数は 前の場合の数のx ! 倍、つまり${\displaystyle f(i)}$${\displaystyle \textstyle x!\{{n \atop x}\}.}$

例：

${\displaystyle X=\{a,b\},N=\{1,2,3\}{\text{, then }}}$

${\displaystyle \left\vert \{(a,a,b),(a,b,a),(a,b,b),(b,a,a),(b,a,b),(b,b,a)\}\right\vert =2!\left\{{3 \atop 2}\right\}=2\times 3=6}$

このケースは、全射関数の場合の対応するケースに似ていますが、xのいくつかの要素は、どの同値類にもまったく対応しない可能性があります (関数はXの順列まで考慮するため、どの要素が関係するかは問題ではなく、要素がいくつあるかだけです)。結果として、N上の同値関係を最大x個のクラスで数え、結果は前述のケースからxまでの値の合計によって得られ、 となります 。 x ≥ nの場合、 xのサイズはまったく制限がなく、n個の要素のセット (つまり、そのようなセットのすべての分割) 上のすべての同値関係を数えます。したがって、ベル数B _nの式が得られます。 ${\displaystyle \textstyle \sum _{k=0}^{x}\{{n \atop k}\}}$${\displaystyle \textstyle \sum _{k=0}^{n}\{{n \atop k}\}}$

このケースは、数nをx個の非ゼロ部分に分割することを数えることと同等です。X のみの順列まで全射関数を数える場合 ( ) と比較すると、関数がNを分割する同値類のサイズ (各サイズの重複を含む) のみが保持されます。これは、2 つの同値関係がNの順列によって相互に変換できるのは、それらの類のサイズが一致する場合のみであるためです。これがまさに、nの分割の概念とNの分割の概念を区別するものであり、結果として、定義により、nをx 個の非ゼロ部分 に分割する数p _x ( n ) が得られます。${\displaystyle \textstyle \{{n \atop x}\}}$

この場合は、数nを≤ x個の部分に分割することを数えることに相当します。関連付けは前の場合と同じですが、今回は分割の一部が 0 に等しい場合があります (具体的には、関数の像にないXの要素に対応します)。最大でx個の非ゼロ部分へのnの各分割は、必要な数のゼロを追加することでそのような分割に拡張でき、これによりすべての可能性が 1 回だけ説明されるため、結果は で与えられます。x 個の部分のそれぞれに 1 を加えると、 n + xをx個の非ゼロ部分に分割できます。この対応は全単射であるため、与えられた式は と書き込むことで簡略化できます。 ${\displaystyle \textstyle \sum _{k=0}^{x}p_{k}(n)}$${\displaystyle p_{x}(n+x)}$

上記の式は、すべての有限集合NとXの適切な値を与えます。場合によっては、ほぼ同等であるものの、 NまたはXが空の場合など、一部の極端な場合には正しい結果が得られない代替式があります。このような場合には、次の考慮事項が適用されます。

• すべての集合Xに対して、空集合からXへの関数が 1 つだけ存在します(この関数の値を指定することはできません)。この関数は常に単射ですが、Xが (また) 空でない限り、単射になることはありません。
• 空でない集合Nごとに、 Nから空集合への関数は存在しません(指定する必要がある関数の値が少なくとも 1 つありますが、指定できません)。
• n > xの場合、N → X への単射関数は存在せず、n < xの場合、 N → X への全射関数は存在しません。
• 式で使用される表現は特定の値を持ちます

${\displaystyle 0^{0}=0^{\underline {0}}=0!={\binom {0}{0}}={\binom {-1}{0}}=\left\{{0 \atop 0}\right\}=p_{0}(0)=1}$

（最初の3つは空積の例であり、その値は二項係数を上限の任意の値に拡張することで得られる）。一方、 ${\displaystyle {\tbinom {-1}{0}}={\tfrac {(-1)^{\underline {0}}}{0!}}=1}$

${\displaystyle \left\{{n \atop x}\right\}=p_{x}(n)=0\quad {\hbox{whenever either }}n>0=x{\hbox{ or }}0\leq n<x.}$

特に、 Xからn個の要素を取った多重集合を数える場合、与えられた式はほとんどの場合 と同等ですが、後者の式はn = x = 0の場合に 0 を返します(負の下側インデックスを持つ二項係数は常に 0 であるという通常の慣例により)。同様に、 x 個の非ゼロ部分を持つnの合成を数える場合、与えられた式はstars and bars の引数で与えられた式とほぼ同等ですが、後者はn = 0およびxのすべての値 に対して誤った値を返します。結果が合計を伴う場合、つまり N を最大でx 個の空でない部分集合に分割するか、 n を最大でx 個の非ゼロ部分に分割するかを数える場合、合計インデックスは 0 から始まるとみなされます。対応する項はn > 0の場合は常に 0 ですが、 n = 0の場合は唯一の非ゼロ項であり、合計が 1 から始まるとすると、これらのケースでは結果が間違ってしまいます。 ${\displaystyle {\tbinom {n+x-1}{n}}}$${\displaystyle {\tbinom {n+x-1}{x-1}}}$${\displaystyle {\tbinom {n-1}{n-x}}}$${\displaystyle {\tbinom {n-1}{x-1}}}$

他の順列群がNとXに作用できるようにすることで、さらに一般化できます。G がNの順列群で、H がXの順列群である場合、関数の同値類を数えます。 2 つの関数fとF は、 が存在する場合のみ、同等であるとみなされます。 この拡張により、巡回順列や二面体順列、および数と集合の巡回分割や二面体分割 などの概念が生まれます。${\displaystyle f\colon N\rightarrow X}$${\displaystyle g\in G,h\in H}$${\displaystyle F=h\circ f\circ g}$

20 倍法と呼ばれる別の一般化は、ケネス P. ボガートが著書「ガイド付き発見による組合せ論」で展開しました。オブジェクトをボックスに分配する問題では、オブジェクトとボックスの両方が同一である場合もあれば、異なる場合もあります。ボガートは 20 のケースを特定しています。 ^[3]ロバート A. プロクターは 30 倍法を構築しました。^[4]

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