質問: (1,2,3,...,n)の置換σでσ[1]<σ[2]>...<σ[n]などとなったとき ふとした疑問です。 (1234)を並び替えて、(abcd)となったとします。 adとなるとき、 (1243),(1342),(2341)で場合の数は3 a**cc>dとなる場合の数は3 a>bbdとなる場合の数は5 a>b>cb>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となったときの、場合の数はどうなるのでしょうか?**
回答: とりあえず漸化式で表しておけば、計算は出来る。(もちろん、漸化式よりも計算に手間の掛からないスマートな方法があれば、それに越したことはない訳だけど。) やってみましょ。 "<"と">"の並びのパターン(以下、「パターン」と呼ぶ)が、「右端がsでその左にパターンpがくっついたもの」であるとき、これを psと書くことにします。例えば "a**c<"なんで、 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について取る。) ということです。**