順列組み合わせ二項定理などの数え上げの基本についてわかりやすくまとめてみた

|| そのまま個数を数えるやり方とか

順列とか組み合わせとかの話

数え上げ Counting

|| 自然数に並ぶくらい基礎的な数学の根幹

数学と言えばだいたい何かを数えています。

$\begin{array}{llllll} \displaystyle n!&:=&n(n-1)(n-2)(n-3)\cdots 3 \times 2\times 1 \end{array}$

$\begin{array}{llllll} \displaystyle {}_n\mathrm{P}_r&:=&\displaystyle\frac{n!}{(n-r)!} \\ \\ {}_n\mathrm{C}_r&:=&\displaystyle \frac{n!}{(n-r)!r!} \\ \\ \\ {}_n\mathrm{H}_r&:=&\displaystyle\frac{(n-1+r)!}{(n-1)!r!} \end{array}$

実用レベルではだいたいこういうのが。

順列 Permutation

|| 順番に並んでる列

「並び」が何通りあるかを『数える方法』

$\begin{array}{llllll} \displaystyle {}_n\mathrm{π}_r&:=&n^r \end{array}$

$\begin{array}{cccllllll} \mathrm{P}(n,r)&:=&\displaystyle\frac{n!}{(n-r)!} \\ \\ \mathrm{P}_{n,r}&:=&\displaystyle\frac{n!}{(n-r)!} \\ \\ \displaystyle {}_n\mathrm{P}_r&:=&\displaystyle\frac{n!}{(n-r)!} \end{array}$

上が「重複順列」で

下が「順列」と呼ばれています。

繰り返しを許す順列

「 $A,B$ 」を「 $2$ つ並べる」時の

『並び方』の「総数」は

$\begin{array}{llllll} \displaystyle AA & AB & BA & BB \end{array}$

以上の $4$ 通り

これはすぐ分かると思います。

で、これどうやって求めたかって話なんですが

$\begin{array}{llllll} \displaystyle A \begin{cases} A \\ B \end{cases} \\ \\ \displaystyle B\begin{cases} A \\ B \end{cases} \end{array}$

だいたいの人はこうやってると思います。

$\begin{array}{llllll} \displaystyle A \begin{cases} A\begin{cases} A \\ B \end{cases} \\ B\begin{cases} A \\ B \end{cases} \end{cases} \\ \\ \displaystyle B\begin{cases} A\begin{cases} A \\ B \end{cases} \\ B\begin{cases} A \\ B \end{cases} \end{cases} \end{array}$

$\begin{array}{llllll} \displaystyle A \begin{cases} A \\ B \\ C \end{cases} \\ \\ \displaystyle B\begin{cases} A \\ B \\ C \end{cases} \\ \\ \displaystyle C \begin{cases} A \\ B \\ C \end{cases} \end{array}$

で、このやり方は数が増えても通用しますから

$\displaystyle \overbrace {n\,個 \begin{cases} n\,個(1) \begin{cases}n\,個(1)\begin{cases}...\end{cases}\\n\,個(2)\begin{cases}...\end{cases}\\n\,個(3)\begin{cases}...\end{cases}\\...\end{cases} \\ n\,個(2) \begin{cases}n\,個(1)\begin{cases}...\end{cases}\\n\,個(2)\begin{cases}...\end{cases}\\n\,個(3)\begin{cases}...\end{cases}\\...\end{cases} \\ n\,個(3) \begin{cases}n\,個(1)\begin{cases}...\end{cases}\\n\,個(2)\begin{cases}...\end{cases}\\n\,個(3)\begin{cases}...\end{cases}\\...\end{cases} \\ ... \end{cases} }^{r}$

この「並び方の総数」は

$\begin{array}{llllll} \displaystyle \underbrace{n\times n\times \cdots \times n}_{r}&=&n^r \end{array}$

「違うとしたものが $n$ 個」あって

「 $r$ 個並べる」なので、こうなる

これは直感的にすぐ分かると思います。

繰り返しを許さない順列

『選んだら減る』並べ方については

これは ↑ みたいにやると ↓ みたいにできます。

$\begin{array}{llllll} \displaystyle A \begin{cases} B \\ C \end{cases} \\ \\ \displaystyle B\begin{cases} A \\ C \end{cases} \\ \\ \displaystyle C\begin{cases} A \\ B \end{cases} \end{array}$

$\displaystyle \overbrace {n\,個 \begin{cases} n-1\,個(1\,以外) \begin{cases}n-2\,個(1,2\,以外)\begin{cases}...\end{cases}\\n-2\,個(1,3\,以外)\begin{cases}...\end{cases}\\n-2\,個(1,4\,以外)\begin{cases}...\end{cases}\\...\end{cases} \\ n-1\,個(2\,以外) \begin{cases}n-2\,個(2,1\,以外)\begin{cases}...\end{cases}\\n-2\,個(2,3\,以外)\begin{cases}...\end{cases}\\n-2\,個(2,4\,以外)\begin{cases}...\end{cases}\\...\end{cases} \\ n-1\,個(3\,以外) \begin{cases}n-2\,個(3,1\,以外)\begin{cases}...\end{cases}\\n-2\,個(3,2\,以外)\begin{cases}...\end{cases}\\n-2\,個(3,4\,以外)\begin{cases}...\end{cases}\\...\end{cases} \\ ... \end{cases} }^{r}$

この表現には『階乗 $n!$ 』っていう

$\begin{array}{llllll} \displaystyle n!&:=&n(n-1)(n-2)(n-3)\cdots 3 \times 2 \times 1 \end{array}$

こういうやつが必要で

「並び方の総数」は

だいたい ↓ のように表現されます。

$\displaystyle \overbrace{n(n-1)(n-2)\cdots(n-r+1)}^{r}$

$\begin{array}{llllll} \displaystyle &&\displaystyle \overbrace{n(n-1)\cdots(n-r+1)}^{r} \\ \\ \\ &&\displaystyle n(n-1)\cdots(n-r+1) \times 1 \\ \\ &=&\displaystyle n(n-1)\cdots(n-r+1)\frac{(n-r)!}{(n-r)!} \\ \\ &=&\displaystyle \frac{n!}{(n-r)!}\end{array}$

念のため確認しておくと

「全て並べる」場合はもちろん ↓ になります。

$\begin{array}{llllll} \displaystyle && \overbrace{n(n-1)\cdots(n-r+1)}^{n} \\ \\ &=&n(n-1)\cdots(n-n+1) \\ \\ \\ &=&n(n-1)\cdots 2\times 1 \\ \\ &=&n! \end{array}$

これについては

計算しなくても直感的にすぐ分かると思います。

最後、補足しておくと

慣例ですがこれはだいたい ↓ みたいに書かれます。

$\begin{array}{llllll} \displaystyle \displaystyle {}_n\mathrm{P}_r&:=&\displaystyle\frac{n!}{(n-r)!} \end{array}$

他の書かれ方はあんま見ないですね。

同じ要素を区別しない場合の順列

「 $AAB$ 」みたいな時の

「 $A$ と $A$ 」を『区別しない』並べ方の総数は

$\begin{array}{llllll} \displaystyle \frac{n!}{k!} \end{array}$

『全て並べる』とした場合

「 $n$ 個の中で１つの要素が $k$ 個同じ」なら

まあこうなるんですけど

$\begin{array}{llllll} \displaystyle\textcolor{pink}{ A \begin{cases} A\begin{cases} B \end{cases} \\ B \begin{cases} A \end{cases}\end{cases}} \\ \\ \displaystyle \textcolor{pink}{A\begin{cases} A\begin{cases} B \end{cases} \\ B\begin{cases} A \end{cases} \end{cases}} \\ \\ \displaystyle B\begin{cases} \textcolor{skyblue}{A\begin{cases} A \end{cases}} \\ \textcolor{skyblue}{A\begin{cases} A \end{cases}} \end{cases} \end{array}$

なんとなくそうなりそうだとは思えますが

これだけ見てもよく分かんないと思います。

具体的な感じ

『区別する』場合

「 $AA$ 」は「 $A_1,A_2$ 」とでもすれば

並び方の総数は ${}_3\mathrm{P}_3=3!$

これはまあ順列を理解していれば当然で

疑問の余地はありません。

で、これと比較すると

『区別しない』場合並び方は

「 $(AAB),(ABA),(BAA)$ 」の $3$ 通りで

$\begin{array}{llllll} \displaystyle 6&&\to&&3 \end{array}$

「区別する」場合の半分になってるわけですが

なんでこうなるのか

どういう計算がなされているのか

具体的にはよく分からないと思います。

具体的な計算の中身

いったいどういった計算をしているのか。

$\displaystyle \frac{{}_3\mathrm{P}_3}{2}=3$

やってることを単純に見ると

まあこうなんですけど

この「分母」の $2$ がどう決まってるのか

この時の「並び方の総数」がどうして半分になるのか

この時点じゃよく分かりません。

『 $A_1$ と $A_2$ を入れ替えても同じ』

この事実からなんとなく察することはできますが

まだこの時点では計算の中身は不明です。

分かることで見てみる

『区別する』パターンは分かっている

その材料を元に考えてみると

$\begin{array}{llllll} \displaystyle A_1 \begin{cases} A_2\begin{cases} B \end{cases} \\ B \begin{cases} A_2 \end{cases}\end{cases} \\ \\ \displaystyle A_2\begin{cases} A_1\begin{cases} B \end{cases} \\ B\begin{cases} A_1 \end{cases} \end{cases} \\ \\ \displaystyle B\begin{cases} A_1\begin{cases} A_2 \end{cases} \\ A_2\begin{cases} A_1 \end{cases} \end{cases} \end{array} ⇐ \begin{array}{llllll} \displaystyle \displaystyle\textcolor{pink}{ A \begin{cases} A\begin{cases} B \end{cases} \\ B \begin{cases} A \end{cases}\end{cases}} \\ \\ \displaystyle \textcolor{pink}{A\begin{cases} A\begin{cases} B \end{cases} \\ B\begin{cases} A \end{cases} \end{cases}} \\ \\ \displaystyle B\begin{cases} \textcolor{skyblue}{A\begin{cases} A \end{cases}} \\ \textcolor{skyblue}{A\begin{cases} A \end{cases}} \end{cases} \end{array}$

よく分からない「区別しない」並べ方の総数 $p$

これを計算するために

一度すべて並べてみて

「 $A$ を区別する」パターンに増やす

$\begin{array}{llllll} \displaystyle AAB&ABA&BAA \end{array}$

$\begin{array}{llllll} \displaystyle AA &\to& \begin{array}{llllll} \displaystyle A_1A_2 \\ A_2A_1 \end{array} \end{array}$

$\begin{array}{rllllll} \displaystyle \overbrace{2!+2!+2!}^{p}&=&{}_3\mathrm{P}_3 \\ \\ p \times 2!&=&{}_3\mathrm{P}_3 \end{array}$

そんな操作を行ってみると

このような形で表現できるのは明らか

$\begin{array}{lcclllll} \displaystyle p \times 2!&=&{}_3\mathrm{P}_3 \\ \\ \\ p&=&\displaystyle\frac{3!}{2!} \\ \\ &=&\displaystyle\frac{3\times 2\times 1}{2\times 1} \end{array}$

となればこの事実から

「区別しない」パターンは

こういう感じで計算されていると考えられます。

一般化

これを一般化して考えてみると

「 $n$ 個を全部並べる」として

『ある１つの要素が $k$ 個』ある

$\begin{array}{llllll} \displaystyle e_1&e_2&\cdots&e_{n-k}&\overbrace{\begin{array}{llllll} \displaystyle e&e&\cdots&e \end{array}}^{k} \end{array}$

とまあこんな感じになるわけですが

これも ↑ の話と同様にすれば

$\begin{array}{rllllll} \overbrace{k!+k!+\cdots +k!}^{p} \\ \\ p\times k!&=& \displaystyle n! \end{array}$

ここで求めたい

『区別しない並べ方の総数 $p$ 』は

このような形で表現できます。

具体的に見てみる

↑ じゃ分かり辛いかもしれないので

とりあえず「 $2$ つ同じ」パターンを考えてみると

$\begin{array}{llllll} \displaystyle e_1&e_2&\cdots&e_{n-2}&\overbrace{\begin{array}{llllll} \displaystyle e&e \end{array}}^{2} \end{array}$

これはもうそのまま

３つで考えた時と同様の話になるので

$\begin{array}{rllllll} \overbrace{2!+2!+\cdots +2!}^{p} \\ \\ \displaystyle p \times 2!&=&\displaystyle n! \end{array}$

こうなるのはすぐに分かると思います。

「同じものが $3$ つ」の時も同様

$\begin{array}{llllll} \displaystyle e_1&e_2&\cdots&e_{n-3}&\overbrace{\begin{array}{llllll} \displaystyle e&e&e \end{array}}^{3} \end{array}$

$2$ つの時と同様に

「 $eee$ 」を区別すれば

$\begin{array}{llllll} \displaystyle (abc)&(acb) \\ \\ (bac)&(bca) \\ \\ (cab)&(cba) \end{array}$

こうですから

「区別しない」パターンのやつは

$\begin{array}{rllllll} \overbrace{3!+3!+\cdots+3!}^{p} \\ \\ \displaystyle p \times 3!&=&n! \end{array}$

こうなります。

同様にしてどんどん増やしていけば

$\begin{array}{llllll} \displaystyle p*k!&=&n! \end{array}$

最終的にこうなる

とまあこんな感じで

『全て並べる』時

「一つの要素が $k$ 個重複している」なら

$\begin{array}{llllll} \displaystyle p*k!=n! &⇒&&\displaystyle p=\frac{n!}{k!} \end{array}$

その並び方の総数はこうなると言えます。

重複するやつが複数の場合

これは同じように

例えば「 $AABB$ 」のような場合でも成立します。

$\begin{array}{llllll} \displaystyle AABB & ABAB & ABBA \\ \\ BAAB & BABA & BAAB \end{array}$

やり方は ↑ と同じです。

「区別しない」パターンの総数 $p$ を

$\begin{array}{rllllll} \displaystyle \overbrace{2!2!+2!2!+\cdots+2!2!}^{p}&=&4! \\ \\ p2!2! &=&4! \end{array}$

「区別する」パターンに組み込めば

同様の手順で求められます。

これを一般化すれば ↓

$\displaystyle \frac{n!}{k_1!k_2}$

更に一般化すれば

$\begin{array}{llllll} \displaystyle \frac{n!}{k_1!k_2!\cdots} \end{array}$

このような形が得られます。

組合せ Combination,Choose

|| あれとそれとこれは選んで他は選ばない

「選び方」が何通りあるかの『数え方』

$\begin{array}{llllll} \displaystyle {}_n \mathrm{C}_r &:=&\displaystyle\frac{n!}{r!(n-r)!} \\ \\ &=&{}_n \mathrm{C}_{n-r} \\ \\ \\ \displaystyle {}_n\mathrm{H}_r&:=&\displaystyle\frac{(n-1+r)!}{(n-1)!r!} \\ \\ &=&\mathrm{}_{n-1+r}\mathrm{C}_{r} \end{array}$

上が「組み合せ」

下が「重複組み合せ」です。

選んだやつは選べない組み合せ

『選ぶ・選ばない』で作られる「順列」のこと

$\displaystyle\frac{n!}{r!(n-r)!}$

具体的には

「 $A,B,C$ 」で考えると

ここから「 $2$ つ選ぶ」時

$\begin{array}{ccccccl} \displaystyle A&B&C \\ \\ 〇&〇&× \\ \\ 〇&×&〇 \\ \\ ×&〇&〇 \end{array}$

その選び方は $3$ 通り

$\begin{array}{llllll} \displaystyle \frac{n!}{r!(n-r)!} \end{array}$

『 $n$ 個』の中から

『 $r$ 個選ぶ』時もこれは同様になります。

組み合せの導出

「選ぶことを示す $〇$ 」が『 $r$ 個』ある

「選ばないことを示す $\times$ 」が『 $n-r$ 個』ある

$\begin{array}{llllll} \displaystyle \overbrace{〇〇〇\cdots 〇}^{r}\underbrace{×××\cdots ×}_{n-r} \end{array}$

こんな感じに考えると

『選び方』は $〇\times$ の順列なので

$\begin{array}{llllll} \displaystyle n! \end{array}$

$〇\times$ の数に依らず

$〇\times$ を区別するならこう

$\begin{array}{rllllll} \displaystyle \overbrace{r!(n-r)!+r!(n-r)!+\cdots +r!(n-r)!}^{p}&=&n! \\ \\ \displaystyle pr!(n-r)!&=&n! \\ \\ p&=&\displaystyle \frac{n!}{r!(n-r)!} \end{array}$

で、選ぶ $〇$ を $r$ 個だとするなら

選ばない $\times$ は当然 $n-r$ 個ですから

区別しない場合はもちろんこうなります。

選んだやつをまた選べる組合せ

同じものを何度選んでも良い『選び方』

$\begin{array}{llllll} \displaystyle {}_n\mathrm{H}_r&:=&\displaystyle\frac{(n-1+r)!}{(n-1)!r!} \\ \\ &=&\mathrm{}_{n-1+r}\mathrm{C}_{r} \end{array}$

具体的には

例えば「 $A,B$ 」があって

そこから「 $3$ 回選ぶ」とすると

$\begin{array}{llllll} \displaystyle AAA&AAB&ABB&BBB \end{array}$

その「選び方」はこの $4$ 通りになりますよね。

これが「重複組み合せ」と言われるもので

これもまた「順列」によって一般形が得られます。

重複組み合わせの導出

これは「仕切り $|$ 」を考えることで

$\begin{array}{llllll} \displaystyle AA|| & A|B| & |BB| \\ \\ |B|C & ||CC &A||C \end{array}$

一般形を求めることができます。

というのも

この「仕切りの位置」で

『要素の個数』が決まるとすると

$\begin{array}{llllll} \displaystyle |XXX & X|XX & XX|X & XXX| \end{array}$

例えば「 $3$ つ並べる」とするなら

「仕切りの左に $A$ 」として

「仕切りの右に $B$ 」とすれば

$\begin{array}{llllll} \displaystyle AAA| & AA|B & A|BB & |BBB \end{array}$

「 $A,B$ 」の個数は

『仕切り』の位置で一意に定まります。

つまり「仕切り」と「選ぶ個数」が決まれば

$\begin{array}{llllll} \displaystyle XXX||| \end{array}$

この組み合わせの総数は決まるわけです。

この事実から

「選ぶ選択肢の種類 $n$ 個」から

『選ぶ数を $r$ 個』とすると

『仕切り』は「間」に来るので

$\begin{array}{llllll} \displaystyle A|B|C|D \end{array}$

「 $n-1$ 個」ですから

$\begin{array}{llllll} \displaystyle \overbrace{XXX\cdots X}^{r}\underbrace{|||\cdots |}_{n-1} \end{array}$

『仕切りの数』と『選ぶ数』から

全体の数 $n-1+r$ が得られて

$\begin{array}{rllllll} \displaystyle \overbrace{r!(n-1)!+\cdots+r!(n-1)}^{p}&=&(r+n-1)! \\ \\ \displaystyle pr!(n-r)!&=&(r+n-1)! \\ \\ \displaystyle p&=&\displaystyle\frac{(n-1+r)!}{(n-1)!r!} \end{array}$

この「順列」と「重複」を考えると

結果、こうなることが分かります。

二項定理 Binomial Theorem

|| 数え上げの主要な成果の一つ

$n$ 次多項式の「係数」についての定理

$\begin{array}{llllll} \displaystyle (x+a)^2&=&x^2+2ax+a^2 \\ \\ (x+a)^3&=&x^3+3ax^2+3a^2x+a^3 \end{array}$

$\begin{array}{llllll} \displaystyle (a+b)^n &=&\displaystyle(a+b)(a+b)(a+b)\cdots(a+b) \\ \\ &=&{}_n \mathrm{C}_0a^nb^0 + {}_n \mathrm{C}_1a^{n-1}b^1 +\cdots+{}_n \mathrm{C}_n a^0b^n \end{array}$

いろいろなところでかなり便利なので

覚えておきたいやつになります。

二項定理の導出

組み合わせを理解していれば

これはわりと簡単に理解できます。

$\begin{array}{rrrrllll} \displaystyle (a+b)^4&=&(a+b)(a+b)(a+b)(a+b) \\ \\ &=&\begin{array}{rrllllll} \displaystyle &a(a+b)(a+b)(a+b) \\ +& b(a+b)(a+b)(a+b) \end{array} \\ \\ &=&\begin{array}{rrllllll} \displaystyle &aa(a+b)(a+b) \\ +& ab(a+b)(a+b) \\ +&ba(a+b)(a+b) \\ +&bb(a+b)(a+b) \end{array} \end{array}$

$\begin{array}{rllllll} \displaystyle & aaaa&+&aaab&+&aaba&+&aabb \\ \\ +&abaa&+&abab&+&abba&+&abbb \\ \\ +&baaa&+&baab&+&baba&+&babb \\ \\ +&bbaa&+&bbab&+&bbba&+&bbbb \end{array}$

$\begin{array}{llllll} \displaystyle a^4b^0 &&{}_4 \mathrm{C}_4 \\ \\ a^3b^1 &&{}_4 \mathrm{C}_3 \\ \\ a^2b^2 &&{}_4 \mathrm{C}_2 \\ \\ a^1b^3 &&{}_4 \mathrm{C}_1 \\ \\ a^0b^4 &&{}_4 \mathrm{C}_0 \end{array}$

というのも

例えば $n=4$ のパターンはこう

$\begin{array}{rrrrllll} \displaystyle (a+b)^n&=&\displaystyle \overbrace{ (a+b)(a+b)(a+b)\cdots (a+b)}^{n} \\ \\ &=&\begin{array}{rrllllll} \displaystyle &a(a+b)(a+b)\cdots(a+b) \\ +& b(a+b)(a+b)\cdots(a+b) \end{array} \\ \\ &=&\begin{array}{rrllllll} \displaystyle &aa(a+b)\cdots(a+b) \\ +& ab(a+b)\cdots(a+b) \\ +&ba(a+b)\cdots(a+b) \\ +&bb(a+b)\cdots(a+b) \end{array} \end{array}$

つまり $n$ だとこうなるので

$\begin{array}{llllll} \displaystyle a^nb^0 &&{}_n \mathrm{C}_0 \\ \\ a^{n-1}b^1 &&{}_n \mathrm{C}_1 \\ \\ &\vdots& \\ \\ a^1b^{n-1} &&{}_n \mathrm{C}_{n-1} \\ \\ a^0b^n &&{}_n \mathrm{C}_n \end{array}$

必然、係数はこうなります。

以上のことから

$\begin{array}{llllll} \displaystyle (a+b)^n&=&{}_n \mathrm{C}_0a^nb^0 + {}_n \mathrm{C}_1a^{n-1}b^1 +\cdots+{}_n \mathrm{C}_n a^0b^n \\ \\ &=&\displaystyle\sum_{k=0}^{n} {}_n \mathrm{C}_k a^{n-k}b^{k} \end{array}$

二項定理が導かれて

$\begin{array}{llllll} (1+1)^n&=&{}_n \mathrm{C}_01^n1^0 + {}_n \mathrm{C}_11^{n-1}1^1 +\cdots+{}_n \mathrm{C}_n 1^01^n \\ \\ &=&{}_n \mathrm{C}_0 + {}_n \mathrm{C}_1 +\cdots+{}_n \mathrm{C}_n \\ \\ &=&\displaystyle\sum_{k=0}^{n} {}_n \mathrm{C}_k \end{array}$

例えばこんな等式が得られたりします。

目次