GOUKAKUの7文字を1列に並べるとき,\ 同じ文字が隣り合わない並べ方は何通り
同じものを含む順列（隣接する・隣接しない） \\
K\,2文字,\ U\,2文字,\ A,\ G,\ Oの計7文字の並べ方は
2個のKが隣り合う}並べ方は
2個のUが隣り合う}並べ方も
2個のKが隣り合い,\ 2個のUも隣り合う}並べ方は
隣接するものと隣接しないものの扱いの基本はすでに学習済みである.
[1]\ \ 隣接するものは,\ 1組にまとめて全体を並べた後,\ 組の中を並べる.}
[2]\ \ 隣接しないものは,\ それら以外のものを並べた後,\ 両端または間に入れる.}
本問は,\ 同じものを含み,\ なおかつ隣接しないものが2種類ある}というより応用的な問題である.
隣接しないものが1種類のときは,\ [2]の方針で直接的に求めることが有効であった.
しかし,\ 隣接しないものが2種類以上あるとき,\ 先に隣接する並べ方を考えると楽になることがある.}
本解は,\ 総数から隣接する場合の数を除く}方針で求めたものである.
注意すべきは,\ 「\,2個のUが隣り合う」と「\,2個のKが隣り合う」}が排反ではない}ことである.
これらが同時に起こる場合も考慮し,\ 二重に引いてしまわないようにしなければならない.
ベン図}(下左図)でとらえるとわかりやすいだろう.\ 色塗り部分を求めればよいわけである.
まずは総数を求める.\ 同じものを含む順列}の求め方は前項で学習済みである.
一旦7個の文字がすべて区別できるものとして並べ,\ 区別できないものの並べ方で割る.}
2個の Kが隣り合う場合は,\ まず異なる6つのもの\ \fbox{KK\vphantom{$_1$\ \fbox{A\vphantom{$_1$\ \fbox{G\vphantom{$_1$\ \fbox{O\vphantom{$_1$\ \fbox{U$_1$}\ \fbox{U$_2$}\ の並びと考える.
実際にはbf U_1\,とbf U_2\,は区別できないから,\ その並べ方2!\,で割る}(同じものを含む順列).
2個の Kは区別できないので,\ \fbox{KK}\ の中の並び換えを考慮する必要はない(1通りしかない).
共通部分は,\ 異なる5つのもの\ \fbox{KK}\ \fbox{UU}\ \fbox{A}\ \fbox{G}\ \fbox{O}\ の並びである.
個数定理n(A∪ B)=n(A)+n(B)-n(A∩ B)より,\ 図の白色部分は\ 360+360-120\ (通り)ある.
本解の考え方は自然だが,\ 同じものが3個以上ある場合には厳しくなる.}\ つまり,\ 応用性が低い.}
本問のように同じものが2個の場合は,\ (隣接しない)=(総数)-(\,2個隣接)が成り立つ.
しかし,\ 同じものが3個の場合は,\ (隣接しない)=(総数)-(\,3個隣接)-(\,2個のみ隣接)となる.
これが面倒なので,\ 3個以上のものが隣り合わない場合は,\ [2]のように求めるのが基本なのであった.
2個のKが隣り合わない}並べ方は $2個のKが隣り合わず,\ 2個のUが隣り合う}並べ方は
上で述べたように,\ 総数から隣接するものを除く方法は応用性が低い.
隣接しないものを直接的に求めることを考える.
「\,2個のbf Kが隣接しない」･･･\,①\ は容易に求めることができる.}
しかし,\ 「\,2個のKが隣接しない\ \ かつ\ \ 2個のU}が隣接しない」は簡単には求まらない(別解2).
実は,\ 「\,2個のKが隣接しない\ \ かつ\ \ 2個のUが隣接する}」･･･\,②\ ならば容易に求められる.}
そこで,\ 容易に求まる①と②を利用したのが別解1である.
つまり,\ (\,2個のKと2個のUが}それぞれ隣り合わない)=①-②\ である.
ベン図(上右図)でいえば,\ (共通部分)=(\,2個のbf Kが隣り合わない)-(斜線部分)}である.
2個の Kが隣り合わない場合,\ まず\ \fbox{A}\ \fbox{G}\ \fbox{O}\ \fbox{U}\ \fbox{U}\ を並べる.
その後,\ ○\ \fbox{U}\ ○\ \fbox{G}\ ○\ \fbox{A}\ ○\ \fbox{U}\ ○\ \fbox{O}\ ○\ \ の6ヶ所の○から\ \fbox{K}\ が入る2ヶ所を選べばよい.
2個のKが隣り合わず,\ 2個のUが隣り合う場合},\ まず\ \fbox{A}\ \fbox{G}\ \fbox{O}\ \fbox{UU}\ を並べる.
その後,\ ○\ \fbox{G}\ ○\ \fbox{UU}\ ○\ \fbox{O}\ ○\ \fbox{A}\ ○\ \ の5ヶ所の○から\ \fbox{K}\ が入る2ヶ所を選べばよい.
別解1の考え方は,\ bf Kが3個以上でも通用する(計算量ほぼ同じ)}という点で本解より優位である.
2個のKの間にA,\ G,\ Oが少なくとも1つ入る}とき
3文字の両端と間の4ヶ所にK\,2個を1個ずつ入れる}方法は $C42}=6\ (通り)$
\ \ 5文字の両端と間の6ヶ所にU\,2個を1個ずつ入れる}方法は 2個のKの間にA,\ G,\ Oがいずれも入らない}ときKUK,\ A,\ G,\ Oの並べ方}は $4!}=24\ (通り)$
\ \ その両端と間の5ヶ所に1個のUを入れる}方法は $
別解2は,\ 「\,2個のKが隣接しない\ \ かつ\ \ 2個のU}が隣接しない」を直接的に求めるものである.
しかし,\ 「両端または間に入れる」を2段階で行うと一部の場合が漏れる}ことに注意が必要である.
以下のような手順で,\ 同じ文字が隣り合わないように並べるとしよう.
「\,A,\ G,\ Oを並べる」→「\,K\,2個を両端か間に入れる」→「\,U\,2個を両端か間に入れる」}
この場合,\ 例えば\ [\,KUKGOUA\,]}\ がカウントされなくなる.
Uを入れる前の段階で,\ [\,KKGOA\,]\ のように2個のKが隣り合っている必要があるからである.}
このような場合もあり得るため,\ 2つの互いに排反}な場合に分けて求めたわけである.
[1]}\ \ まず,\ \fbox{K}\ \fbox{K}\ \fbox{A}\ \fbox{G}\ \fbox{O}\ を2個のKが隣り合わないように並べる.}
\ \ \fbox{A}\ \fbox{G}\ \fbox{O}\ を並べた後,\ ○\ \fbox{G}\ ○\ \fbox{O}\ ○\ \fbox{A}\ ○\ \ の○の位置に2個の\ \fbox{K}\ を入れる.
\ \ さらに,\ △\ \fbox{G}\ △\ \fbox{K}\ △\ \fbox{O}\ △\ \fbox{A}\ △\ \fbox{K}\ △\ \ の△の位置に2個の\ \fbox{U}\ を入れればよい.
[2]}\ \ KUKの順で並ぶ}しかないから,\ まず\ \fbox{KUK}\ \fbox{A}\ \fbox{G}\ \fbox{O}\ を並べる.
\ \ さらに,\ △\ \fbox{O}\ △\ \fbox{KUK}\ △\ \fbox{A}\ △\ \fbox{G}\ △\ \ の△の位置に残り1個の\ \fbox{U}\ を入れればよい.
{AABBCCの6文字を1列に並べるとき,\ 同じ文字が隣り合わない並べ方は何通りあるか.} \\
{2個のAが隣り合う}並べ方は {2個のBが隣り合う}並べ方と2個のCが隣り合う}並べ方も30通りである. {2個のAが隣り合い,\ 2個のBも隣り合う}並べ方はB同士とC同士それぞれ隣り合う,\ C同士とA同士がそれぞれ隣り合う}並べ方も12通り.}{同じ文字が隣り合う}並べ方は {対称性より,\ A○○○○○とB○○○○○とC○○○○○の各文字列の数は等しい.}
A○○○○○のとき,\ 2文字目はBかCの2通りである.
対称性より,\ AB○○○○とAC○○○○の各文字列の数は等しい.}
よって,\ AB○○○○の場合の数を求めて6倍する}と求める場合の数となる.
AB○○○○のとき,\ ABA○○○またはABC○○○となる.
ABA○○○}となるのは,\ ABACBCの1通り}である.
ABC○○○}となるとき,\ ○○○はABC,\ ACB,\ BAC,\ BCAの4通り}である.
よって,\ AB○○○○は5通りあるから,\ 求める場合の数は$5×6}=30\ (通り)}$である.
いずれも2文字であるから,\ 総数から隣り合う場合の数を除く}方針が有効である(本解).
3つの集合の場合の個数定理}を使うことになるが,\ A,\ B,\ Cには対称性がある}ので面倒さはない.
2個のA,\ 2個のB,\ 2個のC}が隣り合う文字列の集合をそれぞれA,\ B,\ Cとする.
n(A∪ B∪ C)=n(A)+n(B)+n(C)-n(A∩ B)-n(B∩ C)-n(C∩ A)+n(A∩ B∩ C)
対称性を考慮すると,\ n(A∪ B∪ C)=3n(A)-3n(A∩ B)+n(A∩ B∩ C)\ となる.
2個の Aが隣り合うとき,\ \ \fbox{AA}\ \fbox{B}\ \fbox{B}\ \fbox{C}\ \fbox{C}\ の並びである.
2個の Aが隣り合い,\ 2個の Bも隣り合うとき,\ \ \fbox{AA}\ \fbox{BB}\ \fbox{C}\ \fbox{C}\ の並びである.
同じ文字が隣り合うとき,\ \ \fbox{AA}\ \fbox{BB}\ \fbox{CC}\ の並びである.
厳しい条件により可能な文字列は限定されるから,\ すべての場合を書き出す}のも有効である(別解).
実際には,\ 対称性の考慮}により,\ すべてを書き出す必要はなくなる.
本問が完全な初見な場合,\ 即座に諦めてしまう学生が実に多いが,\ 別解ならば可能なはずである.
すべて書き出そうと手を動かす中で対称性・規則性に気付けば,\ 後は計算で求めればよいわけである.
