- ベストアンサー
完全順列の証明
赤チャートに完全順列の証明が載っていました <証明> 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と置き換えるとはどういう事なのでしょうか? 何のために置き換えるのですか?
- vengeance
- お礼率46% (62/133)
- 数学・算数
- 回答数4
- ありがとう数3
- みんなの回答 (4)
- 専門家の回答
質問者が選んだベストアンサー
#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つを付け加えることを考えることで見えてくるように思います。
その他の回答 (3)
- zk43
- ベストアンサー率53% (253/470)
何となく、チャートの解答は分かりにくいので、私なりの 理解の説明を・・・ (オイラーの本に載っていたものです。そもそも、この 漸化式を立てて最初にこの問題を解いたのもオイラーだそうです。) 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か所あるということです。 実際例では、クラスで席替えを行ったとき、全員が元の自分 の席とは違う席になるのが完全順列です。 他にも、クラスでクリスマスプレゼントの交換を行うとき、 みんなが他の人のプレゼントをもらうというのも完全順列 です。
- banakona
- ベストアンサー率45% (222/489)
(1)について、着想のことを聞いているのなら、これは「むかし、頭のいい人が、こう置くとウマく漸化式を立てられることを発見したから」としか言いようがないでしょう。おそらく。
- naniwacchi
- ベストアンサー率47% (942/1970)
少し長くなりますが、容赦ください。 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
- 完全順列の問題
完全順列についての漸化式D ( n ) = ( n - 1 ) { D ( n - 2 ) + D ( n - 1 ) }がありますが、その証明方法がわかりません。(1)一番目がkでk番目が位置の場合(2)一番目がkで、k番目が1以外の場合 の二つに場合分けして解く方法は理解しました。 今回質問したいのは、「n枚の完全順列の個数をanとします。 (1)ここへn+1枚目の札をn+1番目に追加します。 n+1番目の札を1~n番目の札のどれか1枚と交換すれば、 n+1枚とも順番が一致しなくなります。よって、an個ある完全順列からn+1番目へはそれぞれn個ずつの完全順列が作れます。 (2)また、n個のうちk番目だけが揃ってしまっているものからも、 k番目の数とn+1番目の札を入れ替えれば、これも完全順列の1つとなります。n個のうちk番目だけが揃っている札の並べ方をbnとすると、 1~nまでのn個のbnから、それぞれ1通りずつの完全順列(の1部)が作れます。 以上のことより、次の漸化式が作れます。 an+1=nan+nbn ……(i) k番目以外はn-1個の完全順列となっているため、 bn=an-1 (n≧2)が成り立ちます。これを(i)II代入して上の漸化式が求まります。」 という解説が理解できないということです。具体的な疑問点は、(1)、(2)のせれぞれの操作は各々理解しているものの、なぜこれを足し合わせればすべて網羅したことになるのかということです。他に数えもれがありそうのように思えます。そもそもなぜこのようなやり方なのでしょうか。 ご教授のほどよろしくお願いします。
- 締切済み
- 数学・算数
- 完全順列が分かりません
完全順列を青チャートで学んでいるんですが、 公式W(n)=(n-1){W(n-1)+W(n-2)}の意味がさっぱりわかりません。 ご説明できる方、助けてください。よろしくお願いします。
- 締切済み
- 数学・算数
- 名刺順列の個数
1~nまでの数を1列に並べるときに、i番目にiという数字が来ない順列を名刺順列とか完全順列とか言います。 このような順列の個数をA(n)とすると、 A(n)=n! * Σ_{k=0}^{n} (-1)^k / k! であるそうです。この導出の仕方を教えて下さい。 ちなみに、A(n)に関する漸化式 A(n)=(n-1)*{A(n-1)+A(n-2)}, A(1)=0, A(2)=1は既に理解していますので、この漸化式の解き方でもいいです。 (この漸化式は1世代前の青チャートで見ました^^;) この式を用いると、全世界の人が名刺を1枚ずつ持ち寄ってシャッフルしたとき、自分のところに自分の名刺が戻ってくる人が1人もいない確率が1/e=36.8%もあることがわかり、なかなか神秘的なのですが。
- ベストアンサー
- 数学・算数
- 順列「n個からr個取り出す」の意味
順列の定義では「いくつかあるものの中から2つ以上取り出して1列に並べたときの並べ方のこと」だそうですが、「取り出す」というのはどういうことなのでしょうか? 異なるn 個のものからr 個とった順列の総数の公式は nPr=n(n-1)…(n-1+1) という公式ですが、では単純に、ABCDを左から右に並べ方の総数は何通りあるか、という公式はどのような式になるのでしょうか?また実際の並べ方は樹形図になると思いますが、樹形図の書き方についてもご指導いただけたら幸いです。 (当方、数字は苦手なのでできるだけ優しく教えていただけると助かります)
- ベストアンサー
- 数学・算数
- モンモール問題、完全順列、攪乱順列の拡張
モンモール問題、完全順列、攪乱順列で検索するといろいろな言い回しがあります。 1,2,3,・・・,n の数を並び替えたとき、先頭から数えた順番と数が一致するものが1つもない並べ方 n人がプレゼントをもちよって、バラバラに交換したとき、1人も自分自身の用意したプレゼントをもらわない方法 写像f:{1,2,…,n}→{1,2,…,n}ただし、単射かつ∀i∈{1,2,…,n},f(i)≠i の総数 これらの場合の数は、n!Σ[k=0,n]{(-1)^k}/k!であることはよく知られています。 そこで、拡張として次の総数を考えるとどうなるのでしょうか? n≦mとする。 写像f:{1,2,…,n}→{1,2,…,m}ただし、単射かつ∀i∈{1,2,…,n},f(i)≠i の総数 たとえば、n=3,m=4のとき、 (f(1),f(2),f(3))=(2,1,4),(2,3,1),(2,3,4),(3,1,2),(3,1,4),(3,4,1),(3,4,2),(4,1,2),(4,3,1),(4,3,2)
- ベストアンサー
- 数学・算数
- 攪乱順列とは・・・
攪乱順列とはなんでしょうか。またその個数の求め方の公式(包含と排除の原理)が解りません。 なんとなく「順列で動かないものが1つもないもの」のようなことはわかります。 包含と排除の原理 n(U)-n(P1∪P2∪P3∪・・・・∪Pn) =n(U)-Σn(Pi)+Σn(Pi∩Pj)-Σn(Pi∩Pj∩Pk)+・・・・+(-1)^n*n(P1∩P2∩P3∩・・・・∩Pn) =n!*(1-1/1!+1/2!+1/3!+・・・・・+(-1)^n*1/n!) 結論として上の最後の行だけ覚えればいいのでしょうか。i,j,kが何かもよくわかりません。1-Pバーのようなことも書いてありますがちょっと理解できません。
- ベストアンサー
- 数学・算数
- 順列の列挙の方法
順列の列挙の方法といっても辞書式順序のやつではありません。別の制約です。 グレイコードというのをご存知でしょうか。例えばビット列のグレイコードは次のようになります。 0:000 1:001 2:011 3:010 4:110 5:111 6:101 7:100 これがどんな制約を満たしているかと言うと、 1、となりのビット列に変換するには1ビット反転すれば良い。 2、すべてのビット列がちょうど1回現れる。 この2つです。グレイコードの正確な定義はさておき、とりあえず今はこれと言うことにします。 この順序でビット列を列挙する関数をC言語で書くと次のような感じになります。 f(int n) { if(n==-1)return; f(n-1); 第nビットを反転; 出力; f(n-1); } さて順列の話ですが、次のような制約を満たす順序で順列を列挙するアルゴリズムは どんな感じになるのでしょうか。 1、となりの順列に変換するには1回スワップ(2つの要素を入れ換える)すれば良い。 2、すべての順列がちょうど1回現れる。 この条件を満たすような順列の列はたくさんあると思いますが、 できるだけ法則性のあるやつ、というかプログラムに書きやすいやつを お願いします。 ビット列のアルゴリズムをちょこっと変えれば出来るかなーと思っていたのですが 数学的センスが無いせいか、苦戦しています。数学的センスのある方、ぜひご教示ねがいます。
- ベストアンサー
- 数学・算数
- 順列 初歩
以下の問題のイがわかりません。ァはわかりますが、イの解説の「そのおのおのに対し,百, 十の位は残り5個から2個を取る順列で」のところがわかりません。5個と2個はどういうことでその数字になるんでしょうか?よろしくお願いします。 問題 数字の順列の基本 6個の整数1, 2, 3, 4, 5, 6から異なる3個を取り出して1列に並べたとき,で きる3桁の整数は全部でァ個ある。このうち、偶数はイ個, 4の倍数は ウ個, 5の倍数はエ個である。 解説 偶数であるから、一の位は2, 4, 6のいずれかで 3通り そのおのおのに対し,百, 十の位は残り5個から2個を取る 順列で 5P2通り よって,求める個数は 5P2×3=5・4×3=60(個)
- ベストアンサー
- 数学・算数