重複組合せ nHr

スポンサーリンク
赤玉,\ 青玉,\ 黒玉から重複を許して5個の玉を取り出す組合せは何通り あるか.\ ただし,\ 1個も取り出されない色の玉があってもよいとする. 異なる3種類のものから, 重複を許して} 5個取る組合せの総数である.  重複組合せは,\ 次のような考え方で,\ 同じものを含む順列に帰着させる.  左のように,\ 5個の玉を○と考えて横1列に並べ,\ 仕切りを2本入れる.  結局,\ ○5個と仕切り2本の並びは,\ 玉の個数の組合せと1対1で対応する.  求める組合せの総数は,\ ○5個と仕切り2本の計7つの順列}に等しい. とにかく,\ {○と仕切りの並びに帰着させる}考え方を習得しよう. 本問の場合,\ ○5個を仕切り2本で分けた後で色をつけると考える. 例えば,\ 「○|○○|○○」は,\ 「赤1,\ 青2,\ 黒2」のみを意味する. 逆に,\ 「赤1,\ 青2,\ 黒2」は,\ 「○|○○|○○」とただ1通りに表せる. よって,\ 「○|○○|○○」と「赤1,\ 青2,\ 黒2」は{1対1に対応}している. 場合の数分野では,\ 総数さえ求めることができれば,\ 考え方は自由である. そして,\ {1対1に対応している複数の事柄の総数はそれぞれ同じ}である. ならば,\ より考えやすい事柄に帰着させて総数を求めればよい. 重複組合せにおいては,\ ○と|の並びに帰着させて考えるのが普通である. さらに,\ ○と|の並びの総数は,\ {同じものを含む順列の総数}である. ○5個と|\ 2本の並びならば,\ 階乗を用いて\ {7!}{5!2!}\ として求めることができる. これでも全く問題ないが,\ 重複組合せはC nrで計算するのが一般的である. その場合,\ 7つの位置\ □□□□□□□\ に○5個と|\ 2本を入れると考えればよい. |\ 2本の位置を選べば,\ ○5個の位置は自動的に決まるから,\ C72\ である. なお,\ ○5個の両端と間に|を入れると考え,\ C62とするのは間違いである. |\ 2本が同じ位置に入る場合も考慮しなければならないからである. 一般化し,\ {異なるn種類のものから重複を許してr個取る組合せの総数}を求める. {r個の○とn-1本の|の計r+n-1個の順列の総数に等しい}から {Cn+r-1}{r ○と|の並びという意味が最も重要だが,\ こうとらえるのが難しい場合も多い. よって,\ 意味を理解した上で,\ さらに\ Cn+r-1}{r}\ を公式として覚えておくのがよい. なお,\ Cn+r-1}{r}=\Kumiawase{n}{r}\ と書くこともあるが,\ あまり意味はない. ところで,\ 最短経路も同じものを含む順列に帰着させることができた. ということは,\ {重複組合せと最短経路も1対1で対応する}と考えられる. 実際に対応させてみると次のようになる. よって,\ 重複組合せを右のような最短経路の総数として求めることもできる. 場合の数分野では,\ {同じC72でも様々な意味を持たせることができる}のだ. 「異なる7個のものから2個を選ぶ」 「異なる3種類のものから重複を許して5個を選ぶ」 「○5個と|\ 2本を並べる」「横5区画,\ 縦2区画の最短経路」 他
タイトルとURLをコピーしました