重複順列 nr、部分集合の個数、部屋割り

異なるn個のものから重複を許して}r個取って並べる順列の総数}は 通常の順列と同じく,\ 単なる{「積の法則」}である. 公式として暗記するものではなく,\ 式の意味を考えて適用する. 1個取るときn通りある.\ r個取って並べる場合の数は {n n n}_{r個}=n^r} P nrは,\ 異なるn個から異なるr個を取り出すから,\ 常にn rであった. これは,\ {実物はn個しかなく,\ その中からr個取り出す}ということである. 重複順列では,\ 同じものを何度でも取り出せるから,\ ,にもなりうる. つまり,\ {実物は異なるn個のものがそれぞれ無限にある}と考えてよいのである. 例えば,\ 柿と苺を重複を許して8個取り出して並べるときの順列の総数は 2^{8} この中には,\ 柿8個を取り出す場合や苺8個を取り出す場合も含まれている. もし,\ 柿や苺の個数に制限があれば,\ その考慮が必要になり,\ 話がややこしくなる. 4個の数字0,\ 1,\ 2,\ 3から重複を許して選んでできる5桁以下の整数の$ $個数を求めよ.$ 4個の数字から重複を許して5個選んで並べればよい. 普通に考えると,\ {桁数で場合分け}することになる.\ これは{排反}な場合分けである. 例として,\ 3桁の整数の個数を求めてみる. {百}\ 1,\ 2,\ 3の3通り.  {十}\ 0,\ 1,\ 2,\ 3の4通り.  {一}\ 0,\ 1,\ 2,\ 3の4通り. 百の位の3通りのいずれに対しても十の位は4通りであるから,\ 34=12通り. さらにその12通りのいずれに対しても,\ 一の位は4通りある. 結局,\ {積の法則}より,\ 344となる.\ 他の桁数の場合も同様である. 最高位以外は,\ {0,\ 1,\ 2,\ 3の4個から重複を許して取って並べる重複順列}となる. 重複順列の部分を累乗の形で書くと,\ 本解のようになる. さて,\ 本問は非常にうまい別解がある. 5桁の整数の個数を求めるとき,\ 最高位に0が並ぶことは許されない. しかし,\ 本問は{5桁以下のすべての整数の個数}を求める問題である. このとき,\ {各桁に0,\ 1,\ 2,\ 3のすべてを入れることができると考えてよい.} こう考えて立式したものが別解の4⁵である. このとき,\ 4⁵の中には,\ {01212,\ 00321,\ 00013,\ 00001}などの並びも含まれる. これらを,\ {それぞれ4桁,\ 3桁,\ 2桁,\ 1桁の整数とみなせばよい}のである. 以上のように考えると,\ 5桁以下の整数の個数を一気に求めることができる. なお,\ 4⁵={2^{10}=102410³}\ は覚えておきたい. 場合の数分野では,\ {「対等性・対称性」}を積極的に利用すると楽になる. 本問は,\ 一見しただけでは対等性があるようには思えない. しかし,\ {「何も存在しない桁に0が存在する」と考えると,\ 桁が対等になる.} 何も存在しない部分に何かが存在すると考えて対等性を得る方法が結構使える. 集合A={1,\ 2,\ 3,\ 4,\ 5}の部分集合の個数を求めよ.$ Aの部分集合は,\ {1,\ 2,\ 3,\ 4,\ 5の一部の要素だけからなる集合}である. 例えば,\ {3}\ {1,\ 2},\ {2,\ 4,\ 5}\ などである. また,\ 全ての要素を含む\ {1,\ 2,\ 3,\ 4,\ 5}\ もAの部分集合の1つである. さらに,\ 空集合(1個の要素も含まない)もAの部分集合の1つである. よって,\ 次の集合が全部で何個あるかを求めることになる. 上の整数の個数の問題と同様に,\ {要素がない部分は×が存在すると考える.} すると,\ 次のように{すべての部分集合の要素の個数が対等になる.} 結局,\  }\ { }\ { }\ { }\ { }\ のパターンが何通りかを考えることに帰着}する. 左端の\ { }\ には,\ {1か×のどちらかが入る.}\ よって,\ 2通り. 左から2番目の\ { }\ には,\ 2か×のどちらかが入る.\ よって,\ 2通り. 他の\ { }\ も同様に2通りずつあるから,\ 結局,\ 22222となるのである. この考え方でもう1つ応用上極めて重要なポイントは{「1対1対応」}である. 例えば,\ 文字列[1×34×]は,\ 部分集合\ {1,\ 3,\ 4}\ と1対1で対応する. つまり,\ [1×34×]とあれば,\ 部分集合\ {1,\ 3,\ 4}\ のみを意味する. 逆に,\ 部分集合\ {1,\ 3,\ 4}\ には,\ [1×34×]のみが対応する. 場合の数分野の問題は,\ 何通りかさえ求めればよい. よって,\ {2つの事柄が1対1対応するとき,\ 考えやすい事柄の総数を求めれば済む.} そこで,\ 本問では,\ {部分集合と1対1対応する文字列の総数を求めた}わけである. 4冊の本を3人に配るとき,\ 何通りの配り方があるか.\ ただし,\ 1冊もも$ 1冊の本につき,\ 3通りの配り方があり,\ 4冊配るから 4³とする間違いが非常に多いので注意が必要である. 4³は,\ {3人がそれぞれ4種類の本から重複を許して取るときの場合の数}である. 1人につき,\ 4通りの選び方があるから,\ 444=4³\ となるわけである. 根本的なポイントは,\ {本と人の対応}である. 題意は,\ {「4冊すべてを3人に対応させること」}である. つまり,\ 本と対応しない人がいてもよいが,\ 人と対応しない本があってはいけない. 4³\ は,\ {「3人全員を4種の本に対応させること」}を意味する. つまり,\ 人と対応しない本があってもよいが,\ 本と対応しない人がいてはいけない. 要は,\ {全て対応させる方の1つ1つが何通りあるかを考え,\ 積の法則を用いる.} このとき,\ n^rは\ {(r個のうちの1個につきn通り)^{(r個すべて対応)を意味する. 5人の生徒を次のように部屋割りする方法は何通りあるか.$ $ただし,\ 空き部屋ができないようにする.$ $ 2つの部屋A,\ B}に入れる.$ $ 3つの部屋A,\ B,\ C}に入れる.$ 空き部屋があってもよい}とし,\ 5人を2つの部屋A,\ Bに入れる. { }1人の生徒につき,\ 2通りの入れ方があるから $2⁵}=32\ (通り)$ { }ここで,\ 5人全員が1つの部屋に入る場合は条件を満たさない. {空き部屋ができないという条件は後で処理する.} {5人全員を2つの部屋A,\ B}に対応させればよい}から,\ 重複順列になる. ただし,\ {5人全員が部屋A}に入る1通りと5人全員が部屋B}に入る1通りを引く.} {空き部屋があってもよい}とし,\ 5人を3つの部屋A,\ B,\ Cに入れる. { }1人の生徒につき,\ 3通りの入れ方があるから  本問はの応用だが,\ パターン問題の中では難易度が高いものである. と同様に,\ 空き部屋ができないという条件は後で処理する. ところが,\ 空き部屋が2つできる場合と1つできる場合があり,\ 単純ではない. 空き部屋が2つできる場合,\ 5人全員を1つの部屋に入れることになる. これは,\ {5人全員がAに入るかBに入るかCに入るかの3通り}がある. 空き部屋が1つできる場合,\ 5人全員を2つの部屋に入れることになる. 5人を2つの部屋に入れるときの場合の数は,\ の2⁵-2=30通りである. さらに,\ {どの2つの部屋に入れるかが,\ AとB,\ BとC,\ CとAの3通り}がある. よって,\ 空き部屋が1つできる場合の数は303=90\ 通りである.
タイトルとURLをコピーしました