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

部屋割りの数

ボールと箱のモデル3

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

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

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

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

としておく．

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

$A$ ：

が空になる

$B$ ：

が空になる

$C$ ：

が空になる

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

とおくと，求めるものは $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$ である．

$room(n, r)$ は $n$ 個の要素をもつ集合 $A$ から， $r$ 個の要素をもつ集合 $B$ への全射のパターンの総数と等しい．

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

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

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)$ は，包含と排除の原理の一般形を用いて，次のように計算できる．

$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)-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君のプレゼントに当る

i. ～iii. は対称的なので，以下i. についてだけ考える（のち4 − 1 = 3倍すればよい）．

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

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$ が自然数で一般的に成り立つから

$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-08-10

この節について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)$ の計算