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

スポンサーリンク
異なるn個のものから\underline{重複を許して}\,r個取って並べる順列の総数}}は  \zyunretu nr\,と同じく,\ 公式の正体は\bm{「積の法則」}である. \\[.2zh] 公式暗記するものではなく,\ 積の法則を適用してみるとたまたまn^r\,の形になるというだけである. \\[1zh] 異なるn個のものから1個取るときの場合の数はn通りである. \\[.2zh] よって,\ r個取って並べる順列の総数は \ \zyunretu nr\,は,\ 異なるn個から異なるr個を取り出すから,\ 常に\,n\geqq r\,であった. \\[.2zh] 重複順列n^r\,では,\ 同じものを何度でも取り出せるから,の場合もありうる. }4個の数字0,\=”” 1,\=”” 2,\=”” 3から重複を許して選んでできる5桁以下の整数の個数を求めよ.=”” \\=”” 4個の数字から重複を許して5個選んで並べればよい.}$=”” \\[.5zh]=”” 5桁以下なので,\=”” \bm{桁数で場合分け}して求める.\=”” これは\bm{互いに排反}な場合分けである.=”” \\[.2zh]=”” 例として,\=”” 3桁の整数の個数を求めてみる.=”” 百の位は1,\=”” 3の3通り,\=”” 十の位は0,\=”” 3の4通り,\=”” 一の位は0,\=”” 3の4通りである.=”” よって,\=”” \bm{積の法則}より3\times4\times4となる.\=”” 他の桁数の場合も同様である.=”” 最高位以外は,\=”” \bm{0,\=”” 3の4個から重複を許して並べる重複順列}となるわけである.=”” \\[1zh]=”” 0の扱いが少し面倒だが,\=”” 実は\bm{0をうまく利用して瞬殺する}方法がある(別解).=”” 5個の数字を並べて5桁の整数の個数を求めるとき,\=”” 最高位に0が並ぶことは許されない.=”” しかし,\=”” 本問は\bm{5桁\dot{以}\dot{下}のすべての整数の個数}を求める問題である.=”” このとき,\=”” \bm{最高位も含めてすべての桁に0,\=”” 3を並べる}と,\=”” 数字の並び方は4^5\,通りある.=”” この4^5\,通りの中には,\=”” 当然\bm{01212,\=”” 00321,\=”” 00013,\=”” 00002}なども含まれる.=”” これらは,\=”” \bm{それぞれ4桁,\=”” 3桁,\=”” 2桁,\=”” 1桁の整数とみなす}ことができる.=”” 以上のような巧妙な発想により,\=”” 5桁\dot{以}\dot{下}の整数の個数をまとめて求めることができる.=”” なお,\=”” 4^5=”\bm{2^{10}=1024}\” は暗記推奨である.=”” 場合の数分野では,\=”” \bm{「対等性・対称性」}を利用できると楽になる.=”” 本問は,\=”” 一見しただけでは対等性があるようには思えない.=”” \bm{「何も存在しない桁に0が存在する」と考えると,\=”” 桁がすべて5桁で対等になる}のである.=”” 今後も,\=”” \bm{何も存在しない部分に何かが存在すると考えて対等性を得る方法は有効}である.=”” 集合$a=”\{1,\” 3,\=”” 4,\=”” 5\}$の部分集合の個数を求めよ.各要素が部分集合に属すか否かは2通りずつある}から =”” aの部分集合は,\=”” \bm{1,\=”” 5の一部の要素だけからなる集合}である.=”” 例えば,\=”” \{3\}\,\=”” \{1,\=”” 2\},\=”” \{2,\=”” 5\}\=”” などである.=”” また,\=”” 全ての要素を含む\=”” もaの部分集合の1つである.=”” さらに,\=”” 空集合\=”” \varnothing\=”” (1個の要素も含まない)もaの部分集合の1つである.=”” 次の集合が全部で何個あるかを求めることになる.=”” 上の整数の個数の問題と同様に,\=”” \bm{属さない要素の代わりに×が属すると考える.}=”” すると,\=”” 以下の例のように\bm{すべての部分集合の要素の個数が対等になる.}=”” つまり,\=”” \bm{異なる2文字○と×から重複を許して5個とって並べる重複順列}である.=”” それゆえ,\=”” 2\times2\times2\times2\times2=”2^5\,となるわけである.” 個数が対等になったことも重要だが,\=”” それよりも重要なのは\bm{「\,1対1対応」}である.=”” \bm{aの部分集合と○×5個の並びは,\=”” 漏れなく重複なく1対1で完全に対応する.}=”” あるaの部分集合は,\=”” 必ず○×5個の並びのうちのどれか1つのみと対応する.=”” 逆に,\=”” ある○×5個の並びは,\=”” 必ずaの部分集合のうちのどれか1つのみと対応する.=”” aの部分集合の個数と○×5個の並びの総数は同じである.=”” 場合の数分野の問題は,\=”” 何通りあるかを答えるのであり,\=”” その具体的な内容まで答える必要はない.=”” \bm{2つの事柄が1対1対応しているとき,\=”” 求めやすい単純な方の事柄の総数を求めれば済む.}=”” そこで,\=”” 本問では,\=”” \bm{aの部分集合と1対1対応している○×5個の並びの総数を求めた}わけである.=”” 異なる4冊の本を3人に配るとき,\=”” 何通りの配り方があるか.=”” \hspace{.5zw}ただし,\=”” 1冊ももらえない人がいてもよい.=”” \1冊の本につきその配り方が3通りずつあり,\=”” 4冊配る}から =”” 深く考えずにただ公式に当てはめて求めようとした結果,\=”” 4^3\,としてしまう誤りが非常に多い.=”” \bm{本と人の対応をきちんと意識し,\=”” 積の法則に基づいて思考すれば間違えようがない.}=”” 題意は,\=”” \bm{「\,異なる4冊の本すべてを3人に対応させること」}である.=”” ここで,\=”” \bm{本と対応しない人がいるのは\textbf{ok}だが,\=”” 人と対応しない本があるのは\textbf{ng}}である.=”” \bm{本に着目}して何通りあるかを考えると,\=”” 3\times3\times3\times3=”3^4\,となるわけである.” 異なる4冊の本\maru1,\=”” \maru2,\=”” \maru3,\=”” \maru4を\text{a君,\=”” b君,\=”” c君}に配るとすると,\=”” 対応を以下のように表せる.=”” \bm{異なる3文字\textbf{a,\=”” b,\=”” c}から重複を許して4個とって並べる重複順列}となるわけである.=”” 5人の生徒を次のように部屋割りする方法は何通りあるか.=”” 空き部屋ができないようにする.=”” \hspace{.5zw} (1)\=”” \=”” 2つの部屋\text{a,\=”” b}に入れる.      (2)\=”” 3つの部屋\text{a,\=”” c}に入れる.=”” {空き部屋があってもよい}として,\=”” 5人を2つの部屋a,\=”” bに入れる.=”” \phantom{ (1)}\=”” 1人の生徒につき2通りの入れ方があるから,\=”” 入れ方は $\textcolor{cyan}{2^5}=”32\” (通り)$=”” 5人全員が1つの部屋に入る場合は条件を満たさない.=”” まず,\=”” \bm{空き部屋がある場合の数(重複順列)を求め,\=”” 空き部屋がない場合の数を後から引く.}=”” 5人の生徒\maru1,\=”” \maru4,\=”” \maru5を部屋\text{a,\=”” b}に入れるとすると,\=”” 結局,\=”” 前問と同様,\=”” \bm{異なる文字\textbf{a,\=”” b}から重複を許して5個とって並べる重複順列}となる.=”” ただし,\=”” 本問は\textbf{空き部屋があってはならないから,\=”” aaaaa,\=”” bbbbbの並びは不可}である.=”” \end{array}}\right]$}}=”” \\\\\\\\=””  (2)\=”” \textcolor{magenta}{空き部屋があってもよい}として,\=”” 5人を3つの部屋a,\=”” cに入れる.=”” 1人の生徒につき3通りの入れ方があるから,\=”” 入れ方は $\textcolor{cyan}{3^5}=”243\” \5人全員が1つの部屋に入る}場合の数は \textcolor{red}{3通り}=”” 5人全員が2つの部屋に入る}場合の数は =”” (1)の応用で有名パターン問題の中ではあるが,\=”” 難易度がそこそこ高く初見では難しい.=”” 基本方針は(1)と同様だが,\=”” \bm{空き部屋2つの場合と1つの場合を両方引く}必要がある.=”” この2つの場合は\bm{互いに排反}である.=”” 空き部屋が2つの場合,\=”” 5人全員が1つの部屋に入ることになる.=”” これは,\=”” \bm{5人全員が\textbf{aに入る場合とbに入る場合とかcに入る場合}の3通り}がある.=”” 文字列でいえば,\=”” \text{aaaaa,\=”” bbbbb,\=”” ccccc}の3通りである.=”” 空き部屋が1つの場合,\=”” 5人全員が2つの部屋に入ることになり,\=”” さらに3つの場合に分けられる.=”” \textbf{5人全員が部屋a,\=”” bに入る}ときの場合の数は,\=”” (1)より2^5-2=”30通りである.” \textbf{5人全員が部屋b,\=”” cに入る}ときと\textbf{5人全員が部屋c,\=”” aに入る}ときも同様である.=”” この3つの場合は\bm{互いに排反}なので,\=”” 空き部屋が1つの場合の数は30+30+30=”90\” 通りである.=”” 以下のように問われた場合も同じ問題であることに気付いてほしい.=”” 「\,3文字\text{a,\=”” c}から重複を許して5個選んで並べるとき,\=”” \text{a,\=”” c}をすべて含む並べ方」<="" div="">
タイトルとURLをコピーしました