- ベストアンサー
円順列
1～nの数字を書いたカードがそれぞれm枚ずつ、計nm枚ある。 これを1列に並べる順列の数F(n,m)は、F(n,m)=(nm)!/(m!)^n では、このm枚を円環状に並べる円順列の数G(n,m)はどうなるでしょうか？ m=1なら、 G(n,1)=F(n,1)/n=(n-1)! m=p (pは素数)なら、 G(n,p)=(F(n,p)-F(n,1))/(np)+F(n,1)/n =((np)!/(p!)^n-n!)/(np)+(n-1)! mが任意の自然数のとき、G(n,m)をnとmの式、または漸化式で表すことは可能でしょうか？ ちなみに、n,mが小さい数値のときのG(n,m)の値は次のようになっています。 G(2,2)=2 G(2,3)=4 G(2,4)=10 G(2,5)=26 G(2,6)=80 G(2,7)=246 G(2,8)=810 G(2,9)=2704 G(2,10)=9252 G(3,2)=16 G(3,3)=188 G(3,4)=2896 G(3,5)=50452 G(4,2)=318 G(4,3)=30804 G(5,2)=11352
- nag0720
- お礼率92% (26/28)
- 数学・算数
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
同じものを含む円順列、で検索してはいかがでしょう。 もっと一般には、ポリアの定理、で検索してはいかがでしょう。
関連するQ&A
- 完全順列の漸化式
完全順列をウィキペディアで調べると以下のように漸化式について解説していました。 モンモール数Ａnを与える漸化式を考える。 n番目に置く数の選び方は1からn-1までの(n-1)通りである。ここで選んだ数をiとする。 次にi番目がnかどうかで場合分けをする。 ｉ番目がnであれば、i番目に置かれたnとn番目に置かれたiを除く（n-2）個の数の並べ方の 総数は、(n-2)個の数による完全順列の数、すなわちA(n-2)に等しい。 i番目がnでない場合は、n番目に置かれたiを除く(n-1)個の数の並べ方の総数は、(n-1)個 の数による完全順列の数、すなわちA(n-1)となる。 以上をまとめると下の漸化式が得られる。 An=(n-1)・{A(n-1)＋A(n-2)｝ n>=3 これでは訳が解らないのでn=4の場合を考えます。 4番目に置く数の選び方は1から(4-1)までの3通りである。ここで選んだ数ｉは3である。 次に3番目(i番目)が4(n)かどうかで場合分けをする。 3番目(i番目)が4（n）であれば3(i)番目に置かれた4（n）と4(n)番目に置かれた3(i)を除く(4-2）個 の数の並べ方の総数は、(4-2)個の数による完全順列の数、すなわちA(4-2)に等しい。 3(i)番目が4(n)でない場合は4(n)番目に置かれた3(i)を除く(4-1)個の数の並べ方の総数は (4-1)個の数による完全順列の数、すなわちA(4-1)となる。 A4=(4-1)・{A(4-1)＋A(4-2)}=3×(A3＋A2) 両辺をそれぞれ自力で強引に調べると確かに両辺とも9になっていて この漸化式は正しいようですが、n=4の場合に簡単化してもいまひとつ ピンときません。 平たく云って、この漸化式はどのような考え方に基づいて成り立って いるのでしょうか。
- ベストアンサー
- 数学・算数
- 名刺順列の個数
１～ｎまでの数を１列に並べるときに、ｉ番目にｉという数字が来ない順列を名刺順列とか完全順列とか言います。 このような順列の個数を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/e=36.8%もあることがわかり、なかなか神秘的なのですが。
- ベストアンサー
- 数学・算数
- 完全順列の問題
完全順列についての漸化式D ( n ) = ( n - 1 ) { D ( n - 2 ) + D ( n - 1 ) }がありますが、その証明方法がわかりません。(1)一番目がkでｋ番目が位置の場合(2)一番目がｋで、ｋ番目が１以外の場合 の二つに場合分けして解く方法は理解しました。 今回質問したいのは、「ｎ枚の完全順列の個数をａnとします。 (1)ここへn+1枚目の札をn+1番目に追加します。 n+1番目の札を１～ｎ番目の札のどれか１枚と交換すれば、 ｎ＋１枚とも順番が一致しなくなります。よって、ａn個ある完全順列からｎ＋１番目へはそれぞれｎ個ずつの完全順列が作れます。 (2)また、ｎ個のうちｋ番目だけが揃ってしまっているものからも、 ｋ番目の数とｎ＋１番目の札を入れ替えれば、これも完全順列の１つとなります。ｎ個のうちｋ番目だけが揃っている札の並べ方をｂnとすると、 １～ｎまでのｎ個のｂnから、それぞれ１通りずつの完全順列(の１部)が作れます。 以上のことより、次の漸化式が作れます。 ａn+1＝ｎａn＋ｎｂn ……(i) ｋ番目以外はｎ－１個の完全順列となっているため、 ｂn＝ａn-1 (ｎ≧２)が成り立ちます。これを（i）II代入して上の漸化式が求まります。」 という解説が理解できないということです。具体的な疑問点は、(1)、(2)のせれぞれの操作は各々理解しているものの、なぜこれを足し合わせればすべて網羅したことになるのかということです。他に数えもれがありそうのように思えます。そもそもなぜこのようなやり方なのでしょうか。 ご教授のほどよろしくお願いします。
- 締切済み
- 数学・算数
- 完全順列の証明
赤チャートに完全順列の証明が載っていました ＜証明＞ 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と置き換えるとはどういう事なのでしょうか？ 何のために置き換えるのですか？
- ベストアンサー
- 数学・算数
- 完全順列(モンモール数)の2項間漸化式の組合せ論的解釈
http://ja.wikipedia.org/wiki/%E5%AE%8C%E5%85%A8%E9%A0%86%E5%88%97 より、 完全順列とは、整数{1,2,3,…,n}を要素とする順列において、i番目(i≦n)がiでない順列のことであり、その総数をモンモール数という。 その総数をa[n]とすると、上記のサイトに、3項間漸化式 a[n]=(n-1)(a[n-1]+a[n-2]) の組合せ論的解釈が書かれています。 また、2項間漸化式 a[n]=n*a[n-1]+(-1)^n が成り立つのですが、普通は3項間漸化式を元に代数的に変形して示します。 しかし、これを直接に組合せ論的解釈したいのです。 いろいろ考えても、いろいろ調べてもわかりません。 興味ある方はどうか教えてください。
- 締切済み
- 数学・算数
- モンモール問題、完全順列、攪乱順列の拡張
モンモール問題、完全順列、攪乱順列で検索するといろいろな言い回しがあります。 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)
- ベストアンサー
- 数学・算数
- VBAで順列を表現する方法
VBAによる順列の表記の仕方を教えてほしいです。 例えばn個の数値から2つの要素を並べる順列nP2の場合、1番目に選んだ数値が2番目の順列の選択候補から外れ、1番目と2番目の数値を順列として表示するようなVBAを組みたいです。 つまり同じ数字を2回以上使わないnPm(m≧2)という順列を作成したいのです。 どのようなプログラムを組めばよいか教えてください。
- ベストアンサー
- オフィス系ソフト
- 場合の数 漸化式
場合の数 漸化式 nを正の整数とする。1からnまでの整数が書かれたカードが各2枚ずつ計2n枚あり，これらをすべて使い2枚ずつの組を作ったとき，すべての組で次の条件を満たす確率をP[n]とする。 条件：組になったカードに書かれた数a，bについて，|a-b|≦1 が成り立つ。 この問題に対し，条件を満たす組み合わせ数をA[n]とすれば， P[n]=A[n]/{(2n)!/2^n} で求めることができると考えました。 (組み合わせの総数について，同じものを含む順列と考え，並べた後2枚おきに区切りを入れれば良いと考えました) しかし，肝心のA[n]が分からないため解答を見たところ， A[n+2]=A[n+1]+2A[n] という漸化式がたてられていました。 この漸化式はどのように立式出来るのでしょうか？どなたか解説お願いします。
- ベストアンサー
- 数学・算数
- 状況の変化をある関数で表す問題（順列）
「m個所の送信施設を持つA国から、n個所の受信施設を持つB国へ信号を送る。A国の各施設はB国の施設の中のただ1個所に必ず信号を送るものとし、その送受信は一斉に行われる。いまm≧nとし、B国のどの受信施設もA国のどこかの送信施設からの信号を少なくとも1つは受信する場合を考える。このような送信パターンの数をｆ(m,n)と表す。以下m,nを変化させて考えるとき、次の問いに答えよ。 (1)n=3のときf(m,３)をｍを用いて表せ。 (2)f(m+1,n)をf(m,n)およびf(m,n-1)を用いて表せ。ただしn≧２とする。 (3)f(m+1,m)をmを用いて表せ。」 という長い問題に取り組んでいます (1)すら解けなくて困っています。 ｍ＝３のときをまず考えました。ｍの3箇所からの送信がnの3箇所に受信されるので、ｍの3箇所の並び替えで3P3＝３！＝６ ｍ＝４のときはｍの4箇所のうち3箇所を選んで並び替えて残り1箇所がｎの3箇所のうちどれかに送信されるので4P3＊３＝72 という考え方でいいのでしょうか？ 順列や組み合わせや確率がかなり苦手なので全く自信がありません。 (2)(3)は(1)がよくわからないのでできません。 教えていただければ幸いです。 宜しくお願いいたします
- ベストアンサー
- 数学・算数
お礼
ありがとうございます。 ポリアの定理は、知識不足で理解できませんでしたが、 「同じものを含む円順列」で検索したら、より一般化した問題の定理がありました。 これでなんとか解決できそうです。