組み合わせの数と二項係数の関係

の組み合わせ $$$n$ によって $$$k$ からのサンプリングと呼ばれる $$$k$ を含むセットで取得された要素 $$$n$ 要素。 同じアイテムを複数回選択することはできません。 要素の選択に関する決定が提示される順序は考慮されません。 可能なすべての組み合わせの数 $$$n$ によって $$$k$ 等しい $$$C_n ^ k$ -ニュートンの二項式の係数。 すべての小学生に知られている事実：あなたはウィキペディアまたは教科書でそれについて読むことができ、そこでは組み合わせと組み合わせ論がまったく言及されています。



ただし、これら2つの数値が等しい理由はどこにも説明されていません。 おそらく誰もがこの事実を自明であり、追加の説明は必要ないと考えています。



実際、考えてみれば、接続は非常に簡単です。 しかし、ある時点まで、多項式の係数と組み合わせ論との間の関係は、私にとって魔法の領域からのものでした。 これが今あなたのためにそうなら、キャットへようこそ、私は明白を説明します。



具体的な例から始めましょう。 量を取る $$$（a + b）$ ある程度、たとえば4番目に上げます。

$$

$$（a + b）^ 4 =（a + b）（a + b）（a + b）（a + b）。$$

右側の括弧を開きましょう。同様の用語を与えず、それらを使用して学位を書きます。また、乗算の可換性について少しの間忘れます。 用語の要素の順序は変更しません。

$$

$$（a + b）^ 4 =$$

$$

$$（a + b）（a + b）（a + b）（a + b）=$$

$$

$$（（a + b）（a + b））（（a + b）（a + b））=$$

$$

$$（aa + ab + ba + bb）（aa + ab + ba + bb）=$$

$$

$$aa（aa + ab + ba + bb）+ ab（aa + ab + ba + bb）+$$

$$

$$ba（aa + ab + ba + bb）+ bb（aa + ab + ba + bb）=$$

$$

$$aaaa + aaab + aaba + aabb + abaa + abab + abba + abbb +$$

$$

$$baaa + baab + baba + babb + bbaa + bbab + bbba + bbbb$$

結果の多項式の項を文字列と考えてみましょう。 4文字の長さの16行を取得しました。 16が簡単な理由を理解する。 2つの用語を含むブラケットを掛けるたびに、最終結果の要素数が2倍になります。 合計で、4つのブラケットに2つの用語を掛けました。 最終的に得た $$$2 \ times 2 \ times 2 \ times 2 = 2 ^ 4 = 16$ 。



要素が等しいと仮定します $$$a$ 、それは「選択」されていませんが、 $$$b$ 、次に「選択」。 この場合、行 $$$aaaa$ 4つの要素のいずれも選択されなかった場合に対応し、行 $$$bbbb$ -すべての要素が選択されている場合。



「4つの要素のうち2つをいくつの方法で選択できるか」という質問に答えたいとします。 合意が得られれば、必要なのは、正確に2文字の行の数を数えることだけです $$$b$ ： $$$aabb、abab、abba、baab、baba、bbaa$ 。 それらのちょうど6つがあります。



ここで、乗算の可換性と表記「度」を思い出しましょう。 これらの行はすべて次のように記述できます。 $$$a ^ 2b ^ 2$ 、元の金額で次のようになります：

$$

$$aabb + abab + abba + baab + baba + bbaa =$$

$$

$$a ^ 2b ^ 2 + a ^ 2b ^ 2 + a ^ 2b ^ 2 + a ^ 2b ^ 2 + a ^ 2b ^ 2 + a ^ 2b ^ 2 =$$

$$

$$6a ^ 2b ^ 2.$$

係数6は、2つの要素を選択する方法の数に関する質問への答えです。 そのような用語を提示するとき、その中の因子の数を計算するので、それは驚くことではありません $$$a$ そして $$$b$ 等しく入ります。 つまり、同じ数の要素が「選択」されている行の数をカウントします。



最初の合計に戻り、すべての条件を与えます。 わかりやすくするために、係数1を明示的に書き留め、次の事実を使用します。 $$$a ^ 0 = b ^ 0 = 1$ 。

$$

$$（a + b）^ 4 = 1a ^ 4b ^ 0 + 4a ^ 3b ^ 1 + 6a ^ 2b ^ 2 + 4a ^ 1b ^ 3 + 1a ^ 0b ^ 4。$$

そのような記録では、選択する方法の数を見つけるために $$$k$ からのアイテム $$$4$ 項の前の係数を見てください $$$b$ に含まれる $$$k$ 学位。



ところで、注意してください $$$1 + 4 + 6 + 4 + 1 = 16 = 2 ^ 4$ 。 これは二項係数の別の特性であり、次の多項式で開始したことを思い出すと明らかになります。 $$$2 ^ 4$ 用語。



一般的な場合

$$

$$（a + b）^ n = C_n ^ 0a ^ nb ^ 0 + C_n ^ 1a ^ {n-1} b ^ 1 + ... + C_n ^ na ^ 0b ^ n$$

$$

$$\ sum_ {k = 0} ^ {n} {C_n ^ k} = 2 ^ n。$$

表記は非常に簡単です。 $$$C$ 下のスタンド $$$n$ -ブラケットの程度、上記 $$$k$ -用語の程度 $$$b$ 。



または、現在わかっているように、 $$$n$ これは、選択を行うセット内の要素の数です。 $$$k$ -選択した要素の数。



通常、二項係数の定義は積で与えられないことを付け加えます $$$a$ そして $$$b$ 、製品を通して $$$（1 + x）^ n$ 結果の多項式には、 $$$x$ （いつから $$$a = 1$ ある程度 $$$a$ 1に等しい）。 これの本質は変わりませんが、結果の式の組み合わせの性質に気付くのはより困難になります。