包除原理とは？
ほうじょげんり
「原理」の用語まとめを見る包除原理とは、複数の集合の和集合の要素数を、各集合の要素数の足し算と引き算を交互に繰り返すことで正確に求める数学の定理です。
包除原理（inclusion-exclusion principle）とは、組み合わせ論・集合論における基本定理で、複数の有限集合の和集合の要素数（大きさ）を求めるための公式です。
最も単純な2つの集合AとBの場合、|A∪B|＝|A|＋|B|－|A∩B|と表されます。単純に足すと積集合（重複部分）が二重に数えられてしまうため、それを引くという発想です。3つ以上の集合に拡張すると「足して、引いて、また足して…」と符号が交互に入れ替わります。
包除原理が活躍する代表的な場面は以下のとおりです。
- 素因数の数え上げ：1からNまでの整数のうち、特定の素数の倍数でないものを数える
- 完全順列（撹乱順列）の計算：どの要素も元の位置に戻らない並べ替えの個数
- 確率論：複数の事象のいずれかが起こる確率の計算
- グラフ彩色問題：特定の条件で色を塗る方法の数え上げ
包除原理はその名のとおり「包む（inclusion）」と「除く（exclusion）」を交互に行う構造を持ちます。オイラーのトーシェント関数（互いに素な整数の個数）の計算にも包除原理が使われており、整数論や暗号理論にも関係が深い定理です。見た目はシンプルですが、組み合わせ問題の多くを解く強力な道具となっています。
使い方・例文
100人のうち数学が好きな人が60人、英語が好きな人が50人、両方好きな人が20人いるとき、少なくともどちらかが好きな人は60＋50－20＝90人と求められます。これが包除原理の基本的な使い方です。
この用語をシェア
最終更新: