|| 人間のための、数への探求
ここでの主なトピックは「数え上げ」です。
いわば『数学の出発点』を拡張したものがこれになります。
スポンサーリンク
目次
数え上げ「順列とか組合せとか使うやつ」
順列「順番に並べるとき、並べ方は何通りか」
同じ要素を区別する「同じものを入れ替えても同じ」
具体例「実際どんな感じか」
一般化「正しさについて帰納的に見てみる」
個数を指定「こうすると成立しないことを確認」
組合せ「同じものは一回だけ選ぶとき、選び方は何通りか」
重複組み合わせ「同じものも選んで良い場合」
主に「有限」のものをここでは扱います。
基本は集合の中にある『要素の数を数える』感じ。
ずばり『基礎』です。
主要な成果は多大ですが、地味っちゃ地味。
いわゆる基礎、『数え上げ』なので。
ともあれ、その分類は大きく分けて 4 つです。
一つは基礎となる『数え上げ』で、
『最大・最小・最適』を発見する「極値」「最適化」が。
『条件の判定や構成、解析』をする「デザイン」「マトロイド理論」が。
『代数的構造の発見』を行う「代数的組合せ論」が。
ここでは主に、基本的な「数え上げ」を見ていきます。
他は専門性が高い上に他の分野の知識も使うので、
ちょっと基本的とは言えないですね。
数え上げ Counting
|| 全てはここから始まった
いっこ、にこ、さんこ、、、、ってやつです。
『数え上げ的組合せ論』では、
『集合』の中にある「要素」の「組合せ」を考えます。
これは『公理的集合論』の「外延性の公理」から、
『中身の並びは関係なく、同じものは一つだけ』な性質から、
「事象の組合せの総数」と、
「集合の要素の組合せの総数」は一致すると分かります。
この性質こそが基礎付け、いわば「正しさの保証」なわけです。
人間が『数』を意識するときは、基本はこれです。
はい。全てはここからなんです。
厳密には「ある」「なし」や、
「はい」「いいえ」なんてのも、数的なものです。
これを確定させるには必ず『数学的な処理』が必要になります。
また他にも『量』的なものも「数学」は扱います。
主に『全部』とか『いくつか存在する』みたいな。
ともあれ、人が『数』をよく意識するのは『数え上げ』です。
『数』という概念を形成する印象の中身はほとんどこれでしょう。
「はい」「いいえ」も『全部』『いくつかある』も。
他には『じゃない』『または』『かつ』『ならば』も。
背後は数学ですが、感覚的には数っぽくないですし。
順列 Permutation
|| 順番に並んでる列
「並び」が何通りあるか、の『数え方』のことです。
これは『数え方』の基本になります。
繰り返しを許した順列
例えば「 A,B 」を「 2 つ並べる」時の『並べ方』は、
「 (AA),(AB),(BA),(BB) 」の 4 通りです。
どうやってこれを求めたかというと、
要は↓みたいに、考えたわけです。
これの数を増やすと↓みたいになって、
この並び方が何通りあるかは、
「違うとしたものが n 個」あって「 r 個並べる」と、
『 n^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 」と要素があったら、
「 A と A 」を『区別しない』並べ方の総数のこと。
結論から行くと、
「 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_1 と A_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
ただこの場合も「最低限含んでいる数」が初期値に来るので、
見た目けっこうややこしいです。
三次方程式の解の公式ほどじゃないですけど、いや扱いづらい。
ちなみに『初期値』が 1 で r=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!}
となります。
