二項係数：定義、実装、使用法

序章

統計では、二項係数は主に分布とともに使用されます。 しかし、計算アルゴリズムに適用すると、さらに多くのことがあります。 これらは、動的計画法だけでなく、統計的機械学習の分野でも広く使用されています。 二項係数に関する最も基本的な考え方は、二項分布から導き出されます。 係数は二項定理で使用されるため、名前が付けられています。

主に、二項係数には2つの定義があります。 それらは次のとおりです。

1.組み合わせを見つけるための二項係数

二項係数は、提供されたオブジェクトのプールから特定の数のオブジェクトを選択する方法の数を見つけるために使用されます。 統計的に、二項係数は、合計x個のオブジェクトからy個のオブジェクトを選択できる方法の数を見つけるのに役立ちます。 xからのy要素サブセットの数。

式は次のように導き出されます。

x個のオブジェクトからy個の要素のサブセットを選択する場合、二項係数または可能な組み合わせはxCy = x！です。 / y！ *（xy）！

このメソッドは、オブジェクトの大きなプールから可能な組み合わせの数を把握する必要がある場合に、非常に便利です。 しかし、これはどこに当てはまりますか？

例

15人の生徒がいるクラスがあると想像してください。 コンテストに7人の学生のチームを選択する必要がある場合は、可能な組み合わせを把握する必要があります。 二項係数の式を使用すると、答えを簡単に計算できます。

合計の組み合わせ=15！ / 7！ *（15-7）！ = 15！ / 7！ * 8！

他の多くのケースははるかに複雑で、二項係数が使用されます。 たとえば、選挙のための政党、より具体的にはシンジケートを選択します。 通過する法案があり、あなたが与党の多数派であると想像してみてください。 どの投票があり、法案に投票するために何人のメンバーが必要になるかを決める必要があります。 野党だけでなく、与党の党員である必要がある。 組み合わせ論を適用して、投票を依頼するメンバーを見つけることができます。

について読む：初心者のための13の興味深いデータ構造プロジェクトのアイデアとトピック

2.分布の二項係数

この定義は、より正式で統計的です。 これは、多項式展開の係数を見つけることを意味します。 簡単に言えば、二項係数C（a、b）は、（x + 1）^aの分散形式でのx^bの係数として定義できます。

これを例で理解しましょう。

例

たとえば、（x + 1）^2の多項式展開が必要です。 これを定義と比較すると、a=2およびb=0,1,2が得られます。

手動計算により、（x + 1）^ 2 = x ^ 2 + 2x + 1の展開がわかります。しかし、これらの係数はどのように計算されますか？

次の式を適用してみましょう。

x ^ 0 = C（2,0）の係数

x ^1の係数=C（2,1）

x ^2の係数=C（2,2）

したがって、展開は次のように記述できます。C（2,0）x ^ 0 + C（2,1）x ^ 1 + C（2,2）x ^ 2

式は同じままです。 C（a、b）= a！ / b！ *（ab）！

ここに同じ式を適用すると、C（2,0）= 2！ / 0！ *（2-0）！ = 1

C（2,1）= 2！ / 1！ *（2-1）！ = 2

C（2,2）= 2！ / 2！ *（2-2）！ = 1

ここで、これらの値を展開に代入すると、x ^ 2 + 2x+1が得られます。

それは私たちが要求した正確な答えです。 これは小さな拡張だったので、単純な乗算方法の方が優れていると感じるかもしれません。 しかし、（x + 1）^ 17の拡張形式を計算する必要がある場合はどうなりますか？

何度も掛ける方法はなく、面倒な仕事になります。 しかし、二項係数の概念を使用すると、作業は簡単になります。

読む： Python再帰関数の概念：初心者のためのPythonチュートリアル

Pythonの実装

二項係数を求める式を実装する前に、いくつかの点に注意する必要があります。 関数を実装するために必要な2つの部分があります。 1つは下部構造で、もう1つは下部構造を繰り返す関数です。

C（a、b）の値を再帰的に見つけるために、次の下部構造を使用できます。

C（a、0）およびC（a、a）= 1

C（a、b）= C（a-1、b）+ C（a-1、b-1）

これらの2つの式を使用して、再帰関数を実装できます。 拡張度が高くなると、下部構造の多くが繰り返されることに注意してください。 計算が不必要に繰り返されると、計算時間が長くなる可能性があります。 したがって、効果的な実装のためには、以前のすべての計算で辞書を維持することが重要です。

このタイプの実装には、O（a * b）の時間計算量があります。 スペースの複雑さは実装によって異なりますが、O（b）に制限できます。

Pythonを使用していて、自分で関数を実装したくない場合は、PythonのライブラリSciPyを使用できます。 SciPyの特別なモジュールには関数binom（）があります。 使用方法は次のとおりです。

scipy.special.binom（a、b）と入力するだけで、同じ値が提供されます。 たとえば、scipy.special.binom（4,3）; 出力を提供します– 4.0

使用法

二項係数の主な使用法については、すでに上で説明しました。 二項係数は、分析と二項分布のベースに使用されます。 あまり知られていない使用法は、二項係数がパスカルの三角形のエントリを表すことです。 これらのタイプの統計的理由により、二項係数を理解する必要があります。

また、チェックアウト：実際の例を使用したPythonでの二項分布

結論

したがって、これはすべて、統計および実装の観点からの二項係数に関するものでした。 組み合わせと展開係数の計算のための二項係数の2つの定義について説明しました。 ライブラリの実装だけでなく、実装戦略についても議論されました。

二項係数には、特に分布で見られる場合、さらに多くの統計的アプリケーションがあります。 したがって、コア機械学習や分析アルゴリズムなどの高度な統計ベースの概念に進む前に、二項係数について学習することが重要です。

機械学習について詳しく知りたい場合は、IIIT-BとupGradの機械学習とAIのPGディプロマをご覧ください。これは、働く専門家向けに設計されており、450時間以上の厳格なトレーニング、30以上のケーススタディと課題、IIIT-を提供します。 B卒業生のステータス、5つ以上の実践的なキャップストーンプロジェクト、トップ企業との仕事の支援。