連続条件のある重複順列

スポンサーリンク
○と●を重複を許して合計7個並べるとき,\ 次の条件を満たす順列は何通りあるか. \\[1zh] \hspace{.5zw} (1)\ \ ○が3個以上連続して並ぶ部分がある. \\[.8zh] \hspace{.5zw} (2)\ \ ○が3個連続して並ぶ部分があるが,\ 4個連続して並ぶ部分はない. \\[.8zh] \hspace{.5zw} (3)\ \ ○が2個連続して並ぶ部分があるが,\ 3個連続して並ぶ部分はない. \\[.8zh] \hspace{.5zw} (4)\ \ ○が2個以上連続して並ぶ部分がない. \\ 連続条件のある重複順列}}}} \.{最}\.{初}\.{の}連続がどこから始まるかを基準にする}}と\textbf{\textcolor{purple}{排反}}な場合分けになる.○でも●でもよいことを*で表す.}\ ただし,\ \textcolor{forestgreen}{下線部には特定の制約がつく.} \\\\  (1)\ \ 左から見て,\ \textcolor{cyan}{\.{最}\.{初}\.{の}3個以上の連続がどこから始まるか}で場合分けする. \ \bm{最初の連続がどこから始まるかで場合分けする}のが標準解法である.\ 初見では到底気付かない. \\[.2zh] 何個連続するかで場合分けする必要はなく,\ 3個以上連続する順列をまとめて求めることができる. \\[.2zh] 排反な場合分けが可能なのでリスクが低く,\ 自然な思考が可能になる優れた解法である. \\[1zh] 全体から「\,2個のみ連続」と「連続しない」を除くことを思いつく人もいるだろう(補集合の利用). \\[.2zh] しかし,\ 連続個数が少ないほどパターンが増えて求めづらくなるので,\ 余計面倒である. →\ (3),\ (4) \\[1zh] [1]\ \ 最初の3個以上の連続が1個目から始まるとき,\ 4個目からは○でも●でも構わない. \\[.2zh] \phantom{[1]}\ \ \bm{1つの*につき○か●かの2通りがある}から,\ 2^4=16\ (通り)である. \\[1zh] [5]\ \ 考えるのは,\ あくまでも\bm{最初の3個以上の連続が5個目から始まる場合}であることに注意する. \\[.2zh] \phantom{[1]}\ \ つまり,\ 便宜上\ ***●○○○\ としているが,\ \bm{***\ が\ ○○○\ ではないという制約がつく.} \\[.2zh] \phantom{[1]}\ \ ○○○●○○○\ のとき,\ 最初の3個以上の連続が1個目から始まる扱いとなるからである. \\[.2zh] \phantom{[1]}\ \ よって,\ この場合(1通り)を除く必要がある. \\[.2zh] \phantom{[1]}\ \ 単純に\ ***●○○○\ の場合を考えてしまうと排反な場合分けにならないのである. \\[.2zh] \phantom{[1]}\ \ 優れた解法ではあるが,\ \bm{ノーリスクではない}ことを肝に銘じておいてほしい. 2個のみのようにちょっとだけ連続する場合が最も複雑性が高く,\ 求めづらい. \\[.2zh] 標準解法を知っていたとしても,\ 正しい答えに至るのは容易ではない. \\[1zh] [1]\ \ \underline{****}\,に3個以上の○が並んではいけない. \\[.4zh] \phantom{[1]}\ \ ○○○○,\ ○○○●,\ ●○○○\,の3通りを除く. \\[1zh] [2]\ \ \underline{***}\,が\,○○○\,となる1通りを除く. \\[1zh] [4]\ \ \underline{**}\,が\,○○\,となる2通りを除く.\ \ \bm{1通りではない!} \\[.4zh] \phantom{[1]}\ \ 右端の\,*\,が○か●かで2通りある. \\[1zh] [5]\ \ \underline{***}\,に2個以上の○が並んではいけない. \\[.4zh] \phantom{[1]}\ \ ○○○,\ ○○●,\ ●○○\,の3通りを除く. \\[1zh] [6]\ \ \underline{****}\,に2個以上の○が並んではいけない.\ 以下の8通りを除く. \\[.4zh] \phantom{[1]}\ \ ○が4個並ぶ場合 ○○○○ \\[.2zh] \phantom{[1]}\ \ ○が3個並ぶ場合 ○○○●,\ ●○○○ \\[.2zh] \phantom{[1]}\ \ ○が2個並ぶ場合 ○○●○,\ ○○●●,\ ●○○●,\ ○●○○,\ ●●○○ {○が4個}のとき ○●○●○●○\ の1通り. ○が3個}のとき ●4個の両端または間の5ヶ所への入れ方は ○が2個}のとき ●5個の両端または間の6ヶ所への入れ方は {○が1個}のとき ●6個の両端または間の7ヶ所への入れ方は ○が0個}のとき ●●●●●●●\ の1通り. \\\\ 連続しない場合については,\ \bm{隣接しない順列と同様の発想が通用する}ので容易である. \\[.2zh] \bm{隣接しないものは,\ それら以外のものを並べた後,\ 両端または間に入れればよい}のであった. \\[.2zh] ○は最大でも4個である.\ ○が0個の場合を忘れないように注意する. \\[1zh] [2]\ \ まず,\ ●4個を並べる.\ といっても,\ 4個の●は区別できないから,\ その並べ方は1通りである. \\[.2zh] \phantom{[1]}\ \ 後は,\ \bm{_\land\ ●\ _\land\ ●\ _\land\ ●\ _\land\ ●\ _\land}\ \ の5ヶ所の\ _\land\ から3ヶ所選んで○を入れればよい. \\[.2zh] \phantom{[1]}\ \ 3個の○は区別できないから,\ 選ぶだけで並べたことになる.
タイトルとURLをコピーしました