ノリの悪い日記

古今東西の映画、ポピュラー音楽、その他をいまここに交錯させながら随想します。

陥没地帯 (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 だから,  in 以下の自然数とすると,  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)!}
}

である.//