場合の数 a1<a2<a3・・・・ b1<b2<b3<・・

a1,a2,a3,・・・・an；b1,b2,b3,・・・bn
は1,2,・・・2nを任意に並べ替えたものである。
このうち、次の（ア）～（ウ）を満たすものの総数をｐnとする。
(ア)a1<a2<a3・・・<an
(イ)b1<b2<b3・・・<bn
(ウ)aj＜bj（j＝1,2・・・n）

(1)p2、p3、p4、p5を求めよ
(2)pnをｎを用いて表せ


この問題に取り組んでいるのですが、うまく数える方法あるでしょうか？
数え上げてみたのですが、自信が全くないです・・・
p2＝２
p3＝５
p4＝15

No.2 ベストアンサー 回答者： cncpt 回答日時： 2007/01/23 23:35

>この問題に取り組んでいるのですが、うまく数える方法あるでしょうか？

うまく数える方法があります。
「カタラン数」というキーワードで検索してみてください。

>(1)p2、p3、p4、p5を求めよ
p2=2, p3=5, p4=14, p5=42

>(2)pnをｎを用いて表せ
pn=(2n)!/((n!)^2*(n+1))

No.1 回答者： koko_u 回答日時： 2007/01/23 23:27

a_1 < b_1 < b_2 ... < b_n より a_1 = 1

a_2 < b_2 < ... < b_n より a_2 <= 3 (a_2 より大きい数が (n-2)+(n-1)個ある)
a_3 < b_3 < ... < b_n より a_3 <= 5

というわけで a_i <= 2i-1

逆に {1, 2, ... , 2n} から a_i を 2i-1 以下となるよう、a_1 < a_2 < ... と取って、残りを小さい順に b_i とすれば a_i < b_i (証明略)

というわけで a_1 の選び方は 1 通り、a_2 の選び方は 3-1=2通り、... a_i の選び方は (2i-1)-(i-1)=i通り

結局総数は 1×2×... ×n = n! 通り

#たまには自信のない回答もしてみたり。