星と棒（組み合わせ論）

組合せ論において、星と棒（「棒と石」、「ボールと棒」、「^ドットと仕切り」と^{も呼ばれる}^{）は、特定の}組合せ定理を導くためのグラフィカルな補助手段である。これは、区別できない $n$ 個のボールを区別できる $k 個$ の箱に入れる方法が何通りあるかなど、多くの単純な計数問題を解くために使用できる。 ^[4]この特定の問題の解は二項係数によって与えられ、これはサイズ $n$ $+$ $k$ $- 1$ の集合から形成できるサイズ $k$ $- 1$ のサブセットの数である。 ${\tbinom {n+k-1}{k-1}}$

たとえば、ボールが 2 個とビンが 3 個ある場合、ボールを配置する方法の数はです。表には、2 つのボールを配置する 6 つの可能な方法、それらを表す星とバーの文字列 (星はボールを示し、バーはビンを互いに分離します)、および文字列に対応するサブセットが示されています。3 つのビンを分離するには 2 本のバーが必要で、ボールが 2 個あるため、各文字列には 2 本のバーと 2 本の星が含まれます。各サブセットは、対応する文字列の 4 つのシンボルのどれがバーであるかを示します。 ${\tbinom {2+3-1}{3-1}}={\tbinom {4}{2}}=6$

定理の記述

星と棒の法則は、方程式の解の数に関する基本的な組合せ論の次の 2 つの定理を証明するために特に導入されることが多いです。

定理1

任意の正の整数 $n$ と $k の$ ペアについて、その合計が $nとなるよう$ な正の整数の $k$ 組の数は、 $n$ $- 1$ 個の要素を持つ集合の $($ $k$ $- 1)$ 要素の部分集合の数に等しい。

例えば、 $n = 10$ 、 $k = 4$ の場合、定理は $x 1 + x 2 + x 3 + x 4 = 10$ （ $x 1 、 x 2 、 x 3 、 x 4 > 0$ ）の解の数を二項係数として与えます。

{\binom {n-1}{k-1}}={\binom {10-1}{4-1}}={\binom {9}{3}}=84,

ここで、 $n$ $- 1 個$ の要素を一度に $k$ $- 1 個$ ずつ取り出す組み合わせの数です。 ${\tbinom {n-1}{k-1}}$

これは整数の合成に対応します。

定理2

$任意の正の整数n$ と $k の$ ペアについて、合計が $nとなる$ 非負整数の $k$ 組の数は、サイズ $n$ $+ 1$ の集合からサイズ $k$ $- 1の$ 多重集合を取った数、またはサイズ $k$ の集合からサイズ $n$ の多重集合を取った数に等しく、次のように表される。

{\binom {n+k-1}{k-1}}.

例えば、 $n = 10$ 、 $k = 4$ の場合、定理は $x 1 + x 2 + x 3 + x 4 = 10$ （ $\geq 0$ ）の解の数を次のように与えます。

\left(\!\!{n+1 \choose k-1}\!\!\right)=\left(\!\!{k \choose n}\!\!\right)={\binom {n+k-1}{k-1}}={\binom {10+4-1}{4-1}}={\binom {13}{3}}=286,

ここで、多重集合係数は、サイズ $k$ のセットから要素が取得された、サイズ $n$ の多重集合の数です。 $\left(\!\!{\binom {k}{n}}\!\!\right)$

これは整数の弱い合成に対応します $。k を固定すると、$ $n = 0、1、2、3、\dots$ の数はパスカルの三角形の $(k - 1)$ 番目の対角線上の数になります。たとえば、 $k$ $= 3のとき、$ $n$ 番目の数は ( n + 1) 番目の三角数で、 $2$ $番目$ $の$ 対角線上にあるため、1、3、6、10、… となります。

星と棒による証明

定理1の証明

合計がnであるk組を列挙する問題は、次のような構成を数える問題と同等です。すべてのビンに少なくとも 1 つのオブジェクトが含まれるように、 n 個のオブジェクトをk 個のビンに配置するとします。ビンは区別されますが (1 からkまで番号が付けられているとします)、n 個のオブジェクトは区別されません (したがって、構成は各ビンに存在するオブジェクトの数によってのみ区別されます)。したがって、構成は正の整数の k組によって表されます。

n個のオブジェクトはn個の星の行として表され、隣接するビンはバーで区切られます。構成は、最初のビンと 2 番目のビンの境界、2 番目のビンと 3 番目のビンの境界などを示すことによって指定されます。したがって、星の間には $k - 1 本の$ バーを配置する必要があります。ビンを空にすることは許可されていないため、星のペアの間には最大で 1 本のバーがあります。星の間には $n - 1 個の$ ギャップがあり、したがってバーを配置できる位置は $n - 1個あります。構成は、これらのギャップの$ $k - 1 個を$ 選択してバーを含めることによって取得されます。したがって、構成が存在します。 ${\tbinom {n-1}{k-1}}$

例

$n = 7$ 、 $k = 3$ の場合、まず 7 つの星を一列に並べます。

★ ★ ★ ★ ★ ★ ★

図1: 星で表される7つのオブジェクト

次に、ビン間の境界を示します。

★ ★ ★ ★ | ★ | ★ ★

図2: この2つのバーは、4個、1個、2個のオブジェクトを含む3つのビンを生み出します。

一般的に、6 つのバー位置のうち 2 つを選択する必要があります。そのため、このような構成が存在します。 ${\tbinom {6}{2}}=15$

定理2の証明

この場合、正ではなく負でないという制限が緩和されたため、星の間に複数のバーを配置でき、最初の星の前と最後の星の後に 1 つ以上のバーを配置することもできます。オブジェクトとビンを含む構成に関しては、ビンを空にできるようになりました。

定理 1 の証明のように、サイズ $n$ $- 1$ のセットから取得されたバー位置の $($ $k$ $-$ 1)セットではなく、サイズ $n$ $+ 1$ のセットから取得されたバー位置の $($ $k$ $- 1$ ) 多重セットが得られます(バー位置は繰り返される可能性があり、端がバー位置として許可されるため)。多重セットの観点からの別の解釈は次のとおりです。サイズ $nの多重セットを選択する$ $k$ 個のビンラベルのセットがあり、この多重セット内のビンラベルの多重度は、そのビンに配置されているオブジェクトの数を示します。この等式は、さまざまなカウント問題の同値性として理解することもできます。つまり、合計が $n$ になる非負整数の $k組の数は、合計が$ $k$ $- 1$ になる非負整数の $($ $n$ $+ 1)$ 組の数に等しく、これは、構成を表す図でバーと星の役割を交換することによって従います。 $\left(\!\!{n+1 \choose k-1}\!\!\right)=\left(\!\!{k \choose n}\!\!\right)$

式を直接見るには、星とバーの配置は合計 $n$ $+$ $k$ $- 1 個$ のシンボルで構成され、そのうち $n個は星で、$ $k$ $- 1個はバーであることに注意してください。したがって、$ $n$ $+$ $k$ $- 1$ 個のスロットをレイアウトし、そのうち $k$ $- 1 個$ を選択してバーを含めることができます (または、同等に、n個のスロットを選択して星を含めることができます)。 ${\tbinom {n+k-1}{k-1}}$

例

$n = 7$ 、 $k = 5$ の場合、組 (4, 0, 1, 2, 0) は次の図で表すことができます。

★ ★ ★ ★ | | ★ | ★ ★ |

図3: これらの4つのバーは、4、0、1、2、0個のオブジェクトを含む5つのビンを生成します。

可能なバーの位置に 1、2、3、4、5、6、7、8 のラベルが付けられ、ラベル $i \leq 7$ $はi$ 番目の星の前のバーで、前の星の次のバーに対応し、ラベル8 は最後の星の次のバーに対応する場合、この構成は、定理 2 の証明で説明されているように、 $(k - 1)$ 多重集合 ${5、5、6、8}$ に対応します。ビンに 1、2、3、4、5 のラベルが付けられている場合は、これも定理 2 の証明で説明されているように、 $n$ 多重集合 ${1、1、1、1、3、4、4}に対応します。$

定理1と定理2の関係

定理 1 は定理 2 の観点から言い換えることができます。これは、各変数が正であるという要件は、各変数を -1 ずつシフトすることによって課すことができ、その後、各変数が非負であることのみを要求することができるためです。

例えば：

x_{1}+x_{2}+x_{3}+x_{4}=10

と $x_{1},x_{2},x_{3},x_{4}>0$

は以下と同等です:

x'_{1}+x'_{2}+x'_{3}+x'_{4}=6

と $x'_{1},x'_{2},x'_{3},x'_{4}\geq 0,$

ここで、それぞれ。 $x'_{i}=x_{i}-1$ $i\in \{1,2,3,4\}$

その他の例

例1

アンバー、ベン、カーティスの3人にそれぞれ少なくとも1ドルが渡されるように、7枚の区別のない1ドル硬貨を分配する方法の数を数えたい場合、分配は基本的に合計が7になる3つの正の整数の組と同等であることがわかります。（ここで、組の最初のエントリはアンバーに渡される硬貨の枚数です。）したがって、定理1が適用され、 $n = 7$ および $k = 3$ であり、硬貨を分配する方法が存在します。 ${\tbinom {7-1}{3-1}}=15$

例2

$n = 5$ 、 $k = 4$ で、 $k$ 個のビンラベルが $a 、 b 、 c 、 d$ の場合、 ★|★★★||★ は、4組 $(1、3、0、1)$ 、バーの位置の多重集合 ${2、5、5}$ 、またはビンラベルの多重集合 ${a 、 b 、 b 、 b 、 d}$ のいずれかを表すことができます。この問題の解決には、 $n = 5 個の$ 星と $k - 1 = 3 個$ のバーを使用した定理 2 を使用して構成を与える必要があります。 ${\tbinom {5+4-1}{4-1}}={\tbinom {8}{3}}=56$

例3

定理 2 の証明では、星よりもバーの数が多くなる可能性がありますが、定理 1 の証明ではそのようなことは起こりません。

たとえば、10 個のボールを 7 つのビンに入れると構成が得られ、7 個のボールを 10 個のビンに入れると構成が得られ、6 個のボールを 11 個のビンに入れると構成が得られます。 ${\tbinom {16}{6}}$ ${\tbinom {16}{9}}$ ${\tbinom {16}{10}}={\tbinom {16}{6}}$

例4

このグラフィカル手法は、ポール・エーレンフェストとハイケ・カメルリング・オンネスによって、星の代わりに記号ε （量子エネルギー要素）、バーの代わりに記号0を使用して、単一周波数の「共振器」システムの「複合体」の数を表すマックス・プランクの式の簡単な導出に使用されました。 ^[5]^[6]

プランクは、複合状態（ミクロ状態）とは、 $N個の$ 共振器上の $P個$ のエネルギー要素εの分布を意味した。^[7]^[8]複合状態の個数 $R$ は

R={\frac {(N+P-1)!}{P!(N-1)!}}.\

それぞれの可能な分布のグラフィカルな表現には、記号εの $P 個$ のコピーと記号0の $N$ $- 1 個$ のコピーが含まれます。Ehrenfest と Kamerlingh Onnes は、そのデモンストレーションで、 $N$ $= 4$ および $P$ $= 7$ (つまり、 $R$ $= 120 の$ 組み合わせ) を取りました。彼らは、この記号表現の例として、4 組 (4、2、0、1) を選択しました: εεεε0εε00ε。

生成関数との関係

定理1と定理2の列挙は、単純な有理式を含む生成関数を使用して見つけることもできます。2つのケースは非常に似ています。まず、定理2の場合を見てみましょう。単一のビンと任意の数のオブジェクトに対して1つの構成しかありません（オブジェクトが区別されていないため）。これは生成関数によって表されます。 $x_{i}\geq 0$

1+1x+1x^{2}+1x^{3}+\ldots =1+x+x^{2}+x^{3}+\ldots ={\frac {1}{1-x}}.

この級数は等比級数であり、最後の等式は $| x | < 1に対して解析的に成り立ちますが、この文脈では$ 形式的なべき級数の操作として理解する方が適切です。 $x$ の指数は、ビンにいくつのオブジェクトが配置されているかを示します。

それぞれの追加ビンは別の係数で表され、 $k$ 個のビンの生成関数は ${\frac {1}{1-x}}$

\underbrace {{\frac {1}{1-x}}{\frac {1}{1-x}}\dots {\frac {1}{1-x}}} _{k{\text{ 因子}}}={\frac {1}{(1-x)^{k}}}

、

ここで、乗算は形式的なべき級数のコーシー積です。

$n$ 個のオブジェクトを持つ構成の数を見つけるには、（生成関数の式の先頭にを付けて表される）の係数が必要です。つまり、 $x^{n}$ $[x^{n}]$

[x^{n}]{\frac {1}{(1-x)^{k}}}=[x^{n}](1-x)^{-k}

。

この係数は二項級数を使って求めることができ、定理2の結果、すなわちと一致します。 ${\tbinom {n+k-1}{k-1}}$

このコーシー積の表現は星印と棒で正当化される。積の展開における係数 $x^{n}$

\underbrace {(1+x+x^{2}+\ldots )(1+x+x^{2}+\ldots )\ldots (1+x+x^{2}+\ldots )} _{k{\text{ factors}}}

$は、 k$ 個の因数のそれぞれから $x$ の 1 乗を乗じて $xの$ $n$ 乗を得る方法の数です。したがって、星印は $x$ を表し、バーは1 つの因数から得られる x と次の因数から得られる $x$ を区別します。

の場合、つまり定理1の場合、どの構成も空のビンを持たないので、単一のビンの生成関数は $x_{i}>0$

x+x^{2}+x^{3}+\ldots ={\frac {x}{1-x}}

。

したがって、コーシー積はであり、の係数は二項級数を使用してであることがわかります。 ${\frac {x^{k}}{(1-x)^{k}}}$ $x^{n}$ ${\tbinom {n-1}{k-1}}$

参照

参考文献

^ バッターソン、J.中学校のための競技数学。問題解決の芸術。
^ フラジョレ、フィリップ、セジウィック、ロバート（2009年6月26日）。解析的組合せ論。ケンブリッジ大学出版局。ISBN 978-0-521-89806-5。
^ 「問題解決の芸術」artofproblemsolving.com . 2021年10月26日閲覧。
^ フェラー、ウィリアム（1968年）。確率論とその応用入門。第1巻（第3版）。ワイリー。38ページ。
^ エーレンフェスト、ポール; カメルリング・オネス、ハイケ (1914)。「プランクが放射理論の基礎として用いた結合理論からの式の簡略化された演繹」。KNAW議事録。17 : 870–873 。 2024年5月16日閲覧。
^ エーレンフェスト、ポール; カメルリング・オネス、ハイケ (1915)。「プランクが放射理論の基礎として用いた組み合わせ理論からの式の簡略化された演繹」。ロンドン、エディンバラ、ダブリン哲学雑誌および科学ジャーナル。シリーズ6。29 (170): 297–301。doi :10.1080/14786440208635308。2020年12月5日閲覧。
^ マックス、プランク (1901)。「正常範囲におけるエネルギーの利用者」。アンナレン・デア・フィジーク。309 (3): 553–563。Bibcode :1901AnP...309..553P。土井：10.1002/andp.19013090310。
^ Gearhart, C. (2002). 「プランク、量子、そして歴史家たち」(PDF) . Phys. Perspect . 4 (2): 170–215. Bibcode :2002PhP.....4..170G. doi :10.1007/s00016-002-8363-7 . 2024年5月16日閲覧。

さらに読む

ピットマン、ジム（1993）。確率。ベルリン：シュプリンガー・フェアラーク。ISBN 0-387-97974-3。
Weisstein, Eric W. 「Multichoose」。Mathworld -- Wolfram Web リソース。2012年11 月 18 日閲覧。

[1] バッターソン、J.中学校のための競技数学。問題解決の芸術。

[2] フラジョレ、フィリップ、セジウィック、ロバート（2009年6月26日）。解析的組合せ論。ケンブリッジ大学出版局。ISBN 978-0-521-89806-5。

[:0-3] 「問題解決の芸術」artofproblemsolving.com . 2021年10月26日閲覧。

[4] フェラー、ウィリアム（1968年）。確率論とその応用入門。第1巻（第3版）。ワイリー。38ページ。

[5] エーレンフェスト、ポール; カメルリング・オネス、ハイケ (1914)。「プランクが放射理論の基礎として用いた結合理論からの式の簡略化された演繹」。KNAW議事録。17 : 870–873 。 2024年5月16日閲覧。

[6] エーレンフェスト、ポール; カメルリング・オネス、ハイケ (1915)。「プランクが放射理論の基礎として用いた組み合わせ理論からの式の簡略化された演繹」。ロンドン、エディンバラ、ダブリン哲学雑誌および科学ジャーナル。シリーズ6。29 (170): 297–301。doi :10.1080/14786440208635308。2020年12月5日閲覧。

[7] マックス、プランク (1901)。「正常範囲におけるエネルギーの利用者」。アンナレン・デア・フィジーク。309 (3): 553–563。Bibcode :1901AnP...309..553P。土井：10.1002/andp.19013090310。

[8] Gearhart, C. (2002). 「プランク、量子、そして歴史家たち」(PDF) . Phys. Perspect . 4 (2): 170–215. Bibcode :2002PhP.....4..170G. doi :10.1007/s00016-002-8363-7 . 2024年5月16日閲覧。