順列と組合せ。 順列式と組合せ式の違いとは？
ここで簡単に説明します。
教会で鐘を鳴らすことを例にとって考えてみましょう。
順列とは、鐘の並び順のことです。
組合せとは、鐘の選択です。 あなたは鳴らすベルを選んでいるのです。 鐘の数が多ければ、まずそれを選んでから順番を考えるだろう。
このことから、お馴染みのIDが生まれる。 (n P r) = (n C r) * r!
nの中からr個の品物を注文する方法は、まずnの中からr個を選び、それからr個を注文する (r! )
そして、これは(n P r) = n! / (n-r)!と(n C r) = n! / ( (n-r)! * r! )
しかしこれをずっと覚えておく方法が知りたいですかね
〈258>私は第1原理思考に大賛成しているんですよ。 問題を理解するには、その核心に触れ、そこから推論します。
これをしないことは、たいてい混乱の原因です。 私の精神的な枠組みは完全ではないので、ただ記憶することにしています。
今回は、順列と組み合わせの直観を構築します。
たとえば、組み合わせの式がなぜ (n C r) か知っていますか。 これはどこから来たのでしょうか。 また、なぜここで階乗が使われるのでしょうか。
まずは、出典から見ていきましょう。 スティーブ・ジョブズとスティーブ・ウォズニアックがガレージで一緒に遊んでアップル社を設立したように、階乗、並べ換え、および組み合わせは、数学者の遊びから生まれたのだ
アップルが本格的に利益を生む会社になったように、単純な階乗 ! は数学分野全体の原子となった。
すべてを忘れて、ボトムアップで考え始めよう。
最初の興味深い使用例は、17 世紀に教会からもたらされました。 順番に「鳴らす」機械があるのです。 鐘が大きすぎるから機械に変えたんだ。 また、鐘は大量にあります。
人々はどのようにして鐘を鳴らすのに最適な順序を見つけたのでしょうか？ もし、いろいろなものを入れ替えたい場合はどうすればよいのでしょうか。 どうしたら、いちばんいい音が出せるのだろう。 各鐘楼には最大16個の鐘があった！
鐘を鳴らす速さを変えることはできなかった-機械は1秒に1個の鐘しか鳴らさない。 唯一できたことは、鐘の順番を変えることでした。 そこで、この課題は、最適な順序を見つけ出すことでした。
途中で、可能なすべての順序を見つけ出すこともできるでしょうか。
鐘を鳴らす人、ファビアン・ステッドマンがこの課題に取り組みました。
彼は2つのベルを用意しました。このベルを鳴らす順番はどうなるでしょうか。
3つのベルではどうでしょうか？
1, 2, and 3.
1, 3, and 2.
次に2番目のベルから、
2, 1, and 3.
2, 3, and 1.
次に3番目のベルから、
3, 1, and 2.です。
3, 2, and 1.
Total, 6.
He then realized this is very similar to two bells!
If he fixed the first bell, then the number of ways to order the remaining two bells is always two.
How many ways could fix the first bells?
最初のベルは何通りあるのだろうか？
このとき、彼は手でやるのは扱いにくいことに気づきました。 一日の時間は限られている、ベルを鳴らさなければならない、可能なベルをすべて引き出しては身動きがとれないのだ。
彼は自分の洞察に戻りました。
もし彼が5つのベルを持っていて、最初のベルを修正したら、4つのベルを注文する方法を考えなければなりませんでした。 まあ、もし彼が4つのベルを持っていて、最初のベルを直したなら、彼がしなければならなかったのは3つのベルを注文する方法を見つけ出すことだった。
そして彼はこれを行う方法を知っていた
つまり、5つのベルの順番 = 5 * 4つのベルの順番
4つのベルの順番 = 4 * 3つのベルの順番
3つのベルの順番 = 3 * 2つのベルの順番
…というわけです。
Fun Fact: これが再帰と呼ばれるプログラミング技法の鍵です。
彼もそうしました。
こうして彼は、5つの鐘の順序＝5 * 4 * 3 * 2 * 1であることを突き止めた。
この順序式は、1808年に、階乗として知られるようになった。
我々は階乗表記を基本として考えているが、この考えは名前を持つずっと前に存在していたのである。 フランスの数学者クリスチャン・クランプが、それがいくつかの場所で使われていることに気づいて、初めて階乗と名付けたのである。
このベルの順序付けは順列と呼ばれる。
何かを学ぶとき、あらゆる角度から物事を見ることで、理解を深めることができると思います。
問題をより少ないベルの数に減らそうとせず、上の式を直接導こうとしたらどうでしょうか？
スペースは5つありますよね？
最初のベルは何通り選択できるのでしょうか？
2個目のベルは？ そうですね、最初の位置に置くときにベルを1つ使い切ったので、残りベルは4つです。
3つ目のベルは？ さて、最初の2つを選んだので、残りは3つのベルだけです。
4つ目のベルは？ 残りベルは2つなので、選択肢は2つです。
5つ目のベルは？
そしてこうして、順序の総数は 5 * 4 * 3 * 2 * 1
となり、最初の一般式ができあがりました。
N個の注文方法はN!
さて、今度は別の問題に直面することになる。 王はすべての教会に新しい鐘を作るように命じました。 いいものもあれば、まあまあのものもあり、耳が遠くなるようなものもある。 しかし、どれも個性的です。 それぞれが独自の音を奏でる。 耳をつんざくような鐘が素敵な鐘に囲まれていると、荘厳な響きになります。
でも、うちの鐘楼にはまだ5つの鐘があるので、熟練の鐘職人が作った8つの鐘から、最適な順番を考えなければなりません。
上記のロジックで進めると、
最初の鐘は、8つの鐘からどれを選んでも良い。
2番目の鐘は、残りの7つの鐘からどれかを選ぶ…といった具合だ。
最終的に、5つの空間に8つのベルを配置した場合、8 * 7 * 6 * 5 * 4通りの順序が得られます。
(n P r) の公式バージョン、n! / (n-r)!に慣れている人は、心配しないでください、これもすぐに導きますよ。
これを導く悪い方法の1つは、分子と分母の両方に3を掛けることです！上の例では –
で、8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1 = 8! / 3!.
ですが、これではなぜこの式が成り立つのか理解することはできません。
The Combination
さて、ものの並び方がわかったので、ものの選び方を考えましょう！
同じ問題を考えてみましょう。 5つの鐘がある鐘楼があり、あなたは8つの鐘を持っています。 しかし、今、あなたは鐘の順番を考えたくありません（それが順列であることを思い出してください）
その代わりに、最高の5つの鐘を選び、音楽の趣味の良い他の人に順番を考えさせたいのです。 事実上、私たちは問題をいくつかの部分に分割しています。 まず、どのベルを選ぶかを考えます。 次に、選んだ鐘をどのように並べるかを考える。
どのように鐘を選ぶか？ これは順列と組み合わせからの「組み合わせ」です。
組み合わせは選択です。 選択式なんだろ。 職人が作った8つのベルから5つを選んでいるのです。
ベルの注文方法がわかったので、この情報を使ってベルの選び方を考えてみましょう。 不可能に聞こえますか？
すべてのベルが一列に並んでいると想像してみましょう。
ベルを選択するすべての方法を見つける前に、ベルを選択する一つの方法に焦点を当てましょう。
この方法は問題を解くのにあまり役立たないので、別の方法を試してみましょう。
ベルを一列に並べ、最初の5個を選びます。
最初の5つの鐘の位置を入れ替えても、選択は変わらないことに注意してください。
これは最後の3つのベルにも当てはまります。
さて、美しい数学のトリックですが、この5つのベルを選ぶ1つの方法に対して、まさにこの5つのベルを選ぶ8つのベルのすべての順序はどうなっているでしょうか。 上の画像から、それは5つのベルのすべての順序（5!）と残りの3つのベルのすべての順序（3!）です。
したがって、5つのベルを選択するすべての方法に対して、8つのベルの順序は（5! * 3!）あります。 8!.
最初の5つのベルを選択するごとに、同じ選択をする8つのベルの順序が(5! * 3!)あることを思い出してください。
次に、最初の5つのベルを選択する方法の数と、一つの選択に対して考えられるすべての順序を掛けると、順序の合計数が求まるはずです。
Ways to choose 5 bells * orderings of one choice = Total orderingsつまり、
Ways to choose 5 bells = the total possible orderings / total orderings of one choice.数学では、次のようになります。
(8 C 5) = 8! / ( 5! * 3!)なんと、8つのうち5つを選ぶ方法について直観的に説明できることがわかったのです。 N個の物があり、その中からR個を選びたい場合、Rで線を引くということです。
つまり、残りの物はN-R個になります。 つまり、R個のアイテムの1つの選択に対して、同じR個のアイテムを与えるR! * (N-R)!個の順序がある。
R個のアイテムを選ぶすべての方法に対して、N! / (R! * (N-R)!)通りの可能性があるのである。
n個の中からr個のアイテムを選ぶ方法の数は、(n C r) = n! / (r! * (n-r)!)
口語では、（n C r）はn choose rとも発音し、組み合わせはアイテムを選ぶためのものだという考えを確固たるものにします。
The Permutation – revisited
コンビネーションが終わり、仕事のその2に戻ってきましょう。 親愛なる友人は、5 つの鐘のすべての可能な組み合わせを計算することによって、最高の 5 つの鐘を選びました。
今度は、順序の数を計算することによって完璧なメロディーを見つけるのが私たちの仕事です。 5個の注文の仕方はすでに分かっているのです。 5! で、終わりです。
つまり、8つのうち5つの項目を並べ替える（順序付ける）には、まず5つの項目を選び、次にその5つの項目を並べます。
つまり、(8 P 5) = (8! / ( 5! * 3!)) * 5!
(8 P 5) = 8! / 3! と式を展開すれば、
と、ちゃんと導かれた、元の公式に一回りしているのです。
n個のうちr個を並べる方法の数は(n P r) = n! / (n-r)!
順列と組み合わせの違い
これで順列と組み合わせの違いがはっきりしましたね。
順列は順序、組み合わせは選択肢。
N個並べるには直感的に答えを出す方法が2通りわかりましたね。 どちらもN!という答えを導き出します。
8つの要素のうち5つを順列化するためには、まず5つの要素を選び、それを順序付ける必要があります。 8474＞で選び、＜3700＞で5個並べる。＜6953＞＜258＞そして＜5266＞から＜3519＞を選ぶ直感は、すべての並び（＜8090＞）を把握して、最初の＜3519＞と最後の＜6428＞が変わらない並び（＜1151＞と＜9296＞）で割っていることです。
そして、順列と組み合わせはこれだけです。
あらゆる高度な順列と組み合わせはこれをベースにしています。 置き換えで組み合わせ？ 同じ考えだ。 同じものを使った順列？ 同じ考えですが、いくつかの項目が同一なので、順序の数が変わるだけです。
もし興味があれば、別の例で複雑なケースに踏み込むことができます。 Twitterで教えてください。
Check out more posts on my blog, and join the weekly mailing list.
End notes
- これが、彼が物事を理解する方法だと想像しています。 歴史の勉強と思わないでください。
- インド人は12世紀、彼より400年前に、
ありました。