個数定理　　　　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　戻る

　有限集合 Ａ の要素の個数 ｎ（Ａ） に関する次の個数定理は、高校１年で学ぶ数学Ａの中
でも最重要公式と呼べるものだろう。これらの公式をもとに、確率の加法定理が示される。

　　　ｎ（Ａ∪Ｂ）＝ｎ（Ａ）＋ｎ（Ｂ）−ｎ（Ａ∩Ｂ）

　　　ｎ（Ａ∪Ｂ∪Ｃ）＝ｎ（Ａ）＋ｎ（Ｂ）＋ｎ（Ｃ）
　　　　　　　　　　　　　　　　　−ｎ（Ａ∩Ｂ）−ｎ（Ｂ∩Ｃ）−ｎ（Ｃ∩Ａ）＋ｎ（Ａ∩Ｂ∩Ｃ）

　ベン図等を用いて、この等式は視覚的に容易に了解されることだろう。

　　　　　　 　　　　　　

　上式は、何れも Ａ、Ｂ、・・・　の何れかの性質を持つものの個数を求める定理であるが、
問題によっては、これらの性質を全く持たないものの個数を求めたいという場合がある。

　これについては、全体集合を Ｕ とすると、補集合の考えを用いて、

　　ＡでもＢでもないものの個数は、

　　　　　ｎ（Ｕ）−ｎ（Ａ∪Ｂ）＝ｎ（Ｕ）−ｎ（Ａ）−ｎ（Ｂ）＋ｎ（Ａ∩Ｂ）

　　ＡでもＢでもＣでもないものの個数は、

　　　　　ｎ（Ｕ）−ｎ（Ａ∪Ｂ∪Ｃ）

　　　＝　ｎ（Ｕ）−ｎ（Ａ）−ｎ（Ｂ）−ｎ（Ｃ）
　　　　　　　　　　　　　　　　　＋ｎ（Ａ∩Ｂ）＋ｎ（Ｂ∩Ｃ）＋ｎ（Ｃ∩Ａ）−ｎ（Ａ∩Ｂ∩Ｃ）

と求められる。

　ｋ 個の集合 Ｅ1、Ｅ2、・・・、Ｅｋ　に対して、性質 Ｅｍ を持つ要素の個数を　ｎ（Ｅｍ）＝Ｎｍ

とし、　ｎ（Ｕ）＝Ｎ　、ｎ（Ｅ1∩Ｅ2）＝Ｎ12　、ｎ（Ｅ1∩Ｅ2∩Ｅ3）＝Ｎ123　、　・・・・　等とすれば、

上記の２式は次のように書き直すことができる。

　　　　性質 Ｅ1、Ｅ2　を全く持たないものの個数は、

　　　　　　　　　　　Ｎ−Ｎ1−Ｎ2＋Ｎ12

　　　　性質 Ｅ1、Ｅ2、Ｅ3　を全く持たないものの個数は、

　　　　　　　　　　　Ｎ−Ｎ1−Ｎ2−Ｎ3＋Ｎ12＋Ｎ23＋Ｎ31−Ｎ123

　この等式を一般化すれば、次の定理が得られる。

定　理　　性質 Ｅ1、Ｅ2、・・・、Ｅｋ　を全く持たないものの個数は、

　　　　　　　　 Ｎ−ΣＮａ＋ΣＮａｂ−ΣＮａｂｃ＋・・・＋（−１）ｋＮ123・・・ｋ

　この公式は、「包含と排除の原理（包除原理）」（Principle　of　Inclusion　and　Exclusion）
と呼ばれる。

　性質 Ｅ1、Ｅ2、・・・、Ｅｋ　を全く持たないものの個数を直接的に求めることは難しいが、い
ろいろな性質を持つ場合の数を計算した方が易しい場合がある。そんな状況に、この包除
原理が大活躍するわけである。

例　３人 ａ 、ｂ、ｃ　を、２組 Ａ、Ｂ に分けたい。何通りあるだろうか？

　　中学校レベルでは次のように場合を尽くして数え上げるのだろう。

　
Ａ Ｂ
１ ａｂ ｃ
２ ａｃ ｂ
３ ｂｃ ａ
４ ａ ｂｃ
５ ｂ ｃａ
６ ｃ ａｂ
　　　左表より、

　　求める場合の数は、

　　　　６通り

　　高校レベルでは、組合せの公式を用いて、場合の数を求めるのだろう。

　　　　3Ｃ2・1Ｃ1＋3Ｃ1・2Ｃ2＝３＋３＝６（通り）

　また、重複順列の考えを用いても場合の数は求められる。

　　異なる２個のものから重複を許して３個取る順列の総数は、　２3＝８（通り）

　　この中には、３人全員がＡ、または、３人全員がＢ　の場合が含まれる。

　　　よって、求める場合の数は、　８−２＝６（通り）


　この重複順列の考えを一般化したものが包除原理を用いた解答となる。

　　３人を２つの部屋　１ と ２　に振り分ける。

　そのときの振り分け方の総数は、　Ｎ＝２3＝８（通り）　である。

　　性質 Ｅ1 は部屋 １ が空室である場合、性質 Ｅ2　は部屋 ２ が空室である場合とする。

　このとき、求める場合の数は、包除原理より、　Ｎ−Ｎ1−Ｎ2＋Ｎ12　で求められる。

　　ところで、　Ｎ1＝１　、Ｎ2＝１　、Ｎ12＝０　なので、

　求める場合の数は、　８−１−１＋０＝６（通り）　となる。

例　４人 ａ 、ｂ、ｃ、ｄ　を、３組 Ａ、Ｂ、Ｃ に分けたい。何通りあるだろうか？

　４人を３つの部屋　１ と ２ と ３　に振り分ける。

　そのときの振り分け方の総数は、　Ｎ＝３4＝８１（通り）　である。

　　性質 Ｅｍ （ｍ＝１、２、３）は部屋 ｍ が空室である場合とする。

　このとき、求める場合の数は、包除原理より、

　　　　　　Ｎ−Ｎ1−Ｎ2−Ｎ3＋Ｎ12＋Ｎ23＋Ｎ31−Ｎ123

　で求められる。ところで、

　　　Ｎ1＝Ｎ2＝Ｎ3＝２4＝１６　、Ｎ12＝Ｎ23＝Ｎ31＝１　、Ｎ123＝０　なので、

　求める場合の数は、　８１−１６×３＋１×３−０＝３６（通り）　となる。


　　（追記）　平成２６年２月２２日付け

　　　　今まで組み分けの問題というと、だいたい３組までが相場であったが、東京理科大学
　　薬学部（２０１４）の入試問題で、４組に分ける場合が出題された。いよいよ「包含と排除
　　の原理（包除原理）」が大学入試の基本テクニックになる日が近づいてきたのだろうか。

　　　ｒは２以上９以下の自然数とする。ｎをｒ以上の自然数として、次の条件を満たすｎ桁の
　　自然数を考える。

　　　（イ）各位の数は１からｒまでの数　１、２、・・・、ｒ　のどれかである。
　　　（ロ）１、２、・・・、ｒのどの一つも必ずどこかの位に現れる。

　　　このような自然数全体の集合を考え、この集合の要素の個数を ｒＳｎ とおく。また、この
　　集合のすべての要素の和を ｆｒ（ｎ）とおく。

　　　（１）　ｒ＝２とする。
　　　　　（ａ）　2Ｓ2 、 2Ｓ3 を求めよ。また、2Ｓｎ を求めよ。
　　　　　（ｂ）　ｆ2（２）、ｆ2（３）を求めよ。また、ｆ2（ｎ）を2Ｓｎ を用いて表せ。

　　　（２）　ｒ＝３とする。
　　　　　（ａ）　3Ｓｎ を求めよ。
　　　　　（ｂ）　ｆ3（ｎ）を3Ｓｎ を用いて表せ。

　　　（３）　ｒ＝４とする。
　　　　　（ａ）　4Ｓｎ を求めよ。
　　　　　（ｂ）　ｆ4（ｎ）を4Ｓｎ を用いて表せ。

　　（解）

　　　（１）　ｒ＝２のとき、（イ）（ロ）を満たすｎ桁（ｎ≧２）の自然数の個数が 2Ｓｎ である。
　　　　（ａ）　ｎ＝２　のとき、　12　、21　なので、　2Ｓ2＝２
　　　　　　　ｎ＝３　のとき、　112　、121　、211　、122　、212　、221　なので、　2Ｓ3＝６
　　　　　2Ｓｎ は、異なるｎ個のものをＡ、Ｂの２組（各組は１個以上）に分ける場合の数に等
　　　　しいので、　2Ｓｎ＝２ｎ−２

　　　　（ｂ）　（ａ）より、　ｆ2（２）＝12＋21＝３３
　　　　　　ｆ2（３）＝112＋121＋211＋122＋212＋221
　　　　　　　　　 ＝３（100＋200）＋３（10＋20）＋３（1＋2）＝９９９

　　　　　一般に、ｆ2（ｎ）＝（2Ｓｎ/２）（3＋30＋300＋3000＋・・・＋300・・・00）
　　 　　　　　　　　　　　＝（2Ｓｎ/２）・３（１０ｎ−１）/９＝（1/6）（１０ｎ−１）2Ｓｎ

　　　（２）　ｒ＝３のとき、（イ）（ロ）を満たすｎ桁（ｎ≧３）の自然数の個数が 3Ｓｎ である。
　　　　（ａ）　3Ｓｎ は、異なるｎ個のものをＡ、Ｂ、Ｃの３組（各組は１個以上）に分ける場合の
　　　　　　数に等しいので、3Ｓｎ＝３ｎ−｛３（２ｎ−２）＋３｝＝３ｎ−３・２ｎ＋３
　　　　（ｂ）　ｆ3（ｎ）＝（3Ｓｎ/３）（6＋60＋600＋6000＋・・・＋600・・・00）
　　　　　　　　　　　＝（3Ｓｎ/３）・６（１０ｎ−１）/９＝（2/9）（１０ｎ−１）3Ｓｎ

　　　（３）　ｒ＝４のとき、（イ）（ロ）を満たすｎ桁（ｎ≧４）の自然数の個数が 4Ｓｎ である。
　　　　（ａ）　4Ｓｎ は、異なるｎ個のものをＡ、Ｂ、Ｃ、Ｄの４組（各組は１個以上）に分ける場合
　　　　　　の数に等しいので、

　　　　　　　4Ｓｎ＝４ｎ−｛4Ｃ1・（３ｎ−３・２ｎ＋３）＋4Ｃ2・（２ｎ−２）＋４｝
　　　　　　　　　 ＝４ｎ−４・３ｎ＋１２・２ｎ−１２−６・２ｎ＋１２−４＝４ｎ−４・３ｎ＋６・２ｎ−４
　　　　（ｂ）　ｆ4（ｎ）＝（4Ｓｎ/４）（10＋100＋1000＋10000＋・・・＋1000・・・00）
　　　　　　　　　　　＝（4Ｓｎ/４）・１０（１０ｎ−１）/９＝（5/18）（１０ｎ−１）4Ｓｎ


例　（出合いの問題または手紙と封筒の問題）・・・モンモール（１７０８年）
　　　　　　　　　　　　　　　　　　　　　　　　　　　（ → 参考 ： 「自然対数の底 ｅ の体感」 ）

　　　１ から ｎ までの自然数の書かれたカードが ｎ 枚
　　ある。今そのカードをよく切って、左図のように番号
　　順に置いていく。
　　　もし、
　　　　　　　　　ａｋ＝ｋ

となるような ｋ が存在するとき、「出合い」が起こったといわれる。

　このとき、「出合いが起こらない確率」はいくつになるであろうか？

　この問題は、「自然対数の底 ｅ の体感」においては、次のように解かれた。

　出合いが起こらない場合の数を Ｆ(ｎ) とおくと、Ｆ(ｎ) について漸化式

　　　　　　Ｆ(ｎ)＝（ｎ−１）（Ｆ(ｎ−１)＋Ｆ(ｎ−２)）

が成り立つ。　明らかに、Ｆ(１)＝０、Ｆ(２)＝１ である。

このとき、 Ｆ(ｎ)−ｎＦ(ｎ−１)＝−（Ｆ(ｎ−１)−（ｎ−１）Ｆ(ｎ−２)） ＝・・・＝（−１）ｎ　から、

　　　　　　　

と変形できるので、
　　　　　　　　　　　　

さらに、Ｆ(１)＝０ なので、
　　　　　　　　　　　　　　　　
となる。

　したがって、
　　　　　　　　

　上記では、かなり大変な計算をしてＦ(ｎ) を求めているが、包除原理を用いるとごく自然に
上式が得られる。実際に求めてみよう。

　１ から ｎ までの自然数の書かれたカードをよく切って並べる場合の数の総数は、

　　　Ｎ＝ｎ！（通り）

である。また、性質 Ｅｍ （ｍ＝１、２、・・・、ｎ）は、　ａｍ＝ｍ　である場合とする。

　このとき、　Ｎｍ個の要素＝（ｎ−ｍ）！（通り）　なので、包除原理より、

　　Ｆ(ｎ)＝Ｎ−ΣＮａ＋ΣＮａｂ−ΣＮａｂｃ＋・・・＋（−１）ｎＮ123・・・ｎ

　　　 　＝ｎ！−ｎＣ1・（ｎ−１）！＋ｎＣ2・（ｎ−２）！−・・・＋（−１）ｎ

　　　 　＝ｎ！−ｎ！/１！＋ｎ！/２！−・・・＋（−１）ｎ

　　　 　＝ｎ！（１−１/１！＋１/２！−・・・＋（−１）ｎ/ｎ！）

　すなわち、
　　　　　　　　

であることが示された。

（コメント）　今まで、「手紙と封筒の問題」というと、漸化式を解く場合しか知りませんでした
　　　　　　が、こんなに軽妙に求められることに驚きました。包除原理の偉大さがよ〜く分
　　　　　　かりました．．． ｆ(^^;) 。

例　赤、青、黄の３色の球がそれぞれ大小１個ずつ合計６個ある。これらの球を一列
　　に並べるとき、同じ色の球が隣り合わないように並べたい。並べ方は全部で何通
　　りあるだろうか。

　普通に考えれば、次のように求められる。

　まず、大小の赤球を一列に並べる場合の数は、　２！＝２（通り）

　その１通り、例えば　× ● × ● ×　に対して、大小２個の青球を×印に入れる場合の

数は、　3Ｐ2＝３×２＝６（通り）

　その１通り、例えば　× ● × ● × ● × ●×　に対して、大小２個の黄球を×印に入

れる場合の数は、　5Ｐ2＝５×４＝２０（通り）

　したがって、求める場合の数は、　２×６×２０＝２４０（通り）


　これに対して、包除原理を用いると、次のように求められる。

　６個の球を一列に並べる場合の数は、　Ｎ＝６！＝７２０（通り）　である。

また、　性質　Ｅｒ ： 大小の赤球が隣り合っている

　　　　 性質　Ｅｂ ： 大小の青球が隣り合っている

　　　　 性質　Ｅｙ ： 大小の黄球が隣り合っている

とする。このとき、　Ｎｒ＝Ｎｂ＝Ｎｙ＝２！×５！＝２４０（通り）

　　Ｎｒｂ＝Ｎｒｙ＝Ｎｂｙ＝２！×２！×４！＝９６（通り）

　　Ｎｒｂｙ＝２！×２！×２！×３！＝４８（通り）

であるので、包除原理より、求める場合の数は、

　　　７２０−３×２４０＋３×９６−４８＝２４０（通り）　となる。

（コメント）　色数が少ないので、普通の解答の方が易しく感じるが、もっと色数が多い場合
　　　　　　は、包除原理の方が易しく感じられるだろう。

例　オイラー関数 φ（ｎ）

　自然数 ｎ と互いに素な自然数の個数を表すオイラー関数も包除原理の適当な例になっ
ている。

　自然数 ｎ が素因数分解されて、　ｎ＝ｐａｑｂ・・・ｒｃ　と書けるとき、

　　　　φ（ｎ）＝ｎ（１−１/ｐ）（１−１/ｑ）・・・（１−１/ｒ）

と書ける。

　素数 ｐ に対して、ｐ と互いに素な自然数は、　１、２、・・・、ｐ−１　の　ｐ−１個あるので、

　　　φ（ｐ）＝ｐ−１＝ｐ（１−１/ｐ）

　素数 ｐ に対して、１ から ｐａ までの自然数のうち、ｐ の倍数になっているものは、

　　ｐ・１　、　ｐ・２　、　・・・・　、　ｐ・ｐａ-1

の ｐａ-1 個あるので、ｐａ と互いに素な自然数は、 φ（ｐ）＝ｐａ−ｐａ-1＝ｐａ（１−１/ｐ） 個あ

る。このことから、上記の φ（ｎ）の式が成り立つことは予想されよう。

　証明は、包除原理を用いると容易だろう。

　１ から ｎ までの自然数の総数は、　Ｎ＝ｎ　（個）　である。

また、性質 Ｅｐ は、ｐ の倍数になっている場合

　　　 性質 Ｅｑ は、ｑ の倍数になっている場合

　　　　　・・・・・・・・・・・・・・・・・・・・・・・・・・・・

　　　 性質 Ｅｒ は、ｒ の倍数になっている場合

とする。

　このとき、　Ｎｐ＝ｎ/ｐ　、Ｎｑ＝ｎ/ｑ　、・・・　、Ｎｒ＝ｎ/ｒ　、Ｎｐｑ＝ｎ/ｐｑ　、・・・・　なので、

包除原理より、

　　φ(ｎ)＝Ｎ−ΣＮｐ＋ΣＮｐｑ−・・・±Ｎｐｑ・・・ｒ

　　　 　＝ｎ−ｎ（１/ｐ＋１/ｑ＋・・・＋１/ｒ）＋ｎ（１/ｐｑ＋・・・）−・・・±ｎ/ｐｑ・・・ｒ

　　　　 ＝ｎ（１−１/ｐ）（１−１/ｑ）・・・（１−１/ｒ）

であることが分かる。

　たとえば、　φ（２）＝２（１−１/２）＝１

　　　　　　　　　　実際に、　２ と互いに素な自然数は、　１ の１個

　　　　　　　　φ（３）＝３（１−１/３）＝２

　　　　　　　　　　実際に、　３ と互いに素な自然数は、　１、２ の２個

　　　　　　　　φ（４）＝４（１−１/２）＝２

　　　　　　　　　　実際に、　４ と互いに素な自然数は、　１、３ の２個

　　　　　　　　φ（５）＝５（１−１/５）＝４

　　　　　　　　　　実際に、　５ と互いに素な自然数は、　１、２、３、４ の４個

　　　　　　　　φ（６）＝６（１−１/２）（１−１/３）＝２

　　　　　　　　　　実際に、　６ と互いに素な自然数は、　１、５ の２個

　　　　　　　　　　・・・・・・・・・・・・・・・・・・・・・・・

例　外見上全く区別のできない箱がいくつかあり、それぞれの箱の中には同様な確か
　　らしさで、ｋ種類（ ｋ≦ｎ ）の図形のうちのどれか一つが入っているという。
　　　この箱を ｎ個（ ｎ≧ｋ ）用意するとき、ｋ種類の図形が全種類揃う確率を求めよ。

　　まず、起こり得る全ての場合の数は、　Ｎ＝ｋｎ （通り）　である。

　ｋ 種類の図形の名前を、　１、２、３、・・・、ｋ　として、

　性質 Ｅｍ （ｍ＝１、２、３、・・・、ｋ）は、図形 ｍ が揃わない場合

とする。このとき、ｋ 種類の図形が全種類揃う場合の数は、包除原理から、

　　　ｋｎ−ｋＣ1（ｋ−１）ｎ＋ｋＣ2（ｋ−２）ｎ＋・・・＋（−１）ｋ-1ｋＣｋ-1１ｎ

　したがって、求める確率は、

　　　１−ｋＣ1（１−１/ｋ）ｎ＋ｋＣ2（１−２/ｋ）ｎ＋・・・＋（−１）ｋ-1ｋＣｋ-1（１/ｋ）ｎ

（コメント）


　　　ｋ＝５　の場合を実験してみよう。

　　　確率は、

　　１−５（４/５）ｎ＋１０（３/５）ｎ−１０（２/５）ｎ＋５（１/５）ｎ　である。

　　Ｅｘｃｅｌ さんに、ｎ＝５、６、・・・、３０　について確率の値を計算

　　してもらったのが左表である。

　　左図の計算結果によれば、ｎ＝３０ のときの確率が ９９．４％

　　となり、かなり高い確率で全種類揃うことになる。

　　　因みに、　ｎ＝６０ 　のとき、確率は、９９．９９９％で、これは

　　ほぼ確実と言ってもいいかな？

　　　ｎ＝１００　のときは、確率　９９．９９９９９９９％である。
　この例について、当ＨＰがいつもお世話になっているＨＮ「ｚｋ４３」さんより、アドバイスを頂
いた。（平成２１年１０月３０日付け）

　少し視点を変えて、

　　「全 ｋ 種類の図形を集めるための箱の個数の平均値はいくらか？」

という問題ではどうでしょうか？

　ｍ種類（０≦ｍ≦ｋ−１）の図形が初めて集まったという段階で、次に箱を１個用意したとき、

その中にまだ集めていない新しい種類の図形がある確率は、　１−ｍ/ｋ　であるから、新し

い種類の図形を集めるまでに用意しなければならない箱の個数 Ｘ は、

　パラメータ　ｐ＝１−ｍ/ｋ　の幾何分布　Ｐ（Ｘ＝ ｔ ）＝ｐ・（１−ｐ）ｔ-1　　（ｔ＝１、２、３、・・・）

に従う。よって、　Σ（１−ｐ）ｔ＝（１−ｐ）/ｐ　より、　Σｔ・（１−ｐ）ｔ-1＝１/ｐ2　なので、

その期待値 Ｅ（Ｘ） は、　１/ｐ＝ｋ/（ｋ−ｍ）　である。

　よって、求める箱の個数の期待値は、これらを加えて、

　　　１＋ｋ/（ｋ−１）＋ｋ/（ｋ−２）＋・・・＋ｋ/２＋ｋ/１

　　＝ｋ（１/ｋ＋１/（ｋ−１）＋１/（ｋ−２）＋・・・＋１/２＋１/１）

　　＝ｋ（１＋１/２＋１/３＋・・・＋１/ｋ）

となる。

（コメント）　確かに、何箱か用意して全種類の図形が揃う確率を求めるよりも、全種類の図
　　　　　　形が揃うには大体何箱用意すればいいかを考える方が現実的で興味があります
　　　　　　ね！ｚｋ４３ さんに感謝します。

　　因みに、　ｋ＝５　のとき、箱の個数の期待値は、

　　　　　５（１＋１/２＋１/３＋１/４＋１/５）＝１３７/１２＝１１．４・・・

　　以上から、図形の種類が５種類であるとき、１１〜１２個の箱を用意すれば、目的が達せ
　られることが期待できる。


（追記）　平成２２年１１月２１日付け

　１１月２０日付けで、上記の例に関して、Ｈ．Ｙ．さんよりメールをいただいた。

　上記の例の問題を見て、それまでわからなかった問題が解けました。もしよろしかったら、

　　　　　　「ガチャポンを全種類集めるには」

を読んでみて下さい。わからなかった問題というのは「コマ大数学科」という番組で出た

　10種類のくじを全部引き当てるには何回くじを引けばよいか期待値を求めなさい

という問題で、上記の問題がヒントになりました。

（コメント）　問題解決に当ＨＰが役立ったということで嬉しい限りです。「コマ大数学科」から
　　　　　　は以前問題使用依頼が来たことがあったのですが、もしかしてこの問題だったの
　　　　　　かな．．．？

　ところで、上記のＨＰサイトによると、「コマ大数学科」では次のように解かれていたという。

（１）   ｋ−１種類まで集まった時点で、次に、ｋ種類目が出る確率は、ａｋ＝１−（ｋ−１）/１０

（２）　ｋ種類目が出るまでには、平均して、１/ａｋ 回かかる。
　　（→例えば、さいころを投げて１の目が出る確率は１/６なので、その逆数の６回投げれば１の目が
　　　　出ることが期待できる。）

（３）　従って、全種類出るまでには、平均して、Σ１/ａｋ 回かかる。

　このように考えると、上記の計算で得られた「求める箱の個数の期待値を表す式」

　　　１＋ｋ/（ｋ−１）＋ｋ/（ｋ−２）＋・・・＋ｋ/２＋ｋ/１

　　＝１/（１−０/ｋ）＋１/（１−１/ｋ）＋１/（１−２/ｋ）＋・・・
　　　　　　　　　　　　　　　　　　　　　　　　　　＋１/（１−（ｋ−２）/ｋ）＋１/（１−（ｋ−１）/ｋ）

の意味が明瞭に浮き彫りになってきますね！Ｈ．Ｙ．さんに感謝します。


　以上のいくつかの例を見ても分かるように、包除原理は見た目よりも豊かな応用を持って
いることが分かる。

　「包除原理はいろいろな場面に応用できそうで面白いですね。」と、ｚｋ４３さん。私も同感
です！　さて、先延ばしにしてきた包除原理の証明に取りかかろう。

　２個の集合についての個数定理　ｎ（Ａ∪Ｂ）＝ｎ（Ａ）＋ｎ（Ｂ）−ｎ（Ａ∩Ｂ）　を出発点として、

３個の集合についての個数定理

　　　ｎ（Ａ∪Ｂ∪Ｃ）＝ｎ（Ａ）＋ｎ（Ｂ）＋ｎ（Ｃ）
　　　　　　　　　　　　　　　　　−ｎ（Ａ∩Ｂ）−ｎ（Ｂ∩Ｃ）−ｎ（Ｃ∩Ａ）＋ｎ（Ａ∩Ｂ∩Ｃ）

が成り立つことは容易に示される。同様にして、

　　　ｎ（Ａ∪Ｂ∪Ｃ∪Ｄ）、ｎ（Ａ∪Ｂ∪Ｃ∪Ｄ∪Ｅ）、・・・・・・

も個別に地道に展開すれば、等式を作ることは容易である。ただ、この方法では包除原理

を一般的に示すことは難しい。

　証明の準備として、次のような集合 Ａ に付随する特性関数 Ａ（ｘ） を定義する。

　　ｘ ∈ Ａ　のとき、　Ａ（ｘ）＝１　、　ｘ ∈ Ａ　でないとき、　Ａ（ｘ）＝０

　この特性関数を用いると、集合 Ａ の要素の個数 ｎ（Ａ） は、

　　　　　　　ｎ（Ａ）＝ΣＡ（ｘ）　（ただし、　ｘ ∈ Ｕ）

例　全体集合 Ｕ に対して、常に、　Ｕ（ｘ）＝１　である。

　以下において、全体集合 Ｕ は有限集合であるものとする。

例　空集合 φ に対して、常に、　φ（ｘ）＝０　である。

　　この特性関数を用いると、集合 Ａ の要素の個数 ｎ（Ａ） は、

　　　　　　　ｎ（Ａ）＝ΣＡ（ｘ）　　（ただし、　ｘ ∈ Ｕ）

　で表される。

　　例えば、　ｎ（Ｕ）＝ΣＵ（ｘ）＝Σ１　（Ｕの要素の個数だけ１を加える）

　　　　　　　　ｎ（φ）＝Σφ（ｘ）＝Σ０＝０

例　集合 Ａ の補集合 Ａｃ に対して、

　　　ｘ ∈ Ａ　のとき、　Ａｃ（ｘ）＝０　、　ｘ ∈ Ａ　でないとき、　Ａｃ（ｘ）＝１

　であるので、　Ａｃ（ｘ）＝１−Ａ（ｘ）　が成り立つ。

例　２つの集合 Ａ 、Ｂ の共通部分 Ａ∩Ｂ に付随する特性関数 Ａ∩Ｂ（ｘ） について、

　　ｘ ∈ Ａ∩Ｂ　のとき、　Ａ∩Ｂ（ｘ）＝１　、　ｘ ∈ Ａ∩Ｂ　でないとき、　Ａ∩Ｂ（ｘ）＝０

　であるが、一方、

　ｘ ∈ Ａ∩Ｂ　のとき、　Ａ（ｘ）Ｂ（ｘ）＝１　、　ｘ ∈ Ａ∩Ｂ　でないとき、　Ａ（ｘ）Ｂ（ｘ）＝０

　が成り立つ。よって、　Ａ∩Ｂ（ｘ）＝Ａ（ｘ）Ｂ（ｘ）　が成り立つ。

例　２つの集合 Ａ 、Ｂ の結び Ａ∪Ｂ に付随する特性関数 Ａ∪Ｂ（ｘ） について、

　　ｘ ∈ Ａ∪Ｂ　のとき、　Ａ∪Ｂ（ｘ）＝１　、　ｘ ∈ Ａ∪Ｂ　でないとき、　Ａ∪Ｂ（ｘ）＝０

　であるが、一方、

　ｘ ∈ Ａ∪Ｂ　のとき、　ｘ ∈ Ａｃ∩Ｂｃ　でないので、　Ａｃ（ｘ）Ｂｃ（ｘ）＝０

　　すなわち、　｛１−Ａ（ｘ）｝｛１−Ｂ（ｘ）｝＝０　より、　Ａ（ｘ）＋Ｂ（ｘ）−Ａ（ｘ）Ｂ（ｘ）＝１

　が成り立つ。同様にして、

　ｘ ∈ Ａ∪Ｂ　でないとき、　ｘ ∈ Ａｃ∩Ｂｃ　なので、　Ａｃ（ｘ）Ｂｃ（ｘ）＝１

　　すなわち、　｛１−Ａ（ｘ）｝｛１−Ｂ（ｘ）｝＝１　より、　Ａ（ｘ）＋Ｂ（ｘ）−Ａ（ｘ）Ｂ（ｘ）＝０

　が成り立つ。

　　以上から、　Ａ∪Ｂ（ｘ）＝Ａ（ｘ）＋Ｂ（ｘ）−Ａ（ｘ）Ｂ（ｘ）　が成り立つ。

　このように考えると、集合における演算（補集合、共通部分、結び）が、数における演算
（＋−×）に翻訳できることが分かる。

　また、　Ａｃ∩Ｂｃ（ｘ）＝（Ａ∪Ｂ）ｃ（ｘ）＝１−Ａ∪Ｂ（ｘ）　であるので、

　　Ａｃ∩Ｂｃ（ｘ）＝１−Ａ（ｘ）−Ｂ（ｘ）＋Ａ（ｘ）Ｂ（ｘ）＝｛１−Ａ（ｘ）｝｛１−Ｂ（ｘ）｝

が成り立つ。

　このことから、ｋ 個の集合 Ｅ1、Ｅ2、・・・、Ｅｋ　に対して、

　　　Ｅ1ｃ∩Ｅ2ｃ∩・・・∩Ｅｋｃ（ｘ）

　　＝｛１−Ｅ1（ｘ）｝｛１−Ｅ2（ｘ）｝・・・｛１−Ｅk（ｘ）｝

　　＝１−ΣＥａ（ｘ）＋ΣＥａ（ｘ）Ｅｂ（ｘ）−・・・＋（−１）ｋＥ1（ｘ）Ｅ2（ｘ）・・・Ｅk（ｘ）

が成り立つ。　ここで、集合 Ｅｍ の要素の個数を　ｎ（Ｅｍ）＝Ｎｍ　とし、

　ｎ（Ｕ）＝Ｎ　、ｎ（Ｅ1∩Ｅ2）＝Ｎ12　、ｎ（Ｅ1∩Ｅ2∩Ｅ3）＝Ｎ123　、　・・・・　等とすれば、

上式は次のように書き直すことができる。

　　　性質 Ｅ1、Ｅ2、・・・、Ｅｋ　を全く持たないものの個数

　　＝ Ｎ−ΣＮａ＋ΣＮａｂ−ΣＮａｂｃ＋・・・＋（−１）ｋＮ123・・・ｋ

（コメント）　お世辞にも厳密な証明とはいかないが、包除原理を納得するには十分であろう。


　当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんより、包除原理を用いる確率の問題をい
ただいた。（平成２３年３月２２日付け）

問　題　５２枚のトランプのカードからランダムに１３枚を選びパケットを裏向きに持つ。
　　「１３」と声に出してパケットのトップからカードを一枚表向きにしてテーブルへ出す。
　　号令とカードの数字が異なれば、次に「１２」と発声して次のカードを重ねていく。
　　このように、最後まで「１」の発声とカードの数字が合わずに終わってしまう確率を
　　求めよ。

　この問題に、当ＨＰがいつもお世話になっているＨＮ「ａｔ」さんが取り組まれた。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２３年３月２２日付け）

（解）　５２枚のトランプのカードを左から横一列に並べたとき、左から１３枚のカードのすべ

　　てが号令と一致しないような並べ方を数え上げればよい。

　　　これら１３枚のカードを並べる１３箇所のうち、特定のｋ箇所（０≦ｋ≦１３）にあるカード

　　が号令と一致するような並べ方は、同一数字が４枚あることに注意して、

　　　４ｋ・（５２−ｋ）！ 通り。

　　したがって、１３箇所のうちの ｋ 箇所にあるカードが号令と一致するような５２枚のカード

　　の並べ方は、　13Ｃｋ・４ｋ・（５２−ｋ）！ 通り。

　　　よって、左端から１３枚のカードのすべてが号令と一致しないような並べ方は、包除原

　　理より、
　　　　　　　Σ[k=0〜13]（−１）ｋ・13Ｃｋ・４ｋ・（５２−ｋ）！ 通り。

　　これを、５２！で割ったものが求める確率となる。

　　　求める確率は、

　　　9571721884148096/26816424180170625≒0.35693505665926537249298212905…

　　で、約 ０．３５６９　となる。　　（終）


　ａｔ さんの解に対して、ＧＡＩ さんからのコメントです。（平成２３年３月２３日付け）

　計算有り難うございます。この一致しない１３枚のパケットの山が４つ作れたら（５２枚のす
べてのカード一致せずに終了する。）、その確率は、0.35694＝0.016225・・・（約１％強）と
なるので、これは非常に珍しいことが起きたと思えるわけですね。

　逆に言うと、５２枚もの枚数で試行すれば、必ず号令と一致するカードを出すことができる
訳ですね。


　ａｔ さんからのコメントです。（平成２３年３月３１日付け）

　１組のトランプ５２枚のカードをすべて使って、１３枚ずつのパケットの山を４つ作り、この４
つの山のそれぞれに対して、「１３、１２、１１、・・・」と号令を発しながら、カードのナンバー
を一枚ずつ調べていくのですね。

　このとき、号令とカードのナンバーが全く一致しないような確率は、確かに0.016225ぐらい
になります。ただ、ＧＡＩ さんの計算方法が、0.35694　となっているのが少々気になります。

　５２枚のトランプのカードからランダムに１３枚を選び出し、この１３枚に対し、号令とカード
のナンバーが全く一致しない確率を ｐ1 とします。ｐ1 の値は先に示したように、

　　　　ｐ1 ＝(9571721884148096)/(26816424180170625)=0.3569…

です。

　１組のトランプ５２枚のカードをすべて使って１３枚ずつのパケットの山を４つ作ったとき、
すべての山について、号令と１３枚のカードのナンバーが全く一致しないような確率は ｐ14
ではなく、正確な確率は ｐ14 よりもごくわずかに大きい値になります。

　たとえば、次の問題を考えてみます。

問題　　同じ形をしたカードが全部で８枚あり、各々のカードには正整数が１つだけ記入さ

　　　　れている。「１」が記入されたカードが４枚、「２」が記入されたカードが４枚あるものと

　　　　する。この８枚のカードを、２枚ずつのパケットの山４つに分ける。この４つの山のそ

　　　　れぞれに対して次のような実験を行う。

　　　　　[実験]　　「２」と声に出してパケットのトップからカードを一枚表向きにしてテーブル

　　　　　　　　　へ出す。号令とカードの数字が異なれば、次に「１」と声に出して次のカード

　　　　　　　　　を重ねる。

　　　　この実験において、どの山についても「１」を発声し、なおかつ号令とカードの数字が

　　　全く一致しない確率はいくらか？

　ひとつの山に注目するとき、その山について、「１」を発声し、なおかつ号令とカードの数字
が全く一致しない確率は、

　　　　　｛Σ[k=0〜2]（−１）ｋ・2Ｃｋ・４ｋ・（８−ｋ）！｝/８！＝２/７

です。山は全部で４つあるので、この問題の答えは、（２/７）4 と解答するのは誤りです。

　題意を満たすためには、４つの山それぞれの一番上には「１」と記入されたカードがあり、
一番下には「２」と記入されたカードがあればよいので、それぞれの順列を考えることによ
り、この問題の正答は、　４！４！/８！＝１/７０ となります。

　冒頭の５２枚のトランプのカードの問題ですが、正確な確率 ｐ2 を求める式は、次のように
なります。

　　ｐ2＝【Σ[k=0〜52]（−１）ｋ｛［ｘｋ］（Σ[ｊ=0〜4]4Ｃｊ2・ｊ・ｘｊ）13｝・（５２−ｋ）！】/５２！

(この式の、『［ｘｋ］（Σ[ｊ=0〜4]4Ｃｊ2・ｊ・ｘｊ）13』の部分は、ｘ の多項式（Σ[ｊ=0〜4]4Ｃｊ2・ｊ・ｘｊ）13 を
展開したときの ｘｋ の係数を表しています。)

　この式を使って、ｐ2 を計算すると、

ｐ2＝(4610507544750288132457667562311567997623087869)
　　　　　　　　　　　　　　　　　/(284025438982318025793544200005777916187500000000)

なので、ｐ14 との差は、　ｐ2−ｐ14＝0.000001296145…　となります。


　ＧＡＩ さんからの新たな疑問です。（平成２３年３月２３日付け）

　一組のトランプから何枚のカードを取り出して、この実験（いくつから数え落とす。）を
したら、一致する確率が０．５を初めて超えるのだろうか？


　ＧＡＩ さんからの続報です。（平成２３年３月３０日付け）

　５２枚のトランプから、任意の ｎ 枚のカードを取り出し、ｎ からカウントダウンしていき、号
令とカードの数字が最後まで一致しないで終わる確率を、ａｔ さんの計算式を参考に計算を
実行したら、次のような結果を得ました。

ｎ ０ １ ２ ３ ４ ５ ６ ７
確率 １.00000 0.92307 0.85218 0.78684 0.72661 0.67108 0.61987 0.57265
ｎ ８ ９ １０ １１ １２ １３
確率 0.52909 0.48891 0.45184 0.41763 0.38607 0.35693

　これより９枚のカードをランダムに取り出し、「９からカウントダウン」していけば、号令とカ
ードの数字が一致してしまう確率が初めて０．５を超える現象を起こせると考えられる。

　何度か実験してみましたが、割と一致することが少ない枚数にもかかわらず起こることが
実感できました。


　ａｔ さんからのコメントです。（平成２３年３月３１日付け）

　一組のトランプから ｎ 枚(０≦ｎ≦１３)を取り出し、ｎ からカウントダウンしていくとき、号令
とカードのナンバーが一致する確率を ｐ(ｎ) とすると、

　　ｐ(ｎ)＝１−｛Σ[k=0〜ｎ]（−１）ｋ・ｎＣｋ・４ｋ・（５２−ｋ）！｝/５２！

　この式を使って計算すると、　　ｐ(８)＝０．４７０・・・　、　ｐ(９)＝０．５１１・・・　　となるので、
一致する確率が０．５を初めて超えるような最小枚数は確かに ９ ですね。


（追記）　平成２４年１０月１１日付け

　当ＨＰ読者のＨＮ「はやふみ」さんからのコメントです。

　上記の「５２枚のトランプで、１〜１３の号令と合うかどうか」の確率の問題なんですが．．．。

　これら１３枚のカードを並べる１３箇所のうち、特定のｋ箇所（０≦ｋ≦１３）にあるカードが
号令と一致するような並べ方は、同一数字が４枚あることに注意して、

　　　４ｋ・（５２−ｋ）！ 通り。

　したがって、１３箇所のうちの ｋ 箇所にあるカードが号令と一致するような５２枚のカード
の並べ方は、　13Ｃｋ・４ｋ・（５２−ｋ）！ 通り。

の部分で、例えば、１ヶ所合うとすると、ｋ＝１を代入して、

　　13Ｃ1・４・５１！＝１３×４×５１！＝５２！（通り）

になるということでしょうか？


（コメント）　計算は合っていますよ！たまたま結果の数字が５２！になっただけです．．．。


（追記）　令和元年１１月３０日付け

　ある部屋に３ヶ国語のうち少なくとも１ヶ国語を知っている何人かの人がいる。そのうち１０
人は中国語を、８人は英語を、９人はフランス語を知っている。５人は中国語と英語を知って
いる。４人は英語とフランス語を知っている。３人はフランス語と中国語を知っている。２人は
３ヶ国語全部を知っている。部屋には何人いるか。そのうちで中国語だけを知っている人は
何人いるか。

（解）　ｎ（中）＝１０、ｎ（英）＝８、ｎ（仏）＝９、ｎ（中＆英）＝５、ｎ（英＆仏）＝４、
　　　ｎ（仏＆中）＝３、ｎ（中＆英＆仏）＝２

　から、個数定理より、　

　ｎ（中）＋ｎ（英）＋ｎ（仏）−ｎ（中＆英）−ｎ（英＆仏）ｰｎ（仏＆中）＋ｎ（中＆英＆仏）
＝１０＋８＋９−５−４−３＋２
＝１７

　中国語だけを知っている人は、

　ｎ（中）−ｎ（中＆英）−ｎ（仏＆中）＋ｎ（中＆英＆仏）＝１０−５−３＋２＝４　　（終）


（コメント）　個数定理を用いた解法は上記の通りであるが、次のような考え方もあることを
　　　　　　最近知ることができた。

　題意より、次の表を得る。

中国語 英語 仏語 中＆英 英＆仏 仏＆中 中＆英＆仏
１０ ８ ９ ５ ４ ３ ２

　この状態から、中＆英＆仏を知っている人が退室すると、下表のようになる。

中国語 英語 仏語 中＆英 英＆仏 仏＆中 中＆英＆仏
８ ６ ７ ３ ２ １ ０

　次に、中＆英を知っている人が退室すると、下表のようになる。

中国語 英語 仏語 中＆英 英＆仏 仏＆中 中＆英＆仏
５ ３ ７ ０ ２ １ ０

　同様にして、英＆仏、仏＆中を知っている人が退室すると、下表のようになる。

中国語 英語 仏語 中＆英 英＆仏 仏＆中 中＆英＆仏
４ １ ４ ０ ０ ０ ０

　この表から、退室した人（２＋３＋２＋１）＋まだ残っている人（４＋１＋４）を求めると、部屋
には１７人いたことが分かる。また、中国語だけを知っている人は、４人である。

＃３つの場合の個数定理を知らなくても機械的な計算で求められますね！


（追記）　令和３年８月１７日付け

　「包含と排除の原理（包除原理）」を用いる問題を考えてみよう。

問題　　５個の数字の並び ***** がある。*に入る数字は、０〜９の１０種類ある。この並び
　　　　の中で、数字の並び「１２」を含むものは何個あるだろうか？

（解）　Ｅ1：１２*** のタイプの並び、Ｅ2：*１２** のタイプの並び、Ｅ3：**１２* のタイプの並び、

　　　Ｅ4：***１２ のタイプの並び　とすると、求める場合は、　Ｅ1∪Ｅ2∪Ｅ3∪Ｅ4　となる。

　まず、　ｎ（Ｅ1）＝ｎ（Ｅ2）＝ｎ（Ｅ3）＝ｎ（Ｅ4）＝１０3

　次に、　ｎ（Ｅ1∩Ｅ2）＝０、ｎ（Ｅ1∩Ｅ3）＝１０、ｎ（Ｅ1∩Ｅ4）＝１０、ｎ（Ｅ2∩Ｅ3）＝０、

　　　　　ｎ（Ｅ2∩Ｅ4）＝１０、ｎ（Ｅ3∩Ｅ4）＝０

　また、相異なる ｉ、ｊ、ｋ に対して、　ｎ（Ｅｉ∩Ｅｊ∩Ｅｋ）＝０　なので、求める場合の数は、

　４・１０3−３・１０＝３９７０（個）　　（終）


（追記）　令和４年８月６日付け

　個数定理や包除原理に関する問題が一橋大学（２０２１年）で出題された。

問題　　１０００以下の素数は、２５０個以下であることを示せ。

　１０００以下の数で、２の倍数だけで５００個、２で割り切れない３の倍数は、１６７個あり、
これだけで、６６７個。あと残りは、３３３個なので、もう少しエラトステネスの篩をかければ、
なんとか２５０個までは減らせそうだ。この方針で、問題を解いてみよう。

（解）　１０００以下の数で、２の倍数の個数は、５００個、３の倍数の個数は、３３３個、５の

　　倍数の個数は、２００個、７の倍数の個数は、１４２個、１１の倍数の個数は、９０個、・・・

　そこで、１０００以下の数で、２の倍数全体を集合Ａ、３の倍数全体を集合Ｂ、５の倍数全体

を集合Ｃ、７の倍数全体を集合Ｄ、１１の倍数全体を集合Ｅ、・・・　とおく。

　集合Ａの要素の個数をｎ（Ａ）で表すと、　ｎ（Ａ）＝５００　となる。同様にして、

　ｎ（Ｂ）＝３３３　、ｎ（Ｃ）＝２００　、ｎ（Ｄ）＝１４２　、ｎ（Ｅ）＝９０　、・・・

　個数定理を考えれば、次の集合の要素の個数も調べなければならない。

　ｎ（Ａ∩Ｂ）＝１６６　、ｎ（Ｂ∩Ｃ）＝６６　、ｎ（Ｃ∩Ａ）＝１００　、ｎ（Ａ∩Ｂ∩Ｃ）＝３３

　ここで、

ｎ（Ａ∪Ｂ∪Ｃ）＝ｎ（Ａ）＋ｎ（Ｂ）＋ｎ（Ｃ）−ｎ（Ａ∩Ｂ）−ｎ（Ｂ∩Ｃ）−ｎ（Ｃ∩Ａ）＋ｎ（Ａ∩Ｂ∩Ｃ）

　　　　　　　　＝５００＋３３３＋２００−１６６−６６−１００＋３３＝７３４

　このとき、１０００以下の素数は、　１０００−７３４＋３＝２６９（個）　以下で、まだ不十分！

　７の倍数までエラトステネスの篩を広げて、

ｎ（Ａ∪Ｂ∪Ｃ∪Ｄ）

＝ｎ（Ａ）＋ｎ（Ｂ）＋ｎ（Ｃ）＋ｎ（Ｄ）−ｎ（Ａ∩Ｂ）−ｎ（Ａ∩Ｃ）−ｎ（Ｂ∩Ｃ）−ｎ（Ｂ∩Ｄ）

　−ｎ（Ｃ∩Ｄ）−ｎ（Ｄ∩Ａ）＋ｎ（Ａ∩Ｂ∩Ｃ）＋ｎ（Ａ∩Ｂ∩Ｄ）＋ｎ（Ａ∩Ｃ∩Ｄ）＋ｎ（Ｂ∩Ｃ∩Ｄ）

　−ｎ（Ａ∩Ｂ∩Ｃ∩Ｄ）

＝５００＋３３３＋２００＋１４２−１６６−１００−６６−４７−２８−７１＋３３＋２３＋１４＋９−４

＝７７２

　このとき、１０００以下の素数は、　１０００−７７２＋４＝２３２（個）　以下で、２５０個以下が

示せた。　　（終）



　　　　　以下、工事中