二項係数と基本的な数え上げ

二項係数は、有限集合から固定サイズのサブセットを選択する方法の数を数え上げ、組み合わせ的数え上げの基本的な構成要素として機能します。

Definition

二項係数 C(n,k) は、n個の要素を持つ集合からk個の要素を持つサブセットを選ぶ方法の数であり、n!/(k!(n-k)!) に等しい。基本的な数え上げとは、有限の構成に対して加法と乗法の法則を体系的に適用することです。

Scope

このトピックでは、基本的な数え上げ原理である和の法則と積の法則、および二項係数 C(n,k) の中心的役割、その恒等式（パスカルの法則、二項定理、ヴァンデルモンドの恒等式）、そしてパスカルの三角形におけるその出現について扱います。これは、すべての数え上げ組み合わせ論が構築される基礎的なツールキットを確立します。

Core questions

• n個の異なる対象からk個の対象を選ぶ方法は何通りありますか？
• 和の法則と積の法則は、数え上げ問題をどのように分解しますか？
• 二項係数を互いに、そして二項定理と関連付ける恒等式は何ですか？
• パスカルの三角形はこれらの係数をどのように再帰的に符号化していますか？

Key concepts

• 和の法則と積の法則
• 順列と組み合わせ
• 階乗
• パスカルの三角形
• ヴァンデルモンドの恒等式
• 多項係数

Key theories

二項定理

展開 (x+y)^n = Σ_{k} C(n,k) x^k y^(n-k) は、二項係数を二項式のべき乗における代数係数として表現し、数え上げと多項式代数を結びつけます。

パスカルの法則

漸化式 C(n,k) = C(n-1,k-1) + C(n-1,k) は、各二項係数をその上にある2つの係数から構築し、パスカルの三角形を生成し、選択されたサブセットが特定の要素を含むかどうかを反映します。

Clinical relevance

二項係数は、二項確率分布、組み合わせアルゴリズムの解析、および順序付けされていない選択の数を数える必要があるあらゆる状況の基礎となっており、確率論、統計学、コンピュータ科学において遍在しています。

History

二項係数の三角形配列は、パスカルが1654年にその構成に西洋で永続的な名前を与えた論文を発表する何世紀も前から、中国、ペルシャ、インドの数学に登場していました。

Key figures

• Blaise Pascal
• Isaac Newton

Seminal works

• stanley2011

Frequently asked questions

順列と組み合わせの違いは何ですか？

順列は順序が重要な配置の数を数えます。一方、二項係数によって数えられる組み合わせは、順序が関係ない選択の数を数えます。

C(n,0) が1に等しいのはなぜですか？

集合から何も選ばない方法は正確に1通り、すなわち空集合であるため、ゼロ要素サブセットの数は1です。