組合せ数学 Combinatorics


|| 人間のための、数への探求

ここでの主なトピックは「数え上げ」です。

いわば『数学の出発点』を拡張したものがこれになります。

スポンサーリンク




目次


数え上げ「順列とか組合せとか使うやつ」


   順列「順番に並べるとき、並べ方は何通りか」

      同じ要素を区別する「同じものを入れ替えても同じ」

         具体例「実際どんな感じか」

         一般化「正しさについて帰納的に見てみる」

         個数を指定「こうすると成立しないことを確認」


   組合せ「同じものは一回だけ選ぶとき、選び方は何通りか」

      重複組み合わせ「同じものも選んで良い場合」








主に「有限」のものをここでは扱います。

基本は集合の中にある『要素の数を数える』感じ。

ずばり『基礎』です。




主要な成果は多大ですが、地味っちゃ地味。

いわゆる基礎、『数え上げ』なので。




ともあれ、その分類は大きく分けて 4 つです。

一つは基礎となる『数え上げ』で、



『最大・最小・最適』を発見する「極値」「最適化」が。

『条件の判定や構成、解析』をする「デザイン」「マトロイド理論」が。

『代数的構造の発見』を行う「代数的組合せ論」が。






ここでは主に、基本的な「数え上げ」を見ていきます。



他は専門性が高い上に他の分野の知識も使うので、

ちょっと基本的とは言えないですね。







数え上げ Counting


|| 全てはここから始まった

いっこ、にこ、さんこ、、、、ってやつです。




『数え上げ的組合せ論』では、

『集合』の中にある「要素」の「組合せ」を考えます。




これは『公理的集合論』の「外延性の公理」から、

『中身の並びは関係なく、同じものは一つだけ』な性質から、



「事象の組合せの総数」と、

「集合の要素の組合せの総数」は一致すると分かります。



この性質こそが基礎付け、いわば「正しさの保証」なわけです。




人間が『数』を意識するときは、基本はこれです。

はい。全てはここからなんです。




厳密には「ある」「なし」や、

「はい」「いいえ」なんてのも、数的なものです。

これを確定させるには必ず『数学的な処理』が必要になります。



また他にも『量』的なものも「数学」は扱います。

主に『全部』とか『いくつか存在する』みたいな。




ともあれ、人が『数』をよく意識するのは『数え上げ』です。

『数』という概念を形成する印象の中身はほとんどこれでしょう。




「はい」「いいえ」も『全部』『いくつかある』も。

他には『じゃない』『または』『かつ』『ならば』も。

背後は数学ですが、感覚的には数っぽくないですし。







順列 Permutation


|| 順番に並んでる列

「並び」が何通りあるか、の『数え方』のことです。

これは『数え方』の基本になります。






繰り返しを許した順列


例えば「 A,B 」を「 2 つ並べる」時の『並べ方』は、

(AA),(AB),(BA),(BB) 」の 4 通りです。



どうやってこれを求めたかというと、

要は↓みたいに、考えたわけです。


\displaystyle A \begin{cases} A \\ B \end{cases} \displaystyle B\begin{cases} A \\ B \end{cases}



これの数を増やすと↓みたいになって、


\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}


この並び方が何通りあるかは、

「違うとしたものが n 個」あって「 r 個並べる」と、

n^r 通り』になります。






繰り返しを許さない順列


いわゆる『選んだら減る』並べ方です。

こっちの方が良く見るでしょう。



↑みたいに見ると↓みたいになります。


\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! 』というものを使って表されます。


n!:=n(n-1)(n-2)(n-3)...3*2*1




↑のを見て分かる通り、並べ方は↓通りです。

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



そしてこれは↓でもあります。

\displaystyle \overbrace{n(n-1)…(n-r+1)}^{r}*1=n(n-1)...(n-r+1)*\frac{(n-r)!}{(n-r)!}=\frac{n!}{(n-r)!}




そして、これが↓みたいに省略されるわけですね。

\displaystyle P(n,r)\,\,\,\,\,\,P_{n,r}\,\,\,\,\,\,{}_n\mathrm{P}_r:=\frac{n!}{(n-r)!}







同じ要素を同じとする場合の順列


いわば「 AAB 」と要素があったら、

AA 」を『区別しない』並べ方の総数のこと。




結論から行くと、

n 個の中で、一つの要素が k 個同じ」な場合の並べ方は、


\displaystyle \frac{n!}{k!}






具体例からこれを求めてみましょう。



まず『区別する』場合、

この二つは「 A_1,A_2 」とでもすればいいわけです。

そうすれば並び方の総数は「 {}_3\mathrm{P}_3=3! 」になるので。




具体的には↑の並びは↓になります。

(A_1A_2B),(A_1BA_2),(BA_1A_2) 」と、

(A_2A_1B),(A_2BA_1),(BA_2A_1) 」です。




見て分かる通り『区別しない』場合は、

↑の並び方は「 (AAB),(ABA),(BAA) 」となって、

「区別する」場合の半分になります。




さて、ではこれはいったいどういう計算をしてるんでしょうか?

見た感じだと、計算の処理は↓っぽく見えます。


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



しかしはて、この「分母」の数 2 はどう決まってるんでしょう?

この時の「並び方の総数」は、どうして半分になるんでしょうか?




まあ↑の具体例を見ると、なんとなく分かると思います。

要は『 A_1A_2 を入れ替えても同じ』ということなので、

全体となる「区別する」場合から、同じものを除けば良いわけです。




すると求めたい「区別しない」並べ方の総数 p は、


\displaystyle p*2!={}_3\mathrm{P}_3\,\,\,\,\,⇒\,\,\,\,\,p=\frac{{}_3\mathrm{P}_3}{2!}=\frac{3*2*1}{2*1}


となるというわけですね。






一般化


これを一般化して考えてみましょう。

というわけで「全体 n 個」から「 n 個並べる」として、

『ある要素一つが k 個』あるとします。




これらを並べると↓みたいな感じになるわけです。

\displaystyle e_1,e_2,…e_{n-k},\overbrace{e,e,…e}^{k}



これの並べ方の総数が、求める「区別しない並べ方」になります。

ここで、求める『区別しない並べ方の総数』を「 p 」としましょう。




まず「同じものが 2 つ」の場合を考えてみます。

この時の並びを、具体的に一つ考えてみます。

\displaystyle e_1,e_2,…e_{n-2},\overbrace{e,e}^{2}



こういうのが「 p 通り」考えられるわけです。



そして『全て並べてる』わけですから、

この『重複する要素 e 』は、全ての並びに含まれてます。




ということは「区別する場合の並べ方」から↓だと分かります。

p(1*2!)=p*2!=n!




同様に「 3 」つある場合を考えてみましょう。

この時の具体的な並び方の一例は↓です。

\displaystyle e_1,e_2,…e_{n-3},\overbrace{e,e,e}^{3}



2 つの時と同様に、

↑の一例を区別すると「 eee 」の部分の並び方は、

(e_ae_be_c),(e_ae_ce_b)\,\,\,(e_be_ae_c),(e_be_ce_a)\,\,\,(e_ce_ae_b),(e_ce_be_a)



つまり「 3! 」通りであることから、

p(1*3!)=n!




同様にしてどんどん増やしていくと、

p*k!=n!

となることが分かります。



というわけで、求めたいものはこれにて求めることに成功しました。

『全て並べる』とき「一つの要素が k 個重複している」なら、


\displaystyle p*k!=n!\,\,\,⇒\,\,\,p=\frac{n!}{k!}


となります。






複数の場合


そしてこれは同じように、

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




やり方は↑と同じです。

まずは「区別する」ことにして、全体を求めます。



その後、↑のように「一つずつ区別しない」でやっていけば、

↑の例なら↓ですから、

(AABB)(ABAB)(ABBA)(BAAB)(BABA)(BAAB)


\displaystyle \frac{4!}{2!2!}=\frac{4*3*2*1}{2*1*2*1}=6

となります。




これを一般化すると↓みたいになります。


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







全て並べない場合


結論は↓になります。


p*k!≠{}_n\mathrm{P}_r\,\,\,(r<n,k≠2)



というわけで↑を確認してみましょう。

なのでさっそく、具体例から見てみましょうか。



さて、では「 r\,\,\,(r<n) 個並べる」ときはどうでしょう。

いわゆる「全体」ではない場合であると、これでいけるんでしょうか?

確認してみましょう。




具体的には「 AAB 」からの、

(AA),(AB),(BA) 」の並び方とかですね。

これもまた、まずは「区別する」方を求めてみましょうか。



すると↑の A を「 A_1,A_2 」とするので、

3*2!={}_3\mathrm{P}_2 となります



一致してるので、一見するとこれでオッケーです。



ただ、なんだかこれじゃちょっと不足気味な感じがします。

並びというより、このままだとただの入れ替えという感じ。

なにせ「 2 のときは n=n! 」ですから。

n=0,n>3\,\,\,⇒\,\,\,n≠n!






そこで、今度は「 AAAB 」で考えてみます。

同じ手順で、これの具体例は↓です。

(AA),(AB),(BA)




区別した場合は {}_4\mathrm{P}_2=4*3=12 通りなので、

3*3!≠4*3



あら、今度は結果が不一致となりました。



ということは「個数を指定」した場合、

単に割るだけではだめだと、これで確定ですね。






結果からちゃんと求めてみましょう。

「区別する」のなら、


(AA) のときは {}_3\mathrm{P}_2=6 で、

(AB),(BA) のときは {}_3\mathrm{P}_1=3 で、

合計で 6+3*2=12 通りです






はい。見ての通りです。

p*k!={}_n\mathrm{P}_r\,\,\,(r<n) 」とはなりません。



2 はやはり鬼門ですね。

ちゃんと確かめてみないと合ってるかどうか分からないです。




さて、ともかくこうなると別の考え方が必要になります。

一般形をパッと考えてみても、ちょっと複雑な感じ。



やるだけやってみましょう。

前提は↑のものをそのまま使うことにします。




まず考えるべきは「並べる r 個」の中に、

「重複する要素 k 個の内、いくつ」含まれているかです。



これを統一して考えることは、なんかちょっと難しそう。

こうなるともう、場合分けするしかありませんね。






ただその前に、まず↑みたいにして簡単に考えてみましょう。

求めたい「重複を省いた並び方の総数」を「 p 」とします。




そしてその一例を見てみましょう。



k の内 1 個含まれる」場合、

これは『区別すると {}_k\mathrm{P}_1 通り』あります。



k の内 2 個含まれる」場合、

これは『区別すると {}_k\mathrm{P}_2 通り』あります。



同様にして、

k の内 i\,\,\,(i≤k) 個含まれる」場合、

これは『区別すると {}_k\mathrm{P}_i 通り』あります。




つまりは「区別すると」↓だということですね。



\displaystyle \overbrace{{}_k\mathrm{P}_1+{}_k\mathrm{P}_2+…+{}_k\mathrm{P}_i+…}^{p}≤{}_n\mathrm{P}_r



これはまあ「不等号」をつけるのが適切でしょう。

なぜなら『 k が一つも入ってない』という場合もあります。



この並びもまた「 {}_n\mathrm{P}_r 」は含んでますから、

その時はどうしても大きくなっちゃいます。






はい。というわけで、これは簡単にできません。

どうしても複雑になっちゃいます。



それでもまあ、せっかくですからまとめてみましょう。

r,k 」を使って場合分けです。




まず『重複するものが k 個ある』わけです。

これを前提に『 r 個並べる』ということを考えます。




・「重複するもの」を含まない場合がある時

これは『 r 個の中に入ってない場合がある』ってことなので、



つまりは『 r≤n-k 』の場合になります。

意訳すれば『 n から k を取り除いた個数より、

並べる数 r は少ない』ということです。




そしてこの時↓になります。


\displaystyle \overbrace{{}_k\mathrm{P}_1+{}_k\mathrm{P}_2+…+{}_k\mathrm{P}_i+…+{}_k\mathrm{P}_r}^{r}≤{}_n\mathrm{P}_r



並べる限界は「 r 」ですから、

重複しているものが含まれる最大の数も『 r 』になります。

つまりこの時は、このアプローチの意味はあまりないですね。






・「重複するもの」を必ず含んでしまう場合

これは↑にならうと『 r>n-k 』ということです。




この場合は『一部』または『全て』含んでるので、

この時は↓になります。



\displaystyle \overbrace{{}_k\mathrm{P}_{r-(n-k)}+{}_k\mathrm{P}_{r-(n-k)+1}+…+{}_k\mathrm{P}_i+…+{}_k\mathrm{P}_p}^{r}={}_n\mathrm{P}_r



ただこの場合も「最低限含んでいる数」が初期値に来るので、

見た目けっこうややこしいです。

三次方程式の解の公式ほどじゃないですけど、いや扱いづらい。



ちなみに『初期値』が 1r=p の時は、

↑で示したように、



\displaystyle \overbrace{{}_k\mathrm{P}_{1}+{}_k\mathrm{P}_{2}+…+{}_k\mathrm{P}_i+…+{}_k\mathrm{P}_p}^{p=r}={}_n\mathrm{P}_r



となるわけですね。

というわけで、使いやすいのはこれだけです。

ただ条件が多すぎて、うーんって感じ。








組合せ Combination,Choose


|| あれとそれとこれは選ぶ、他は選ばない

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






繰り返しを許さない組み合わせ


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



具体的には「 A,B,C 」があって、

2 つ選ぶ」とき、その選び方は、


(〇〇×),(〇×〇),(×〇〇)3 通りになります。




これは『 n 個』あって、

r 回選ぶ』とするなら、



「選ぶことを示す 」が『 r 個』あって、

「選ばないことを示す × 」が『 n-r 個』あるってことです。




つまり『選び方』は、このとき↓通り考えられます。

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



これは重複するものがある『順列』の数え方から明らかです。






繰り返しを許す組合せ


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

「重複組み合わせ」とか言ったりします。




これは「選び終わったものを入れた箱」を考えて数えます。

重要なのは、この箱には『仕切りがある』ということです。



つまるところ「選ばれたもの」はいくつか入ってて、

「選ばれてないもの」には一つも入ってないわけです。




具体的に見てみましょう。

A,B 」があって、「 3 回選ぶ」とします。



このとき考えられる選び方は↓

(AAA),(AAB),(ABB),(BBB)4 通りです



これは一見、分かるようで分かりません。

なんか結果も分かるし作れるけど、

一般形となると、途端に ん?ってなります。



というわけで、先ほど述べた「仕切り」についてざっと。

↑の例を使うと、「仕切り | 」を使えば↓みたいになります。

(AAA|),(AA|B),(A|BB),(|BBB)




この「仕切りの位置」で『ある要素の個数』が決まるので、

こうすると、なんで「 2,3 」から、いきなり、

4 』なんて数が出てきたのか、なんとなく分かります。



要は、↑なら、

(|XXX),(X|XX),(XX|X),(XXX|) 」でいいわけです。

A,B 」の判定は『仕切り』の位置で決定します。




こうなると、後は単純です。

『選ぶ数』と『仕切り』で順列を考えれば良いだけなので、



『選ぶ数を r 個』とし、

選ぶ選択肢の種類 n 個を、

『仕切りを n-1 個』で区分けするとします。




すると『仕切りの数』と『選ぶ数』から、全体の数 n-1+r が。

これの「並び方」ですから、↑の組合わせと同じように考えて、


\displaystyle {}_n\mathrm{H}_r:=\frac{(n-1+r)!}{(n-1)!r!}


となります。