プロが教えるわが家の防犯対策術!

ふとした疑問です。
(1234)を並び替えて、(abcd)となったとします。
a<b<c<dとなるとき、
(1234)で場合の数は1
a<b<c>dとなるとき、
(1243),(1342),(2341)で場合の数は3
a<b>c<dとなるとき、
(1324),(1423),(2314),(2413),(3412)で場合の数は5
以下、対称性を考えると、
a<b>c>dとなる場合の数は3
a>b<c<dとなる場合の数は3
a>b<c>dとなる場合の数は5
a>b>c<dとなる場合の数は3
a>b>c>dとなる場合の数は1
場合の数の合計は、4!=24です。
以上のことを一般にするとどうなるのでしょうか?
(1,2,3,4,…,n)を並び替えて、(σ[1],σ[2],…,σ[n])となったとします。
不等号が、σ[1]<σ[2]>…<σ[n]などとなったとき、
<を0、>を1とみなして、01…0を対応させます。
不等号の組の種類は、00…0から11…1までの2^(n-1)通りあります。
不等号の組が2進法表示でmとなったときの、場合の数はどうなるのでしょうか?

このQ&Aに関連する最新のQ&A

A 回答 (2件)

ANo.1の続きです。


同じ事を、行列を使ってキレーに表すこともできる。(説明のない記号はANo.1のものと同じ。)

 R(n, P)をn次元縦ベクトル
N(n,P,1)
N(n,P,2)
  :
N(n,P,n)
とする。従って、
T(n,P)=(1,1,…,1)R(n,P)
が成り立つ。

 L[n]はn+1行n列の行列であって、
0、0、0、…、0、0
1、0、0、…、0、0
1、1、0、…、0、0
:   :   :   :   : 
1、1、1、…、1、0
1、1、1、…、1、1
であるとする。
 U[n]もn+1行n列の行列であって、
1、1、1、…、1、1
0、1、1、…、1、1
0、0、1、…、1、1
:   :   :   :   : 
0、0、0、…、0、1
0、0、0、…、0、0
であるとする。

 そうすると、
R(2,<)=L[1]
R(2,>)=U[1]
R(n, P<)=L[n-1]R(n-1,P)
R(n, P>)=U[n-1]R(n-1,P)
が成り立つ。

 だから、
X(P,j)=(Pの右からj文字目が<のときL[j], >のときU[j])
とすると、
R(n, P)=X(P,n)X(P,n-1)X(P,n-2)…X(P,1)
が成り立つ。
(証明はご自分で。)
    • good
    • 0

とりあえず漸化式で表しておけば、計算は出来る。

(もちろん、漸化式よりも計算に手間の掛からないスマートな方法があれば、それに越したことはない訳だけど。)

やってみましょ。
"<"と">"の並びのパターン(以下、「パターン」と呼ぶ)が、「右端がsでその左にパターンPがくっついたもの」であるとき、これを Psと書くことにします。例えば "a<b>c<d" ならばパターンは"<><"なんで、 P=<>、s=<であって、Ps=<><

さて、1~nの数字の並びであって、右端がkであり、パターンがPであるときの場合の数をN(n,k,P)と書くことにすると、n>2について
N(n,k,P<)=ΣN(n-1,j,P) (Σは k-1≧j≧1 となるjについて取る。)
N(n,k,P>)=ΣN(n-1,j,P) (Σは k≦j≦n-1 となるjについて取る。)
ということになる。で、初期値は
N(2,1,<)=0
N(2,2,<)=1
N(2,1,>)=1
N(2,2,>)=0
(証明はご自分で。)

 欲しいのは、1~nの数字の並びであってパターンがPであるときの場合の数だから、これをT(n,P)と書くと、
T(n,P)=ΣN(n,k,P) (Σは 1≦k≦n となるkについて取る。)

 ところで、ご質問にある二進数の記法を用いるなら(<を0、>を1とみなすのだから)、
N(n,k,P)=ΣN(n-1,j,[P/2]) ([ ] は切り捨て。Σは 
P mod 2 = 0のとき、k-1≧j≧1 となるjについて取る。
P mod 2 = 1のとき、k≦j≦n-1 となるjについて取る。)
ということです。
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード