ふとした疑問です。
(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.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について取る。)
ということです。
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)
が成り立つ。
(証明はご自分で。)
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 数学 絶対値記号がついていない不等式の計算でも場合分けをする場合はありますか? また、あるのでしたら 3 2022/05/15 20:45
- Excel(エクセル) エクセルの数式で教えてください。 2 2023/03/09 10:07
- UNIX・Linux bash環境でのエラー対応をお願い致します。 1 2022/11/26 17:41
- 数学 高一数学二次関数 画像あり 〔 チャート 89ページ 問題練習112番 〕 (2)です。 再び申し訳 2 2023/08/23 13:58
- 統計学 適合性の検定の同等性の検定 15 2022/09/24 00:36
- Excel(エクセル) 1から9まで表示するのに必要なボタン 1 2023/02/05 19:06
- 法学 全部取得条項付株式の取得と引換えにする株式の発行 申請書について 1 2022/12/21 17:32
- 数学 場合の数です. 7人の人が徒競争をした.そのうちのA君が,B君, C君の少なくとも一方より早いような 1 2022/12/31 20:08
- PHP アップロードファイルの数に応じてCSSを動的に変更したいのですが、方法がわかりません 3 2023/07/23 21:59
- 英語 数+単位で名詞を修飾する場合の表現方法について 9 2023/03/02 10:40
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
近似曲線の数式を手計算で出し...
-
Σの添え字について
-
Π←これは一体?
-
シグマの記号の読み方
-
2重ΣΣのΣ記号は交換可能でしょ...
-
Σの下にくるk=1のkってなに...
-
平面の計算方法
-
Σk(k+1) k=1 式を教えて下さい ...
-
Σの上が2n
-
Σx^2と(Σx)^2の違いは?
-
数列の問題です。次の数列の和...
-
二重和(ΣΣ)の計算方法について
-
19 Σk k=6 の和を求めろという...
-
理系数学プラチカの45(2)のまた...
-
最小二乗法における有効数字に...
-
a1=1,an+1=an+3n-1 この条...
-
分散について
-
Σのk=2
-
数学で答えを教えて欲しいので...
-
調和数列の和なんですが。。。。。
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報