順列と組み合わせ:順列式と組み合わせ式の違いは何ですか?

これが短いバージョンです。

例として、教会で鳴っている鐘を取り上げましょう。

順列はベルの順序です。あなたはそれらを鳴らすための最良の順序を考えています。

組み合わせはベルの選択です。あなたは鳴らす鐘を選んでいます。ベルが多すぎる場合は、最初にベルを選択してから、注文することを検討します。

これにより、おなじみのアイデンティティが生まれます。 (n P r) = (n C r) * r!

からrアイテムを注文する方法nは、最初にからrアイテムを選択しn、次にrアイテムを注文することです(r!

そして、この手段(n P r) = n! / (n-r)!(n C r) = n! / ( (n-r)! * r! )

しかし、これを永遠に覚える方法を知りたいですか?

私は第一原理思考の大ファンです。問題を理解するには、問題の核心に到達し、そこから推論します。

これを行わないと、通常、混乱の原因になります。物事がどのように機能するかを理解していない場合、概念をどこに掛ければよいかわかりません。私の精神的な枠組みは完全ではないので、それを覚えておくことにしました。

ご想像のとおり、これは理想的ではありません。ですから、時々、私はソースから物事を導き出し、物事がどのように機能するかについての直感を構築する練習に夢中になります。

今回は、順列と組み合わせの直感を構築しています。

たとえば、組み合わせの式が(n C r)である理由を知っていますか?これはどこから来たのですか?そして、なぜ階乗がここで使用されるのですか?

ソースから始めましょう。階乗、順列、組み合わせは、スティーブ・ジョブズとスティーブ・ウォズニアックがアップルをガレージで一緒に遊んで設立したのと同じように、一緒に遊んでいる数学者から生まれました。

Appleが本格的な収益性の高い会社になったのと同じように、単純な階乗は!、数学の全分野である組み合わせ論の原子になりました。

すべてを忘れて、下から上に考え始めましょう。

最初に知られている興味深いユースケースは、17世紀の教会からのものでした。

教会で鐘がどのように鳴っているのか疑問に思ったことはありませんか?それらを順番に「鳴らす」マシンがあります。ベルが大きすぎるので機械に切り替えました。また、たくさんの鐘があります。

人々はどのようにして彼らを鳴らすための最良の順序を見つけましたか?彼らが物事を切り替えたいと思ったらどうしますか?彼らはどうやって最高の音を見つけることができるでしょうか?各鐘楼には最大16個の鐘がありました!

ベルを鳴らす速度を変えることはできませんでした。マシンは毎秒1つのベルしか鳴らしませんでした。あなたができる唯一のことは、鐘の順番を変えることでした。したがって、この課題は最良の順序を見つけることでした。

途中で、すべての可能な注文を見つけることもできますか?すべてを試す価値があるかどうかを判断するために、考えられるすべての注文を知りたいと思います。

ベルリンガーのファビアン・ステッドマンがこの挑戦に取り組みました。

彼は2つのベルから始めました。彼がこれらの鐘を鳴らすことができるさまざまな順序は何ですか?[1]

1と2。

または

2と1。

これは理にかなっています。他に方法はありませんでした。

3つのベルでどうですか?

1、2、および3。

1、3、および2。

次に、2番目のベルから始めます。

2、1、および3。

2、3、および1。

次に、3番目のベルから始めます。

3、1、および2。

3、2、および1。

合計、6。

それから彼はこれが2つの鐘に非常に似ていることに気づきました!

彼が最初のベルを修理した場合、残りの2つのベルを注文する方法の数は常に2つでした。

彼は最初のベルをいくつの方法で修正できますか?3つのベルのいずれかが1つになる可能性があります!

さて、彼は続けました。それから彼は5つの鐘に達した。

これは彼が手で物事をするのは扱いにくいことに気づいたときです。あなたは一日にそんなに多くの時間を持っているだけです、あなたは鐘を鳴らさなければなりません、あなたはすべての可能な鐘を引き出して立ち往生することはできません。これをすばやく理解する方法はありましたか?

彼は洞察に戻った。

彼が5つのベルを持っていて、最初のベルを修正した場合、彼がしなければならなかったのは、4つのベルを注文する方法を理解することだけでした。

4つの鐘のために?さて、彼が4つのベルを持っていて、最初のベルを修正した場合、彼がしなければならなかったのは、3つのベルを注文する方法を理解することだけでした。

そして彼はこれを行う方法を知っていました!

したがって、5つのベルの注文= 5 * 4つのベルの注文。

4つのベルの注文= 4 * 3つのベルの注文

3つのベルの注文= 3 * 2つのベルの注文。

..パターンが見えますね。

おもしろ情報:これは、再帰と呼ばれるプログラミング手法の鍵です。

彼もそうしました。しかし、彼の近くに誰もこれを発見していなかったので、彼ははるかに長くかかりました。[2]

したがって、彼は5つのベルの順序= 5 * 4 * 3 * 2 * 1

この注文式は、1808年に階乗として知られるようになりました。

階乗表記をベースと考えていますが、名前がつくずっと前から存在していました。フランスの数学者クリスチャン・クランプがそれが階乗と名付けたのは、それがいくつかの場所で使用されていることに気づいたときだけでした。

このベルの順序は、順列と呼ばれます。

順列はアイテムの順序です。

何かを学ぶときは、いろいろな角度から見て理解を深めるのがいいと思います。

問題をベルの数を減らすことなく、上記の式を直接導出しようとするとどうなりますか?

5つのスペースがありますよね?

最初のベルを選ぶ方法はいくつありますか?5、それは私たちが持っている鐘の数だからです。

2番目のベル?さて、最初の位置に置いたときにベルを1つ使い切ったので、残りのベルは4つです。

3番目のベル?さて、最初の2つを選択したので、選択できるベルは3つだけです。

4番目のベル?残りのベルは2つだけなので、2つのオプションがあります。

5番目の鐘?残り1つなので、1つのオプション。

そして、私たちはそれを持っています、注文の総数は 5 * 4 * 3 * 2 * 1

したがって、最初の一般式があります。

Nアイテムを注文する方法の数はN!

順列

今、私たちは別の問題に直面しています。王はすべての教会のために新しい鐘を作るように命じました。いい人もいれば、大丈夫な人もいれば、耳が聞こえなくなる人もいます。しかし、誰もがユニークです。それぞれが独自の音を出します。素敵な鐘に囲まれた耳をつんざくような鐘は雄大に聞こえます。

しかし、私たちの鐘楼にはまだ5つの鐘があります。そのため、熟練した鐘職人が作った8つの鐘の中から最適な順序を見つける必要があります。

上記のロジックを使用して、先に進むことができます。

最初のベルには、8つのベルのいずれかを選択できます。

2番目のベルについては、残りの7つのベルのいずれかを選択できます...など。

最終的に、8 * 7 * 6 * 5 * 45つのスペースで8つのベルを注文できるようになります。

(n P r)の式バージョンに精通している場合はn! / (n-r)!、心配しないでください。すぐにそれを導き出します。

それを導き出す悪い方法の1つは、分子と分母の両方に3を掛けることです。上記の例では-

8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1=を取得し 8! / 3!ます。

しかし、これは、この式が機能する理由を理解するのに役立ちません。そこに着く前に、物事の選択、または組み合わせを見てみましょう。

組み合わせ

注文方法がわかったので、物の選び方を理解できます。

同じ問題を考えてみましょう。5つの鐘のある鐘楼があり、8つの鐘があります。ただし、現時点では、ベルの順序を理解する必要はありません(これが順列であることを忘れないでください)。

代わりに、5つの最高のベルを選択し、音楽の趣味が優れている他の人に順序を理解させます。実際には、問題をいくつかの部分に分解しています。まず、どのベルを選択するかを判断します。次に、選択したベルの注文方法を理解します。

どのように鐘を選びますか?これは、順列と組み合わせからの「組み合わせ」です。

組み合わせは選択です。あなたは選択的です。あなたは職人が作った8つの鐘から5つの鐘を選んでいます。

ベルの注文方法を知っているので、この情報を使用してベルの選択方法を理解します。不可能に聞こえますか?関係する美しい数学が見えるまで待ちます。

すべての鐘が一列に並んでいると想像してみましょう。

ベルを選択するすべての方法を見つける前に、ベルを選択する1つの方法に焦点を当てましょう。

1つの方法は、任意の5つをランダムに選択することです。これは問題の解決にはあまり役立たないので、別の方法を試してみましょう。

ベルを一列に並べて、最初の5つを選択します。これはベルを選択する1つの方法です。

最初の5つのベルの位置を切り替えても、選択は変わらないことに注意してください。5つのユニークなベルを選択する方法は同じです。

これは最後の3つのベルにも当てはまります。

さて、美しい数学のトリック-5つのベルを選択するこの1つの方法では、これらの5つのベルを正確に選択する8つのベルのすべての順序は何ですか?上の画像から、5つのベルのすべての順序(5!)と残りの3つのベルのすべての順序(3!)です。

したがって、5つのベルを選択するすべての方法に対して5! * 3!、8つのベルの()注文があります。

8つのベルの可能な注文の合計はいくつですか?8!

最初の5つのベルの選択肢ごとに5! * 3!、同じ選択肢を与える8つのベルの()注文があることを忘れないでください。

次に、最初の5つのベルを選択する方法の数に、1つの選択肢のすべての可能な注文を掛けると、注文の総数が得られます。

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! * (N-R)!、同じRアイテムを提供する注文があります。

Rアイテムを選択するすべての方法について、私たちはN! / (R! * (N-R)!)可能性を持っています。

rアイテムを選択する方法の数n(n C r) = n! / (r! * (n-r)!)

口語的には、(n C r)も発音さn choose rれます。これは、組み合わせがアイテムを選択するためのものであるという考えを固めるのに役立ちます。

順列-再考

組み合わせが完了し、ほこりを払ったら、私たちの仕事のパート2に戻りましょう。私たちの親愛なる友人は、5つのベルのすべての可能な組み合わせを考え出すことによって、最高の5つのベルを選びました。

注文数を把握して完璧なメロディーを見つけるのが今の私たちの仕事です。

しかし、これは簡単なことです。私たちはすでに5つのアイテムを注文する方法を知っています。これで5!完了です。

したがって、8つのうち5つのアイテムを並べ替える(注文する)には、最初に5つのアイテムを選択し、次に5つのアイテムを注文します。

言い換えると、

(8 P 5) = (8 C 5) * 5! 

そして、式を展開すると、 (8 P 5) = (8! / ( 5! * 3!)) * 5!

(8 P 5) = 8! / 3!

そして、適切に導き出された元の式に完全に到達しました。

rアイテムを注文する方法の数n(n P r) = n! / (n-r)!

順列と組み合わせの違い

これにより、順列と組み合わせの違いが明確になることを願っています。

順列は順序であり、組み合わせは選択です。

N個の要素を注文するために、答えを理解するための2つの直感的な方法を見つけました。どちらも答えにつながります、N!

8つの要素から5つを並べ替えるには、最初に5つの要素を選択してから、それらを並べ替える必要があります。を使用して選択し(8 C 5)、を使用して5を注文し5!ます。

そして、選択するための直感RのうちN(すべての順序を考え出すさN!)と第1の順序で割るRと、最後はN-R同じ(残っているR!(N-R)!)。

そして、順列と組み合わせについてはこれですべてです。

すべての高度な順列と組み合わせは、これをベースとして使用します。交換との組み合わせ?同じ考え。同一アイテムの順列?同じ考えですが、一部のアイテムは同一であるため、注文数のみが変更されます。

興味があれば、別の例で複雑なケースに入ることができます。Twitterで教えてください。

私のブログで他の投稿をチェックして、毎週のメーリングリストに参加してください。

エンドノート

  1. これが彼が物事を理解したと私が想像する方法です。歴史の教訓としてとらえないでください。
  2. インド人は、12世紀に彼の400年前にいました。