赤チャートに完全順列の証明が載っていました
<証明>
n個の数の順列1,2,・・・,nの完全順列の個数をW(n)で表す。
1,2,・・・,nの完全順列をf(1),f(2),・・・f(n)とする。
f(1)=k とするとこの完全順列は[1],[2]のどちらかである。
[1]f(k)=1 であるもの
1,k を除いた 2,・・・,k-1,k+1,・・・,n のn-2個について完全順 列であるからその個数はW(n-2)個
[2]f=(k) ではないもの
f(h)=1とするとh=kではないから,f(1)=1,f(h)=kと置き換えると,1を 除いた 2,・・・,n のn-1個について完全順列であるから,その個数
はW(n-2)個
2≦k≦nであるから,kのとりうる値は n-1通り
したがってW(n)=(n-1){W(N-1)+W(N-2)} <終>
いくつか理解できない点があります
(1)なぜf(k)=1と、f(k)=1でないものに分けて考えているのでしょうか?
(2)[2]で、f(1)=1,f(h)=kと置き換えるとはどういう事なのでしょうか?
何のために置き換えるのですか?
No.3ベストアンサー
- 回答日時:
#1です。
#2の方が着想について書かれていますが、
そのことで先の回答を書いているときに思ったことを書きます。
先の回答(質問者さんの回答でも)では、W(n)を W(n-1)と W(n-2)で表す方法を示しています。
以下では、逆に W(n)から出発して W(n+1)を表そうと考えてみます。
・すでに、W(n)で n個の数字が完全順列になっています。
そこへ数字「n+1」を付け足すことになります。
・付け足すだけだと「n+1」は n+1番目になってしまうので、どこかへ並べ直す必要があります。
そこで、先の n個のどれかと入れ換えることで実現します。(場合分けの[2])
・ところが、先の n個の並びには f(k)=kという場合がないので、その分が勘定から漏れてしまいます。
・そこで、f(k)=kとなっているときの残り n-1個に対する完全順列を考えます。(場合分けの[1])
結果、漸化式には W(n-1)も現れることになります。
この内容だと、W(n+1) = n* { W(n)+ W(n-1) }になります。
こう考えると、場合分けの[2]が一般的で、[1]が特殊な場合という感じになります。
注意深い考察がないと、なかなか導けない内容だと思います。
具体的に 3つ、4つぐらいの数字で、
さらに 1つを付け加えることを考えることで見えてくるように思います。
No.4
- 回答日時:
何となく、チャートの解答は分かりにくいので、私なりの
理解の説明を・・・
(オイラーの本に載っていたものです。そもそも、この
漸化式を立てて最初にこの問題を解いたのもオイラーだそうです。)
1が2,3,…,nのどこに行くかはn-1通りある。
1がkに行くとする。ここに、k=2,3,…,nのどれかn-1通り。
ここで、kの行先で場合分けを行う。
(1)kが1に行く場合。
後は、残りの2,3,…,k-1,k+1,…,nのn-2個で完全順列を
作れば良いので、それは、W(n-2)通りある。
(2)kが1に行かない場合
2が行ってはいけないのは2
3が行ってはいけないのは3
・・・
k-1が行ってはいけないのはk-1
kが行ってはいけないのは1
k+1が行ってはいけないのはk+1
・・・
nが行ってはいけないのはn
となり、n-1個について、それぞれ行ってはいけない
場所が1個あるので、これは、n-1個の完全順列に相当
し、W(n-1)通りある。
つまり、写像f:{2,3,…,n}→{1,2,…,k-1,k+1,…,n}
で、禁止されているのは、
f(2)=2,f(3)=3,…,f(k)=1,…,f(n)=n
のどれかが成り立つ場合であり、右側の集合で、1がkの
役割を果たしているということです。
そして、(1)と(2)は排反な事象で、kはn-1通り考えられるから、
W(n)=(n-1)W(n-2)+(n-1)W(n-1)となる。
完全順列というのは、2つの集合{a1,…,an}、{b1,…,bn}
の間の対応を考えるとき、a1→b1,…,an→bnとはならない
対応であるとも考えられます。
添え字で順番づけしていますが、要するにどの元も行っては
いけない場所が1か所あるということです。
実際例では、クラスで席替えを行ったとき、全員が元の自分
の席とは違う席になるのが完全順列です。
他にも、クラスでクリスマスプレゼントの交換を行うとき、
みんなが他の人のプレゼントをもらうというのも完全順列
です。
No.2
- 回答日時:
(1)について、着想のことを聞いているのなら、これは「むかし、頭のいい人が、こう置くとウマく漸化式を立てられることを発見したから」としか言いようがないでしょう。
おそらく。No.1
- 回答日時:
少し長くなりますが、容赦ください。
f(1)=kとしたとき、kは 2~ nまでの n-1とおりを選ぶことができます。…(★)
f(2)~f(n)に入る数を考えると、1~ k-1と k+1~ nの n-1個となります。
つまり、kはすでに 1番目となっているので、2番目以降には絶対現れません。
つまり必然的に(自動的に)、f(k)≠kになるということです。
ここで完全順列の定義に戻ってみると、
「f(m)=mとならないような並び方」を考えるということになります。
ここで、「何番目の数字」の集合と「並ぶ数字」の集合は
同じ要素が含まれていることが前提になっています。
これが重要なポイントです。
[1] f(k)=1のとき
f(2)~ f(k-1)とf(k+1)~ f(n)に入る数は、
2~ k-1と k+1~ nと要素が一致しています。
つまり、n-2個の完全順列を考えていることになります。
[2] f(k)≠1のとき、
f(h)=1とおくと
i= 1, 2, …, h, …, k, …, n
f(i)=k, □, …, 1, …, ○, …, △
という並びになります。(表にするのがわかりやすいです)
このままではうまく要素が一致しません。
ここで、この f(i)の並び方を次のように考えます。
2~ nまでの n-1個の数を完全順列で並べてから、「k」と書かれているところを「1」に入れ換えた。
先に完全順列で並べているので、f(k)=○は kではありません。
すると、最後の入れ替えは「自動的に決まる」ので、
この組合せの数は W(n-1)とおりとなります。
あとは、[1]、[2]のそれぞれの場合について、kは n-1とおりの選択が可能であることから(★印)、
W(n)=(n-1)* { W(n-2)+W(n-1) }
となります。
正直「完全順列」を知らなかったのですが、wikiなどの説明を参考にしました。
ポイントは、「要素をそろえないと完全順列として勘定できない」というところです。
わかりにくいところなどあれば、補足してください。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- Java Java 南京錠 2 2023/02/04 11:46
- 数学 【 数A 重複順列 】 問題 3種類の記号〇,△,□を重複を許して 並べる順列を作る。1個以上4個以 2 2022/07/21 14:24
- 数学 n乗はどうなったのでしょうか 1 2023/01/31 19:26
- 数学 群数列の問題がわかりません。どなたか教えてください… 【問題文】 1から順に自然数を並べて, 下のよ 2 2022/03/28 18:55
- 数学 高一数学 場合の数 画像あり 〔 チャート 267ページ 問題練習34番 〕 (2)です。 解説の右 1 2023/08/21 17:31
- Excel(エクセル) Xlookupの結果がうまくいきません。(excel2013) 2 2023/06/18 17:32
- Excel(エクセル) 結合セルのソートについて 5 2022/04/22 11:57
- 数学 高一数学 場合の数 画像あり 〔 チャート 265ページ 問題練習31番 〕 (1)です。 輪にする 6 2023/08/24 07:41
- 工学 図のように自己インダクタンスL1、L2、巻き数N1、N2、相互インダクタンスMの二つのコイル1とコイ 2 2022/10/11 13:00
- Java Java配列の問題を教えてください。 乱数で20個出力し、最大、最小、合計、平均を求め、更に昇順にソ 3 2023/07/10 18:32
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
∈と⊂の違いは何ですか?
-
集積点が、まったく分かりませ...
-
6以下の自然数全体の集合の要素...
-
数学でのセミコロンについて
-
R\\{0} って、0を除く実数って...
-
数字の上のバー
-
大学数学、集合と位相について
-
高1数学
-
閉包と集積点と内部
-
1から100までの自然数で、3,4,5...
-
∈ と ⊂ のはっきりとした違い
-
何故線型空間はあっても、非線...
-
数字は存在するのか
-
言語の無限性に関してお考えを...
-
次の説明は「急速に減少✨️しな...
-
_ a aの上に書かれている_(ア...
-
A∩BとAかつBは意味が違うのでし...
-
1桁の自然数全体を全体集合Uと...
-
数学の集合で閉じているの意味...
-
集合について。
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
∈と⊂の違いは何ですか?
-
空集合のべき集合
-
数字は存在するのか
-
数学で、数字の上にある横線の意味
-
R\\{0} って、0を除く実数って...
-
数学でのセミコロンについて
-
要素と、部分集合の違いを教え...
-
Rの半開区間(0,1]と開区間(0,1)...
-
部分が全体に等しいのが無限で...
-
数字の上のバー
-
集積点が、まったく分かりませ...
-
内包的記法と外延的記法について
-
6以下の自然数全体の集合の要素...
-
ACCESSのSQL
-
すべての自然数とすべての実数...
-
数学の集合で閉じているの意味...
-
集合の記号の読み方等について
-
∈ と ⊂ のはっきりとした違い
-
高校1年の数学Aです。 この、ピ...
-
有理数と実数とではどちらが多いか
おすすめ情報