場合の数 ★★★ 応用の問題 全8問

方針

解答

⓪ 発想(どう考え始めるか) 問題の形は「$3$ 種類・合計 $8$ 個・$0$ 個も可」。

果物そのものを並べるかわりに、○ $8$ 個と仕切り $2$ 本の列に置き換える。すると、買い方と記号列がちょうど $1$ 対 $1$ で対応する。ものの配分を、記号の並べ替えに言い換える。重複組合せはこの対応を見つければ解ける。

3種類から合計8個を選ぶ問題を、「記号の並べ方」に置きかえる。果物を ○ で表し、りんご・みかん・なしの3グループを2本の仕切り | で区切る。たとえば

は「りんご2個、みかん3個、なし3個」を表す。買わない種類があるときは、その区画の ○ が0個になる(仕切りがとなり合う)だけで、きちんと表せる。

こうすると、買い方は「○を8個、|を2個、合わせて10個を1列に並べる」並べ方とぴったり1対1で対応する。10か所のうち、仕切り | を置く2か所を選べば並びが決まるので

$${}_{10}{\mathrm{C}}_2=\frac{10\times 9}{2\times 1}=45(\text{通り})$$

まとめ:これは「$x+y+z=8$ を満たす0以上の整数の組が何通りか」を数えるのと同じだ。一般に、$n$ 種類から重複を許して $r$ 個選ぶ重複組合せは、仕切り $n-1$ 本と ○ $r$ 個の並べ方 ${}_{n+r-1}{\mathrm{C}}_{n-1}$ で求まる。ここでは $n=3,r=8$ で ${}_{10}{\mathrm{C}}_2$ になる。

発展。 この $45$ という数は $(x+y+z{)}^8$ を展開したときに現れる項の種類の数と同じだ。

展開すると $x^i{y}^j{z}^k$($i+j+k=8$)の形の項が出る。指数の組 $(i,j,k)$ を選ぶことは、りんご・みかん・なしの個数を選ぶことにほかならない。だから項の種類は $45$ 通りになる。

このように「重複を許して選ぶ」数え上げは、多項式の展開や母関数と地続きだ。選び方を式の項で表すと、代数の道具がそのまま数え上げに使える。

別解

別解:りんごの個数で場合分けして足す(苦手な人向けの素朴なルート)。 仕切りの並べ方に言い換えず、正面から数えてみる。

りんごの個数を $a$ 個と決める。$a$ は $0$ から $8$ まで動く。りんごを $a$ 個にすると、残りの $8-a$ 個をみかんとなしの $2$ 種類に分けることになる。みかんを何個にするかで分け方が決まり、みかんは $0$ 個から $8-a$ 個まで選べるので $9-a$ 通り。

あとは $a$ を動かして足し合わせる。

$$\sum _{a=0}^8(9-a)=9+8+7+\cdots +1=45.$$

仕切りの発想がぱっと出なくても、$1$ つの種類を固定して残りを数えるだけでたどり着ける。本解と同じ $45$ 通りだ。

方針

解答

⓪ 発想(どう考え始めるか) 「全員が自分の以外」を正面から数えるのは難しい。

そこで補集合に切り替える。「少なくとも $1$ 人が自分のを受け取る」場合を、全体から引く。ただし「$1$ 人が自分の」という場合どうしは重なり合う。重なりを足し引きする包除で調整する。

否定の数え上げは補集合と包除の合わせ技で攻める。その定跡を総合する問題だ。

全員が自分以外を受け取る配り方を、包除の考え方で数える。「自分のものを受け取ってしまう」という『まずい』場合を引いていく。

特定の $k$ 人が自分のプレゼントを受け取り、残り $4-k$ 人は自由、という配り方は ${}_4{\mathrm{C}}_k\times (4-k)!$ 通り。これを $k=1,2,3,4$ について、符号を「引く→足す→引く→足す」と交互にして全体から差し引く。

$$4!-{}_4{\mathrm{C}}_1\cdot 3!+{}_4{\mathrm{C}}_2\cdot 2!-{}_4{\mathrm{C}}_3\cdot 1!+{}_4{\mathrm{C}}_4\cdot 0!$$

$$=24-4\times 6+6\times 2-4\times 1+1\times 1=24-24+12-4+1=9(\text{通り})$$

符号が交互になるのは、「1人が自分のを受け取る場合」を引くと「2人が受け取る場合」を引き過ぎるので足し戻し、するとまた「3人」を戻し過ぎる…という調整が続くからだ。

まとめ:4人くらいなら、実際に樹形図で書き出しても9通りと確かめられる。「Aが受け取る相手はB, C, Dの3通り、その1つ1つに対して残りの配り方が3通り」で $3\times 3=9$ 通り、という数え方もできる。

発展。 $9$ 通りの中身を「入れかわりの形」で分類すると、構造が分かる。全員が自分以外を受け取る配り方は、じつは $2$ つの型しかない。

$1$ つは「$2$ 人ずつのペアが交換する」型。$4$ 人を $2$ 人ずつのペアに分ける方法は $3$ 通りで、各ペアの中で交換するだけだから、この型は $3$ 通り。

もう $1$ つは「$4$ 人がひとつの輪になって順送りする」型。$\mathrm{A}\to \mathrm{B}\to \mathrm{C}\to \mathrm{D}\to \mathrm{A}$ のような一巡の並べ方は $(4-1)!=6$ 通り。合わせて $3+6=9$ で、数え上げの結果とぴたり一致する。

この「交換のペア」と「順送りの輪」への分解は、並べかえ(置換)をサイクルという部品に分ける見方で、あらゆる並べかえがサイクルの組み合わせに分解できる。完全順列とは「長さ $1$ のサイクル(動かない人)がない置換」のことだ、と言い直せる。

別解

別解:小さい人数から漸化式で積み上げる(得意な人向けの視点)。 包除を使わず、人数を増やしながら数える。

$n$ 人の完全順列の個数を $D_n$ とする。$1$ 人だけなら自分に配るしかなく $D_1=0$、$2$ 人なら入れ替える $1$ 通りで $D_2=1$。

$n$ 人のとき、$1$ 番の人が受け取る相手を $k$ とすると、$k$ の選び方は $n-1$ 通り。このとき「$k$ 番も $1$ 番のものを受け取る(=$1$ と $k$ が交換する)」なら、残り $n-2$ 人の完全順列で $D_{n-2}$ 通り。「$k$ 番は $1$ 番のを受け取らない」なら、残り $n-1$ 人を「それぞれ決まった $1$ 席を避けて」座らせる完全順列とみなせて $D_{n-1}$ 通り。

まとめると

$$D_n=(n-1)\left(D_{n-1}+D_{n-2}\right).$$

順に計算すると $D_3=2(D_2+D_1)=2(1+0)=2$、$D_4=3(D_3+D_2)=3(2+1)=9$。本解の包除と同じ $9$ 通りだ。

方針

解答

⓪ 発想(どう考え始めるか) 塗り分けは、制約のいちばんきつい領域から決めるのが基本だ。

全部の扇形と接している中心を、最初に塗る。すると残りは輪に並んだ扇形どうしの隣接だけの問題になる。輪の塗り分けは、最後の $1$ 枚が最初の $1$ 枚とも隣り合う。そこで衝突が起こりうると、先に見抜いておく。場合分け、または数え直しが要る合図だ。

中心を決める: 中心の色は4通り、どれでもよい。

扇形を決める: 4つの扇形を輪の順に $S_1,S_2,S_3,S_4$ とする($S_1$-$S_2$-$S_3$-$S_4$-$S_1$ がとなり合う)。各扇形は中心と違う色でなければならないので、使えるのは中心以外の3色だ。この3色で、輪をなす4つの扇形を、となりどうし違うように塗る。

$S_1$ は3通り。$S_2$ は $S_1$ と違う2通り。$S_3$ は $S_2$ と違う2通り。問題は $S_4$ で、$S_3$ とも $S_1$ とも違う色でなければならない。$S_1$ と $S_3$ が同じ色か違う色かで $S_4$ の選択肢が変わるので、単純なかけ算だけでは処理できない。

こういう『輪(サイクル)の塗り分け』は、次の公式で数えられる。$n$ 個の領域が輪をなすとき、$k$ 色でとなりどうし違うように塗る方法は

$$(k-1{)}^n+(-1{)}^n(k-1)$$

通りだ。いま扇形は $n=4$ 個、使える色は中心以外の $k=3$ 色だから

$$(3-1{)}^4+(-1{)}^4(3-1)=2^4+2=16+2=18(\text{通り})$$

かけ合わせる: 中心の4通りと扇形の18通りは別々に選べるので

$$4\times 18=72(\text{通り})$$

まとめ:もし扇形が輪ではなく一列(両はしがつながらない)なら $3\times 2\times 2\times 2=24$ 通りで済む。でも輪では、両はし(最初と最後)もとなり合うぶん条件が増える。図の形が『輪か一列か』を正しく読み取るのが、塗り分けの出発点だ。

発展。 この図は中心の点を $4$ つの扇形すべてとつなぎ、扇形どうしを輪でつないだ形だ。グラフ理論では車輪グラフ $W_4$ と呼ばれる。

「隣り合う領域は違う色」という塗り分けの数は、色数 $k$ を変数と見ると $k$ の多項式になる。これを彩色多項式という。$W_4$ の彩色多項式に $k=4$ を代入すると、ちょうど $72$ が出る。

地図の塗り分け(四色定理)もこの彩色多項式の枠組みで語られる。図形の隣接関係をグラフに直すと、塗り分けが代数の問題に変わる。

別解

別解:輪の公式を使わず場合分けで数える(苦手な人向けの手作業ルート)。 扇形に使えるのは中心以外の $3$ 色。この $3$ 色で輪 $S_1$-$S_2$-$S_3$-$S_4$-$S_1$ を塗る数を、じかに数える。

$S_1$ は $3$ 通り。$S_2$ は $S_1$ と違う $2$ 通り。ここまでは素直だ。

問題の $S_4$ は $S_3$ とも $S_1$ とも違わねばならない。そこで $S_3$ の色で場合を分ける。$S_3$ は $S_2$ と違えばよいので、候補は $S_1$ と「残りの $1$ 色」の $2$ つ。

• $S_3=S_1$ のとき:$S_4$ は $S_3=S_1$ を避ければよく、$3$ 色から $1$ 色を除いて $2$ 通り。
• $S_3$ が残りの $1$ 色のとき:$S_4$ は $S_3$ とも $S_1$ とも違い、この $2$ 色は別なので $1$ 通り。

$S_3,S_4$ の決め方は $1\cdot 2+1\cdot 1=3$ 通り。よって扇形は $3\cdot 2\cdot 3=18$ 通り。中心 $4$ 通りとかけて

$$4\times 18=72.$$

公式を覚えていなくても、最後の $1$ 枚の衝突を場合分けで押さえれば、同じ $72$ 通りにたどり着く。

方針

解答

⓪ 発想(どう考え始めるか) 通れない辺がある問題だ。

その辺を避ける経路を正面から数えると、回り道の場合分けが増える。逆に、全体から「その辺を通る経路」を引くほうが速い。その辺を通る経路は $P\to Q$ の $1$ 歩を必ず踏む。だから前半 $A\to P$ と後半 $Q\to B$ に切れて、かけ算で数えられる。

禁止条件を補集合と分割のかけ算で処理する合わせ技だ。

全経路数: A から B へは右4区画・上3区画なので

$$\frac{7!}{4!\times 3!}=35(\text{通り})$$

工事区間 P→Q を通る経路: この道を通る経路は必ず「A→P と進み、P→Q の1歩を踏み、Q→B と進む」形になる。P は A から右2・上1、Q は右3・上1の場所だ。

• A → P: 右2区画・上1区画なので $\frac{3!}{2!1!}=3$ 通り
• Q → B: 残り右1区画・上2区画なので $\frac{3!}{1!2!}=3$ 通り

P→Q の1歩は決まっているので、前半3通りと後半3通りの組合せで $3\times 3=9$ 通りがこの工事区間を通る。

工事区間を通らない経路: 全体から引いて

$$35-9=26(\text{通り})$$

まとめ:「特定の道を通らない」を最初から数えると、その道を避ける回り道を場合分けすることになって大変だ。『通ってしまう経路』のほうが(1歩が決まっているぶん)数えやすいので、裏返して引くのが得だ。

発展。 別解では全経路を「列 $x=2$ から $x=3$ へどの高さで移るか」で分類して足した。この足し算は二項係数の積の和 $\left(\genfrac{}{}{0ex}{}{2}{2}\right)\left(\genfrac{}{}{0ex}{}{4}{1}\right)+\left(\genfrac{}{}{0ex}{}{3}{2}\right)\left(\genfrac{}{}{0ex}{}{3}{1}\right)+\left(\genfrac{}{}{0ex}{}{4}{2}\right)\left(\genfrac{}{}{0ex}{}{2}{1}\right)+\left(\genfrac{}{}{0ex}{}{5}{2}\right)\left(\genfrac{}{}{0ex}{}{1}{1}\right)$ になり、値は全経路 $\left(\genfrac{}{}{0ex}{}{7}{3}\right)=35$ に等しい。

二項係数の積を足すと $1$ つの二項係数にまとまる、というヴァンデルモンド型の恒等式(畳み込み)の一例だ。経路を途中の $1$ か所で切って前後に分けるたびに、この形が現れる。

禁止された $1$ 本の辺はこの和からちょうど $1$ 項($\left(\genfrac{}{}{0ex}{}{3}{2}\right)\left(\genfrac{}{}{0ex}{}{3}{1}\right)=9$)を落とすことに当たる。数え上げを和の形にしておくと、禁止や条件を「項を消す」操作として扱える。

別解

別解:列の境目を「どの高さで越えるか」で数える(直接足し上げるルート)。 引き算を使わず、通ってよい経路を正面から足し上げる。

どの経路も $x=2$ の列から $x=3$ の列へ移る右向きの $1$ 歩を、ちょうど一度だけ踏む。その $1$ 歩の高さ $y$ は $0,1,2,3$ のどれかだ。工事中なのは高さ $y=1$ の $1$ 歩、すなわち $P\to Q$。だから $y=0,2,3$ で越える経路だけを数えればよい。

高さ $y$ で越える経路の数は、$A\to (2,y)$ と $(3,y)\to B$ の積になる。

• $y=0$:$\left(\genfrac{}{}{0ex}{}{2}{2}\right)\times \left(\genfrac{}{}{0ex}{}{4}{1}\right)=1\times 4=4$
• $y=2$:$\left(\genfrac{}{}{0ex}{}{4}{2}\right)\times \left(\genfrac{}{}{0ex}{}{2}{1}\right)=6\times 2=12$
• $y=3$:$\left(\genfrac{}{}{0ex}{}{5}{2}\right)\times \left(\genfrac{}{}{0ex}{}{1}{1}\right)=10\times 1=10$

足すと

$$4+12+10=26.$$

全体から引く本解と同じ $26$ 通りに、こんどは足し算だけでたどり着く。

方針

解答

⓪ 発想(どう考え始めるか) これは、基本の「$6$ 人を $2$ 人ずつ」の拡大版だ。

構造は同じ。まず区別ありで数え、そのあと区別のない同じ人数の組の並べ替え $3!$ で割る。人数が増えても、割る理由は変わらない。同じ分け方が $3!$ 回だぶって数えられるからだ。原理から自分で再現できるかを問う問題だ。

(1) 名前のついた組 A, B, C に、順に人を選んで入れる。

$${}_9{\mathrm{C}}_3\times {}_6{\mathrm{C}}_3\times {}_3{\mathrm{C}}_3=84\times 20\times 1=1680(\text{通り})$$

(2) 組に名前がない場合を考える。(1)では同じ3人組の集まりでも「どれを A・B・C と呼ぶか」で $3!=6$ 通りを別々に数えている。組に名前がなければ、これらは全部同じ分け方なので、6で割る。

$$\frac{1680}{3!}=\frac{1680}{6}=280(\text{通り})$$

まとめ:3つの組がすべて同じ人数(3人)だからこそ、$3!$ 通りの呼び替えが全部ダブりになる。もし『4人・3人・2人』のように人数がすべて違えば、組の大きさで自然に区別がつくので割る必要はない。「同じ大きさの組が何個あるか」を見て、その個数の階乗で割る、と覚えておこう。

発展。 同じ人数 $m$ の組を $n$ 個つくって $mn$ 人を分ける数は、一般に $\frac{(mn)!}{(m!{)}^{n}n!}$ だ。いまは $m=3,n=3$ で $\frac{9!}{(3!{)}^{3}3!}=280$ になる。

名前をつけた(区別する)組に分ける数は $\frac{(mn)!}{(m!{)}^n}$ で、これは名前なしの数のちょうど $n!$ 倍。名前の付け替え $n!$ 通りだけ多く数えているからだ。

この分数はいつも整数になる。実際に「分け方の個数」を数えているのだから、割り切れて当然だ。階乗の割り算が整数になる背景には、たいていこうした数え上げの意味がある。

別解

別解:「その組の代表」を決めて重複を出さずに数える(割り算のいらないルート)。 (2)の名前なしの組分けを、$3!$ で割らずに直接数える。

コツは組を「いちばん若い番号の人」で見分けること。まず全体で最年少の $1$ 番を含む組をつくる。$1$ 番の相手 $2$ 人を残り $8$ 人から選んで $\left(\genfrac{}{}{0ex}{}{8}{2}\right)=28$ 通り。

次に、まだ組に入っていない人のうち最年少の人を含む組をつくる。相手 $2$ 人を残り $5$ 人から選んで $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ 通り。残った $3$ 人が最後の組で $1$ 通り。組はいつも「含まれる最年少の人」でひとりでに見分けられるので、重複は生じない。

$$\left(\genfrac{}{}{0ex}{}{8}{2}\right)\times \left(\genfrac{}{}{0ex}{}{5}{2}\right)\times 1=28\times 10=280.$$

区別ありで数えて $3!$ で割る本解と同じ $280$ 通り。代表を決める見方だと、そもそもだぶりが出ない。

方針

解答

⓪ 発想(どう考え始めるか) 「何番目か」は、$1$ つずつ数えていては終わらない。

先頭の数字を決めると、残り $4$ 桁の並びが $4!$ 個のかたまりになる。このブロック単位で数を積み上げる。逆に「$80$ 番目は?」も、同じブロック割りで上の位から絞り込める。

辞書式はブロックの大きさで位取りをする。以下ではこの見方で数える。5個の数字の順列は $5!=120$ 個。先頭の数字を1つ決めると、残り4桁の並びが $4!=24$ 個あるので、「先頭が◯の整数」は24個ずつのかたまりになる。

(1) 51234 の順位

先頭が 1, 2, 3, 4 の整数は、それぞれ24個ずつで合計 $4\times 24=96$ 個あり、これらは全部 51234 より小さい(先頭が5より小さいから)。

次に先頭が5の整数を考える。51234 は、先頭5の後ろが「1234」で、これは残り4個 $\{1,2,3,4\}$ を小さい順に並べたいちばん小さい並びだ。だから先頭5のかたまりの中では1番目。

$$96+1=97(\text{番目})$$

(2) 80番目の数

80番目がどの『先頭』のかたまりに入るかを調べる。24個ずつなので

• 先頭1: 1〜24番目、先頭2: 25〜48番目、先頭3: 49〜72番目、先頭4: 73〜96番目

80番目は先頭4のかたまりの中の $80-72=8$ 番目だ。先頭は4に決まる。残る数字は $\{1,2,3,5\}$。2桁目を決めると残り3桁が $3!=6$ 個ずつのかたまりになる。$\{1,2,3,5\}$ を小さい順に見て

• 2桁目1: 1〜6番目、2桁目2: 7〜12番目

8番目は2桁目2のかたまりの $8-6=2$ 番目。2桁目は2。残る数字は $\{1,3,5\}$。3桁目を決めると残り2桁が $2!=2$ 個ずつ。

• 3桁目1: 1〜2番目

2番目はこの中にあり、3桁目は1、その中の2番目。残る $\{3,5\}$ の並びは小さい順に「35」(1番目)、「53」(2番目)だから、下2桁は53。つなげて

$$4,2,1,5,3⟹42153$$

発展。 辞書式の順番が決まると、ある並びの「次の並び」を、全部を作り直さずに求められる。

手順はこうだ。右から見て、初めて増加する箇所を探す。そこの数字を、右側にあるより大きい数字のうち最小のものと入れ替え、さらに右側を小さい順に並べ替える。これで辞書式のちょうど $1$ つ後ろが得られる。

この「次の順列」の作り方はコンピュータで順列を辞書順にもれなく生成するときの基礎になっている。$120$ 個の並びを $1$ 番から順に書き出したり、ある並びから何番か先へ飛んだりできる。数え上げと手順(アルゴリズム)は地続きだ。

別解

別解:順位を「階乗進法」の数として読む(得意な人向けの高い視点)。 位取りのかたまりが $4!,3!,2!,1!$ だったことに注目すると、順位そのものを「位の重みが階乗になった数」として読める。

まず順位を $0$ から数え直す(最小の $12345$ を $0$ 番目とする)。ある並びの $0$ 始まりの順位は、各桁について「その桁より右にある、自分より小さい数字の個数」を、重み $4!,3!,2!,1!$ でかけて足した値になる。

(1) $51234$ では、先頭 $5$ の右に小さい数字が $4$ 個あり、以降の桁は右に自分より小さい数字が $1$ つもない。だから $0$ 始まりの順位は $4\times 4!+0\times 3!+0\times 2!+0\times 1!=96$。$1$ 始まりに直して $97$ 番目。

(2) $80$ 番目は $0$ 始まりで $79$。これを階乗の重みで割り分ける。$79=3\times 4!+1\times 3!+0\times 2!+1\times 1!$ で、係数は上の桁から $(3,1,0,1)$、最後の桁は残り $1$ 個で自動的に決まる。この係数は「残っている数字のうち、下から何個を飛ばして次を取るか」を表す。$\{1,2,3,4,5\}$ から $3$ 個飛ばして $4$、残り $\{1,2,3,5\}$ から $1$ 個飛ばして $2$、残り $\{1,3,5\}$ から $0$ 個飛ばして $1$、残り $\{3,5\}$ から $1$ 個飛ばして $5$、最後は $3$。よって $42153$。

順位と並びを「位の重みが $10,100$ でなく $4!,3!,2!$ の数」で橋渡しするこの見方なら、順位を $1$ つの数として分解するだけで並びが定まる。本解の積み上げと同じ $97$ 番目・$42153$ にたどり着く。

方針

解答

⓪ 発想(どう考え始めるか) 玉に区別がないから、分け方を決めるのは「誰が何個か」の数の組だけだ。

つまり $x+y+z=10$ の整数解の個数を数えればよい。これは重複組合せ、すなわち ○ と仕切りの並べ方に言い換えられる。(2)の「$1$ 個以上」は先に $1$ 個ずつ配ってしまう。すると「$0$ 個以上」の型に戻る。条件を配り済みにして標準形へ帰着させる発想だ。

玉が区別できないので、分け方は A, B, C のもらう個数 $x,y,z$ の組で決まる。つまり $x+y+z=10$ の整数の組を数える。

(1) 各人0個以上なので、0以上の整数の組を数える。玉10個を ○、A・B・C の区切りを仕切り | 2本で表すと、○10個と | 2本の並べ方に対応する。

よって

$${}_{10+2}{\mathrm{C}}_2={}_{12}{\mathrm{C}}_2=\frac{12\times 11}{2\times 1}=66(\text{通り})$$

(2) 3人とも1個以上という条件は、先に1個ずつ配ってしまうと扱いやすい。まず A, B, C に1個ずつ配ると3個使い、残りは $10-3=7$ 個。これを改めて0個以上で3人に分ければ、全員が(最初の1個があるので)必ず1個以上になる。残り7個を0以上で分ける方法は

$${}_{7+2}{\mathrm{C}}_2={}_9{\mathrm{C}}_2=\frac{9\times 8}{2\times 1}=36(\text{通り})$$

まとめ:『1個以上』を『先に1個ずつ渡して、残りを0個以上に』と読みかえるこの手は、$x,y,z\ge 1$ を $x^{\prime },y^{\prime },z^{\prime }\ge 0$($x=x^{\prime }+1$ など)に置きかえたのと同じだ。条件を消して基本の形に戻すのが、重複組合せの応用でよく使う方法だ。

発展。 (2)の答え $36$ は $10$ を $3$ 個の正の整数の順序つきの和に書く方法の数と同じだ。こうした順序つきの分け方を、整数の「組成」という。

一般に、正の整数 $r$ を $n$ 個の正の整数の順序つき和に書く方法は $\left(\genfrac{}{}{0ex}{}{r-1}{n-1}\right)$ 通り。$r$ 個の玉のあいだ $r-1$ か所から、仕切りを入れる $n-1$ か所を選ぶ、と見れば出る。

個数を問わず、$r$ を何個かの正の整数の和に書く方法をすべて足すと $2^{r-1}$ 通り。$r-1$ か所の各すきまで、仕切りを入れるか入れないかを選ぶからだ。順序を区別しない「分割」とは別物で、こちらはすきまの選び方で数えられる。

別解

別解:「$0$ 個の人がいる」場合を包除で除く(補集合のルート)。 (2)を先渡しせず、(1)の $66$ 通りから「誰かが $0$ 個」の分け方を引く。

まず「$A$ が $0$ 個」の分け方を数える。$A=0$ なら残り $10$ 個を $B,C$ に $0$ 個以上で分けるので、$B$ の個数が $0$〜$10$ で $11$ 通り。$B$ だけ、$C$ だけが $0$ の場合も、同じく $11$ 通りずつ。

ただし「$A,B$ がともに $0$」だと $C$ が $10$ 個で $1$ 通り。こうした $2$ 人が $0$ の場合を引きすぎるので、足し戻す。$3$ 人とも $0$ は和が $10$ にならず、起こらない。

包除でまとめると

$$66-\left(\genfrac{}{}{0ex}{}{3}{1}\right)\times 11+\left(\genfrac{}{}{0ex}{}{3}{2}\right)\times 1-0=66-33+3=36.$$

先に $1$ 個ずつ配る本解と同じ $36$ 通り。少し手間だが、条件を「禁止事象」として包除で処理する練習になる。

方針

解答

⓪ 発想(どう考え始めるか) 否定が $2$ つ重なった条件だ。

包除の型どおりに設計する。全体から「$AB$ が隣」と「$CD$ が隣」を引き、両方が隣の分を足し戻す。足し戻しを忘れると、両方隣の場合を二重に引いてしまう。この包除の仕組みを、ひも縛り(隣接のかたまり化)と組み合わせて使う。総合問題だ。

求めるのは「AB がとなり合わず、かつ CD もとなり合わない」並び方。否定が2つ重なるので、包除を使う。

全体: 6人を1列に並べる方法は $6!=720$ 通り。

AB がとなり合う: A と B をひもで結んで1つのかたまりにすると、「かたまり + 残り4人」の5つの並べ方 $5!$、かたまりの中の並び $2!$ で

$$2\times 5!=2\times 120=240(\text{通り})$$

CD がとなり合う: 同じように $2\times 5!=240$ 通り。

AB も CD もとなり合う: AB のかたまりと CD のかたまりを両方作ると、「2つのかたまり + 残り2人」の4つの並べ方 $4!$、各かたまりの中の並び $2!\times 2!$ で

$$2\times 2\times 4!=4\times 24=96(\text{通り})$$

包除で仕上げる: 「AB 隣接」と「CD 隣接」を引くと、両方となり合う96通りを2回引いているので、足し戻す。

$$6!-2\times 5!-2\times 5!+2\times 2\times 4!=720-240-240+96=336(\text{通り})$$

まとめ:否定が1つなら「全体 − となり合う」で済むが、否定が2つ重なると引き過ぎが出る。これは、$A\cup B$ を引くとき共通部分を2回引くので1回戻す、という個数定理とまったく同じ調整だ。

発展。 この解き方は「隣り合わせたくない組」が増えても使える。互いに人を共有しない($AB$ と $CD$ のように別々の)$k$ 組を、どれも隣り合わせない並べ方は、$n$ 人の列で ${\sum }_{j=0}^k(-1{)}^j(\genfrac{}{}{0ex}{}{k}{j})2^j(n-j)!$ 通りになる。

$k$ 組から $j$ 組を選んでそれぞれ「くっつけたかたまり」にすると、かたまりの中の並びが $2^j$、かたまりを $1$ 人分とみた全体の並べ方が $(n-j)!$、組の選び方が $\left(\genfrac{}{}{0ex}{}{k}{j}\right)$。これに符号を交互につけて足すのが包除だ。いまは $n=6,k=2$ で $720-480+96=336$ になる。

ただしこの式は $k$ 組が人を共有しないときに限る。たとえば $AB$ と $BC$ のように $B$ を共有すると、$2$ 組を同時にくっつけた形が $3$ 人のかたまりになり、内部の並びが $2^2$ でなくなって数え方が崩れる(このときの正しい答えは $288$ で、式の $336$ とはずれる)。並びを円卓に変えたり、$n$ 組の夫婦を男女交互かつどの夫婦も隣り合わないように円卓へ座らせる古典的な「夫婦問題(メナージュ問題)」に進んだりすると、端の重なりや交互条件が加わってさらに難しくなる。禁止したい隣接の形に合わせて包除の項の作り方を変えるのが、数え上げの腕の見せどころだ。

別解

別解:隙間法で $AB$ を離してから $CD$ を処理する(別の道具を使うルート)。 包除でなく、隣り合わせない配置を隙間に入れて作る。

まず $A,B$ を離す。ほかの $4$ 人 $C,D,E,F$ を並べると $4!=24$ 通りで、その両端と間に隙間が $5$ か所できる。この $5$ か所から $2$ か所を選んで $A,B$ を入れると、隣り合わない。順序を区別して $5\times 4=20$ 通り。合わせて $24\times 20=480$ 通り。

この $480$ 通りには $CD$ が隣り合うものも混じるので、それを引く。$CD$ を $1$ かたまり $[CD]$(中の並び $2$ 通り)にして、$[CD],E,F$ の $3$ つを並べる($3!=6$)。その $4$ か所の隙間から $2$ か所へ $A,B$ を入れて離すと $4\times 3=12$ 通り。$CD$ が隣り、かつ $AB$ が離れる並びは $2\times 6\times 12=144$ 通り。

引いて

$$480-144=336.$$

包除でまとめて出す本解と同じ $336$ 通りになる。隙間に入れて隣接を断つ道具でも、同じ答えにたどり着く。