 | まず1,...,nなるn個の数字からk個(k=1,…,n)を取り出して作る組み合わせ１つに対して単調増加、単調減少となるものがそれぞれ1つ対応しているに注意します。
(1)
求める総数は1,...,n-1なるn-1個の数字からk個(k=1,2,..,n-2)を取り出してできる組み合わせの総数に等しくなりますので、その数Nは
N=2∑[k=1～n-2](n-1)Ck=2^(n-1)-2
(2)
横軸に問題の順列の順番を、縦軸に順列を作る数字の値をとると、順列に対応する点を順番の増加順に結んでできる折れ線には数字の値がnである点(Pとします)を頂点とする山と、それ以外のある点(この点をQとします)を底とする谷が1つづつできます。
今、山が谷よりも左側にあるものとして、
山の左側の勾配がp個(p=1,2,..,n-3)の点、
山の右側の勾配がq個(q=0,1,…,n-(p+1)-2)の点
(いずれもP,Qは含まないものとします)
で構成されているものとすると
このような順列の数は
{(n-1)Cp}{(n-1-p-1)Cq}[個]
順列の並びの順序を左右逆転させることを考えると、求める順列の総数Mは
M=2∑[p=1～n-3]∑[q=0～n-p-3]{(n-1)Cp}{(n-p-2)}Cq
=2∑[p=1～n-3]{(n-1)Cp}{2^(n-p-2)-1}
=∑[p=1～n-3]{(n-1)Cp}{2^{(n-1)-p}-2}
=3^(n-1)-2^(n-1)-{(n-1)C(n-2)}2^{(n-1)-(n-2)}-1
-2{2^(n-1)-1-(n-1)C(n-2)-1}
=3^(n-1)-2^(n-1)-2(n-1)-1-{2^n-4-2(n-1)}
=3^(n-1)-3・2^(n-1)+3[個]
|
