• 締切済み

対称群(置換群)の転倒数の母関数、期待値、分散

n個の整数{1,2,…,n}からなる順列 があるとき、その順列の総数はnの階乗 n!個存在する。 そのひとつを(a_1,a_2,…,a_n)で表す。 この順列において i < j かつa_i > a_j の関係にあるとき a_iとa_jとの間に転倒があるという。 この転倒の総数を転倒数という。 n!個の順列のうち転倒数がkの順列の場合の数は、 1(1+q)(1+q+q^2)…(1+q+q^2+…+q^(n-1))　を展開したときのq^kの係数に等しい。 これがどうしてなのか教えていただけないでしょうか? また、転倒数の期待値、分散もご存知であればどうか教えてください。

  • jlglg
  • お礼率34% (133/384)

みんなの回答

  • nag0720
  • ベストアンサー率58% (1093/1860)
回答No.2

どうしてなのかと言われてもそうなっているのだからしょうがない。 証明したいのなら、帰納法を使えば可能でしょう。 n個の整数{1,2,…,n}からなる、ある順列の転倒数がkのとき、整数(n+1)を追加する箇所によって転倒数がk,k+1,k+2,・・・,k+nとなる(n+1)種類の順列ができます。 これを利用すれば帰納法で証明できるでしょう。

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

それぞれの因子が何を表しているのかを考えてください. そして母関数がわかれば期待値や分散は計算できますよね.

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • 組み合わせ数学

    任意の正整数n,kに対し, p*(n,k)=p*(n-k,k)+p*(n,k-1) n>kのとき p*(n,k)=1+(n,k-1) n=kのとき p*(n,k)=p*(n,n) n<kのとき が成り立つ 任意の正整数n,kに対し,p*(n,1)=p*(1,k)=1が成り立つ これらの条件でp(8)の値を求めたいのですが、全く分かりません。計算過程も含めて詳しく教えてください。例えばnは正整数とする 総和がnとなるような正整数の組をnの分割と呼ぶ。また、nの分割の総数をnの分割数といい、p(n)で表すということです そして、nの分割のうち、ちょうどk個の正整数による組をnのk個分割、高々k個の正整数による組をnの高々k個分割と呼ぶこととし、それぞれの総数をp(n,k)およびp*(n,k)で表す。 また、nの分割のうち、最大値がkである組をnの最大値k分割、最大値がk以下である組をnの最大値k以下分割と呼ぶこととし、それぞれの総数をq(n,k)およびq*(n,k)で表す。ということらしいです。長くなってすみませんお願いします。お願いします。

  • 二項定理の多項定理

    二項定理を使った問題の解法を教えてください。 多項定理です。 「同じものがあるときの順列」で考えると (a+b+c)^n を展開したときの，a^p b^q c^r の項は， a を p 個，b を q 個，c を r 個 選んでかけ合わせたものである。 ーーここまでは理解できたのですがーー 上記より、それらを並べ替えてできる順列の 総 数 が 項の係数になる。 というのが理解できません。 教えてくださいｍ(＿)ｍ cf. n ! ────通り p !q !r !

  • 第二種スターリング数の母関数の組合せ論・計数子による解釈

    1,2,3,…,nのn個の数字を、k種類の区別のないグループに分ける場合の数を、第二種スターリング数と言って、ここでは、S(n,k) と書きます。 すると、1,2,3,…,nのn個の数字を、k種類の区別のあるグループに分ける場合の数は、k!*S(n,k) となります。 これは、f:{1,2,…,n}→{1,2,…,k}の全射の場合の数でもあります。 ところで、 Σ[n=0,∞] k!*S(n,k)x^n/n! = (e^x - 1)^k という公式があります。 右辺のx^n/n!の係数は、1,2,…,kの数字を重複を許してn個並べて、全種類の数字が少なくとも1回は使われているという条件をつけたときの場合の数とみなせます。（指数型計数子） ここまではいいのですが、似たような公式 Σ[n=0,∞] S(n,k)x^n = x^k/(1-x)(1-2x)…(1-kx) を計数子によって解釈する方法があれば、どうか教えてください。

  • 対称群の交換子群

    教えていただけると嬉しいです。 ｎ次対称群Snの交換子群D(Sn)はｎ次交代群Anである、ということの証明を読んでいて、D(Sn)⊂Anは理解しました。が、An⊂D(Sn)の証明のところがわかりません。 「1≦i＜j＜k≦nとすると、[(i,j),(i,k)]＝(i,j,k)であり、Anは３文字の巡回置換によって生成されるからAn⊂D(Sn)である。」 とあるのですが、「生成されるから」のところまではすべてわかります。ですが、なぜここから結論が出てくるのかがわかりません。

  • 四元数群

    四元数群Q={±1, ±i, ±j, ±k}について、Qから上への準同型写像φ:Q→Kをつくることのできる群Kは同型を除いて2つある。2通りの場合についてそれぞれKの乗積表と、準同型写像φ:Q→Kの例を少なくとも一つ与えよ。 という問題です。四元数群は、通常のi^2=j^2=k^2=-1をみたすものです。 同型でないもので全射、かつ準同型写像なのですが、うまく例を与えることができません。どなたか知恵を貸していただけないでしょうか。。

  • 完全順列の漸化式

    完全順列をウィキペディアで調べると以下のように漸化式について解説していました。 モンモール数Ａ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の場合に簡単化してもいまひとつ 　ピンときません。 　平たく云って、この漸化式はどのような考え方に基づいて成り立って 　いるのでしょうか。

  • モンモール問題、完全順列、攪乱順列の拡張

    モンモール問題、完全順列、攪乱順列で検索するといろいろな言い回しがあります。 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)

  • 完全順列(モンモール数)の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項間漸化式を元に代数的に変形して示します。 しかし、これを直接に組合せ論的解釈したいのです。 いろいろ考えても、いろいろ調べてもわかりません。 興味ある方はどうか教えてください。

  • 二次形式のモーメント母関数について

    二次形式のモーメント母関数について 閲覧ありがとうございます。 確率統計について分からない問題があるので教えてください。 問 X[1],X[2],...,X[n]は独立で共通な標準正規分布N(0,1)に従う確率変数である。 X = (X[1],X[2],...,X[n])'とおく。 (’はベクトル・行列の転置を表す。) A=(a[i][j])をn次の実対称行列とし、固有値全体を{λ[1],λ[2],...,λ[n]} (λ[1]≧λ[2]≧...≧λ[n])　とする。 Aを係数行列にもつXに関する二次形式 Z = X' A X =Σ[n,i,j=1] a[i,j]X[i]X[j] このとき以下について答えよ (1)Mz(t)のモーメント関数を求めよ。 (2)Zの確率分布が自由度k (1≦k≦n)のカイ二乗分布ならば λ[1]=...=λ[n]=1, 　λ[k+1]=...=λ[n]=0であることを証明せよ。 (1)については全然わかりません。。。すいません。 (2)について n次の直交行列をU,固有値を対角成分とする行列をLとしてA=U' L Uと分解します。 Y=UXとして、　Z=X' A X =Y' L Yとかける。 条件よりYは確率分布N(0,1)に従う確率分布である。 ここまで考えましたが後がわかりません。 よろしくお願いします。

  • 組合せ

    2個の整数m,n(m≧n)をキーボートから受け取って、m個の相異なる物の中からn個取り出す組合せの数を計算するプログラムを作っているんですが、下のプログラムだと、13の階乗でオーバーフローしてしまいました。combination関数を使わずに、13の階乗を計算したいのですが…。 13!/(k!(13-k)!)で、13!でオーバーフローなので、13!/k!=(k+1)×…×13を計算すればいいのは分かるのですが、どういう関数を定義すればいいのかわかりません。 ヒントやアドバイス頂けると、助かります。 よろしくお願いします。 #include <stdio.h> void main(void) {long m,n; long fact(long); while(scanf("%ld,%ld",&m,&n)!=EOF) printf("comb(%ld,%ld)=%ld\n",m,n, fact(m)/(fact(n)*fact(m-n))); } long fact(long k) {long i,f; f=1; for (i=1;i<=k;i=i+1) f=f*i; return(f); }

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する