数学A 第1章場合の数 — 部屋割り

この節の前提順列／重複順列

例えば、5人の人が鶴の間、亀の間、松の間の3つの部屋に泊まる場合、部屋を割り当てる方法（空部屋はでないようにする）には何通りの方法があるだろうか。このような問題は、人を「区別するボール」、部屋を「区別する箱」として、ボールと箱のモデルで考えることができる。

ボール・箱	単射	写像全て	全射
あり・あり	順列	重複順列	部屋割り
なし・あり	組合せ	重複組合せ	資源配分
あり・なし		（右枠の和）	部屋割り（区別なし）
なし・なし		（右枠の和）	資源配分（区別なし）

部屋割りの数

ボールと箱のモデル3

ボールと箱のモデルを使って

「区別する5個のボールを、区別する3個の箱に最低1個は配る場合の数」を考えてみよう。

準備として、ボールは区別するので番号をつけ、それを①、②、③、④、⑤とし、箱も区別するので番号をつけ、それを

下にそれぞれ1、2、3の番号が書かれた、3つの四角い枠が横一列に並んでいる。それぞれの枠の中は空で、枠と枠の間にはカンマが置かれている。

としておく。

集合 $A, B, C, U$ をそれぞれ

$A$ ：

が空になる

$B$ ：

が空になる

$C$ ：

が空になる

$U$ ：ボールを適当に箱にしまう場合（空・重複有り）

とおくと、『最低1個は配る』は『どの箱も空にならない』ということだから、全体から『どれかの箱が空になる場合』を除いて、求めるものは $n(U)-n(A\cupB\cupC)$ である。

$n(U)=3⁵$ ←重複順列 $3Π5$

$n(A)=n(B)=n(C)=2⁵$ ←指定した1つの箱が空になる場合

$n(A\capB)=n(B\capC)=n(C\capA)=1$ ←指定した2つの箱が空になる場合

$n(A\capB\capC)=0$ ←全部の箱が空になる場合

であるから、包含と排除の原理を使って

$n(U)-n(A\cupB\cupC) = n(U)-{n(A)+n(B)+n(C)-n(A\capB) -n(B\capC)-n(C\capA)+n(A\capB\capC)} = n(U)-n(A)-n(B)-n(C)+n(A\capB) +n(B\capC)+n(C\capA)-n(A\capB\capC) = 3⁵-3・2⁵+3-0 = 150$

通りとなる。

ここで、ボールを箱へこのように配る方法を定義しておく。

1から5の番号がついた5つのボールが、1から3の番号がついた3つの箱に配られて、箱1に4、箱2に1と3、箱3に2と5が入る様子が矢印で示されている。

定義1部屋割りの数room(n,r)の定義

「区別するn個のボールを、区別するr個の箱に（空の箱がないように）最低1個は配る場合の数」を、 $FTEXT$ では $room(n, r)$ と表す。

この例では、 $room(5, 3)=150$ である。

ボール全体の集合 $X$ （ $n$ 個）から箱全体の集合 $Y$ （ $r$ 個）への写像を、『各ボールに、そのボールを入れた箱を対応させる』と考えると、どの箱にも最低1個入ることは、 $Y$ のどの要素にも矢印が向かうこと、すなわち全射であることと同じである。よって $room(n, r)$ は $X$ から $Y$ への全射のパターンの総数と等しい。

★包含と排除の原理の一般形

包含と排除の原理（一般の場合）

1から $r$ までの $r$ 個の自然数の集合 ${1, 2, \dots, r}$ から $k$ 個の要素をとってきて、小さいものから順に並び換えた組

$個 (i1, i2, i3, \dots, ikk個)$

を作るとする。このとき、この組の作り方は全部で $rCk$ 通りあるが、そのすべてに関して次の例のような和を考え $Σ$ と表すことにする。

例えば、 $k = 1$ の例 $Σ2^i1$ は

$Σ2^i1=2¹+2²+2³+\dots+2^(r-1)+2^r$

を意味し、 $r = 4, k = 2$ の例 $Σai1ai2$ は

$Σai1ai2= a1a2+a1a3+a1a4 +a2a3+a2a4+a3a4$

を意味している

この記号を用いると、 $r$ 個の集合 $A1,A2,A3,\dots,Ar$ の和集合 $A1\cupA2\cup\dots\cupAr$ の要素の個数に関して、次の式が成り立つ。

$n(A1\cupA2\cup\dots\cupAr) = Σn(Ai1)-Σn(Ai1\capAi2)+\dots+ (-1)^r-1Σn(Ai1\capAi2\cap\dots\capAir)$

この式が包含と排除の原理の一般形である。

部屋割りの数 $room(m,r)$ の計算

一般の部屋割りの数 $room(m,r)$ は、包含と排除の原理の一般形を用いて、次のように計算できる。

箱 $i$ が空になる場合の集合を $Ai (i=1, 2, \dots, r)$ 、ボールを適当に箱にしまう場合（空・重複有り）の全体を $U$ とおく。先の5個・3箱の例と同じである。このとき、求めるものは $n(U)-n(A1\cupA2\cup\dots\cupAr)$ であり、 $n(U)=r^m$ （重複順列 $rΠm$ ）である。

また、 $Ai1\capAi2\cap\dots\capAik$ は、指定した $k$ 個の箱が空になる場合であるから、残り $r-k$ 個の箱に $m$ 個のボールを自由に入れて $(r-k)^m$ 通りである。指定の仕方は $rCk$ 通りあるので

$Σn(Ai1\cap\dots\capAik)=rCk(r-k)^m$

となる。これらを使って計算すると

$room(m, r) = n(U)-n(A1∪A2∪A3∪…∪Ar) = n(U)-{Σn(Ai1)-Σn(Ai1∩Ai2) +Σn(Ai1∩Ai2∩Ai3)-… +(-1)^r-1Σn(Ai1∩Ai2∩…∩Air)} = n(U)-Σn(Ai1)+Σn(Ai1∩Ai2) -Σn(Ai1∩Ai2∩Ai3)+… -(-1)^r-1Σn(Ai1∩Ai2∩…∩Air) = r^m-rC1(r-1)^m+rC2(r-2)^m -rC3(r-3)^m+…+(-1)^rrCr(r-r)^m = Σ(-1)^krCk(r-k)^m$

まとめておこう

定理2部屋割りの数 $room(n,r)$ の計算

部屋割りの数 $room(n, r)$ は

$room(n, r)=Σ(-1)^krCk(r-k)^n =r!Σ(-1)^k(r-k)^n/(r-k)!k!$

と計算できる。

撹乱順列

『部屋割り』とは異なるが、『包含と排除の原理』の応用として次の問題を考えてみよう。どの人も自分自身のものに当たらないような配り方を撹乱順列という。

問題1撹乱順列

4人の友達A、B、C、Dがクリスマスパーティーでプレゼントを交換する。自分自身の持ってきたプレゼントに誰も当たらないようになるのは何通りの分け方があるか求めよ。

解答を見る

解答1：包含と排除の原理

$U$ ：プレゼントの分け方のすべて

$A$ ：A君が自分自身のプレゼントをもらう

$B$ ：B君が自分自身のプレゼントをもらう

$C$ ：C君が自分自身のプレゼントをもらう

$D$ ：D君が自分自身のプレゼントをもらう

と集合をおくと

$n(U)=4!$ ←4人に1つずつ配る順列 $4P4$

$n(A)=n(B)=n(C)=n(D)=3!$ ←指定した1人が自分のプレゼントをもらい、残り3人には自由に配る場合

$n(A\capB)=n(A\capC)=\dots=2!$ ←指定した2人が自分のプレゼントをもらう場合

$n(A\capB\capC)=\dots=1!$ ←指定した3人が自分のプレゼントをもらう場合

$n(A\capB\capC\capD)=0!$ ←4人全員が自分のプレゼントをもらう場合

であり、人の指定の仕方はそれぞれ $4C1$ 、 $4C2$ 、 $4C3$ 、 $4C4$ 通りあるから

$n(U)-n(A\cupB\cupC\cupD) = n(U)-{n(A)+n(B)+n(C)+n(D) -n(A\capB)-n(A\capC)-n(A\capD) -n(B\capC)-n(B\capD)-n(C\capD) +n(A\capB\capC)+n(A\capB\capD) +n(A\capC\capD)+n(B\capC\capD) -n(A\capB\capC\capD)} = 4!-{ 4C1(4-1)!- 4C2(4-2)! + 4C3(4-3)!- 4C4(4-4)!} = 4!(1/0!-1/1!+1/2!-1/3!+1/4!) = 4!-4・3!+6・2!-4・1!+1 = 9$

通り

解答2：漸化式を使う

$n$ 人のプレゼント交換において、自分自身の持ってきたプレゼントに誰も当らない場合の数を $D(n)$ とする。

いま、 $D(4)$ は次の3つに場合分けできる。

A君がB君のプレゼントに当る
A君がC君のプレゼントに当る
A君がD君のプレゼントに当る

1.～3. は対称的なので、以下は 1.（A君がB君のプレゼントに当る場合）についてだけ考える（のち4 − 1 = 3倍すればよい）。

プレゼントを小文字のアルファベットで表すとして、“A君のプレゼントaをbと考えて”、残りの3人へのプレゼントの配り方を考えると、B君にbが当るかどうかで

B君にb（本当はa）を配り、残りC、D君に自分自身のプレゼントが当らないように配る
B、C、D君に自分自身のプレゼントが当らないように配る（見かけの上ではあるが、B君にbが配られない場合を考える）

の2通りに場合分けできる。ここで1. は $D(2)$ 、2. は $D(3)$ に他ならない。つまり $D(4)$ は

$D(4)=(4-1){D(3)+D(2)}$

で計算できる。同じ考え方で、 $n≧3$ のとき

$D(n)=(n-1){D(n-1)+D(n-2)}$

が成り立つ。また、1人だけなら必ず自分のプレゼントに当るので $D(1)=0$ 、2人ならお互いに交換する1通りだけなので $D(2)=1$ である。よって

$D(4)= (4-1){D(3)+D(2)} = 3D(3)+3D(2) = 3[2{D(2)+D(1)}]+3D(2) = 9D(2)+6D(1) = 9D(2)+0 = 9・1 = 9$

通り

最終更新: 2026-09-03

この節についてAIに質問する

この節に書かれている内容だけを根拠に答えます。個人情報は書かないでください。

質問の内容

数学A 第1章 場合の数 — 部屋割り

部屋割りの数

ボールと箱のモデル3

定義1部屋割りの数room(n,r)の定義

★包含と排除の原理の一般形

包含と排除の原理（一般の場合）

部屋割りの数room(m,r)の計算

定理2部屋割りの数 room(n,r) の計算

撹乱順列

問題1撹乱順列

この節についてAIに質問する

数学A 第1章場合の数 — 部屋割り

部屋割りの数 $room(m,r)$ の計算

定理2部屋割りの数 $room(n,r)$ の計算