(1,2,3,…,n)の置換σでσ[1]<σ[2]>…<σ[n]などとなったとき

質問

ふとした疑問です。
(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となったときの、場合の数はどうなるのでしょうか？

回答No.2

stomachman · ベストアンサー

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列の行列であって、
０、０、０、…、０、０
１、０、０、…、０、０
１、１、０、…、０、０
：　　　：　　　：　　　：　　　：　
１、１、１、…、１、０
１、１、１、…、１、１
であるとする。
　U[n]もn+1行n列の行列であって、
１、１、１、…、１、１
０、１、１、…、１、１
０、０、１、…、１、１
：　　　：　　　：　　　：　　　：　
０、０、０、…、０、１
０、０、０、…、０、０
であるとする。

　そうすると、
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)
が成り立つ。
（証明はご自分で。）

回答No.1

stomachman

とりあえず漸化式で表しておけば、計算は出来る。（もちろん、漸化式よりも計算に手間の掛からないスマートな方法があれば、それに越したことはない訳だけど。）

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

さて、１～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
（証明はご自分で。）

　欲しいのは、１～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について取る。）
ということです。