組合せの公式

組合せの公式

\[_{n}C_{0}=_{n}C_{n}=1\]\[_{n}C_{1}=n\]\[_{n}C_{r}=_{n}C_{n-r}\]\[_{n}C_{r}=_{n-1}C_{r}+_{n-1}C_{r-1}\]\[r \cdot _{n}C_{r}=n \cdot _{n-1}C_{r-1}\]

3番目の公式は,異なる $n$ 個の中から $r$ 個選ぶ選び方 $_{n}C_{r}$ 通りのそれぞれは,$n$ 個のものから選ばない$ (n−r) $個のものを選ぶ選び方 $_{n}C_{n−r}$ 通りと1対1に対応するということから導かれます.

4番目の特定のものについての場合分けに関する公式に関しては,異なる $n$ 個のものの中から $r$ 個選ぶ方法が,ある特定の 1 個を含まないで $r$ 個選ぶ選び方の総数が $_{n-1}C_{r}$ 通りであること,ある特定の 1 個を含む $r$ 個選ぶ選び方の総数が $_{n-1}C_{r-1}$ 通りであること,そして,この 2 つの事象が同時に起こることはないので,\[_{n}C_{r}=_{n-1}C_{r}+_{n-1}C_{r-1}\]が成り立ちます.

最後の公式は,リーダーの公式とか大統領と委員の公式と呼ばれます.

つまり,$n$ 人の中から委員 $r$ 人選び,その $r$ 人の委員の中からリーダーを 1 人決める決め方は,$_{n}C_{r} \times r$ 通り考えられます.

また,$n$ 人の中から先にリーダーを決めて,残りから委員 $r-1$ 人を選ぶ方法もありますが,両者は結局同じことなので(本当に同じかという問題はあります),\[r \cdot _{n}C_{r}=n \cdot _{n-1}C_{r-1}\]が成立します.

Mathematics is the language with which God has written the universe.





















巡回群 順列の数と組合せの数 環と微分 環とモノイド ヤコビアン 底の変換公式