![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67)
ふとした疑問です。
(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ベストアンサー
- 回答日時:
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)
が成り立つ。
(証明はご自分で。)
No.1
- 回答日時:
とりあえず漸化式で表しておけば、計算は出来る。
(もちろん、漸化式よりも計算に手間の掛からないスマートな方法があれば、それに越したことはない訳だけど。)やってみましょ。
"<"と">"の並びのパターン(以下、「パターン」と呼ぶ)が、「右端が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について取る。)
ということです。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
三乗の公式
-
Π←これは一体?
-
Σの上が2n
-
近似曲線の数式を手計算で出し...
-
シグマの記号の読み方
-
Σの添え字について
-
「f(z)=1/(z^2-1)に関して ロー...
-
Σk(k+1) k=1 式を教えて下さい ...
-
(1+x+x2乗)7乗の展開式におけ...
-
漸化式
-
x(π−x)をフーリエ級数展開して...
-
期待値と無限等比級数の融合問...
-
階乗和
-
偏差平方和の式
-
2重ΣΣのΣ記号は交換可能でしょ...
-
数学です。 Σn=1〜∞ 1/(2n+1)(2...
-
二重和(ΣΣ)の計算方法について
-
2変数関数の近似曲線
-
参考書によると、 n Σ(2n-2k+1)...
-
19 Σk k=6 の和を求めろという...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
Π←これは一体?
-
Σの添え字について
-
近似曲線の数式を手計算で出し...
-
シグマの記号の読み方
-
Σk(k+1) k=1 式を教えて下さい ...
-
Σの上が2n
-
平面の計算方法
-
最小二乗法における有効数字に...
-
x(π−x)をフーリエ級数展開して...
-
数列の問題です。次の数列の和...
-
三乗の公式
-
a1=1,an+1=an+3n-1 この条...
-
Σと∫って入れ替えできるんです...
-
二重和(ΣΣ)の計算方法について
-
(sinx)^3のテイラー展開を項別...
-
Σ計算について
-
数列の和について
-
画像の説明のタイトルの次の文...
-
Σx^2と(Σx)^2の違いは?
-
Z=e^(x+y)について2変数のマク...
おすすめ情報