場合の数 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 · ベストアンサー

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

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

>(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

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! 通り

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