陥没地帯 (276) - ノリの悪い日記

$2003$ 年の一橋大の問題. 組合せの数
${}_n\mathrm{C}_m$ というのは, もちろん $n$ 個の要素をもつ集合において $m$ 個の要素をもつ部分集合の個数のことをいう. また, ${}_n\mathrm{C}_m$ は, $m$ 個の要素をもつ集合 $X$ から, $n$ 個の要素をもつ集合 $Y$ (要素の間に全順序が定められているとする) への狭義増加関数 (真に増加している関数) の個数にも等しい. なぜなら, $Y$ の $m$ 個の要素をもつ部分集合をひとつ定めれば, $X$ から $Y$ への狭義増加関数がひとつ定まり, 逆もまたそうだからである. (狭義増加関数ならば, 単射なので, $m \leq n$ である.)

別の言い方をすれば, $X$ から $m$ 個のボールを投げて, いずれのボールも $Y$ の $n$ 個の箱のいずれかに入るのが写像だが, どの箱にもたかだか $1$ 個 ( $0$ または $1$ 個) しかボールが入らないときが単射である. 何かが同じであるというためには, ある基準がいるのであって, ボールを区別せずに, ボールが $1$ 個入っている箱 ( $Y$ の要素で箱はひとつひとつ識別されている) の集合が一致すれば, 写像は同じものとみなすという考え方も存在する. この場合の異なる写像の個数が, ${}_n\mathrm{C}_m$ であり, 一方, ボールを識別して, ボールの来た先が違っていれば, ボールが入っている箱 (要素) の集合が一致していても違う写像とみなすという考え方に立てば, 異なる写像の個数は ${}_n\mathrm{P}_m$ となる.

場合の数や確率の応用問題では, 数え上げを行う上で, どこまでを「同じ」とみなすのかは, 明示されないことがあるし, 「同じ」であることに絶対的な基準があるわけでもないので, 注意する必要がある.

【問】
f:id:noriharu-katakura:20211113153259j:plain

【解】

$(1)$ $(a_1, a_2)$ が $1 \leq a_1 < a_2 \leq n$ となる数字の箱の作り方は, ${}_n\mathrm{C}_2$ 通りだが, それぞれの数字の箱には, 箱と同じ番号で $2$ 枚の異なるカードの内のどちらかを入れるから, ${}_n\mathrm{C}_2 \times 2^2$ 通りのカードの並べ方がある. したがって, 求める確率は,

$\displaystyle{1- \frac{{}_n\mathrm{C}_2 \times 4}{{}_{2n}\mathrm{P}_2} \\= 1- \frac{2n(n-1)}{2n(2n-1)} \\= \frac{n}{2n-1} }$

である.

$(2)$ $1 \leq a_1 < a_2< \cdots < a_n \leq n$ だから, $i$ を $n$ 以下の自然数とすると, $a_i = i$ となり, 数字の箱の作り方は, $(1, 2, \cdots, n)$ の一通りしかない. それぞれの数字の箱には, 箱と同じ番号で, $2$ 枚の異なるカードの内のどちらかを入れるからカードの並べ方は, $2^n$ 通りである. したがって求める確率は,

$\displaystyle{\frac{2^n}{{}_{2n}\mathrm{P}_n}= \frac{2^n (2n-n)!}{(2n)!}= \frac{2^n n!}{(2n)!} }$

である.

$(3)$
問題の条件は, $1 \leq a_1 < a_2< \cdots < a_m \leq n$ をみたしていることと同値である. $(a_1, a_2, \cdots, a_n)$ となる数字の箱の作り方は, ${}_n\mathrm{C}_m$ 通りある. それぞれの数字の箱には, 箱と同じ番号で $2$ 枚の異なるカードの内のどちらかを入れるからカードの並べ方は, $2^m \cdot {}_n\mathrm{C}_m$ 通りである. したがって求める確率は,

$\displaystyle{\frac{ 2^m \cdot {}_n\mathrm{C}_m }{{}_{2n}\mathrm{P}_m} = \frac{2^m n! (2n-m)!}{(2n)!m!(n-m)!} }$

である.//