翻訳と辞書
Words near each other
・ 包装紙
・ 包装資材
・ 包裝大師
・ 包豹忱
・ 包道乙
・ 包金
・ 包金銀
・ 包銀
・ 包鋼
・ 包鋼股分
包除原理
・ 包雲蔚
・ 包青天
・ 包領
・ 包頭
・ 包頭二里半空港
・ 包頭器
・ 包頭市
・ 包頭東駅
・ 包頭空港


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

包除原理 : ウィキペディア日本語版
包除原理[ほうじょげんり]
組合せ数学において、包除原理(ほうじょげんり、包含と排除の原理、)とは''A''1, ..., ''A''''n''有限集合としたとき
:
\left|\bigcup_i A_i\right|
=
\sum_i \left|A_i\right|
- \sum_ \left|A_i\cap A_j\right|
+ \cdots
+ (-1)^ \left|A_1\cap \cdots \cap A_n\right|

となることをいう。ここで |''A''| は集合 ''A'' の濃度をあらわす。例えば、''n'' = 2 のときは、二重計算の特別な場合となる。簡単に言えば、集合 ''A'' と ''B'' の和集合の大きさを計算する方法として、まず |''A''| と |''B''| を足しあわせ、それらの共通部分の大きさを引き去ることで計算できるというものである。この原理の名称は、あらゆるものを「含め」、その後で「取り除いて」補正をするという考え方に基づいていることからきている。''n'' > 2 のときは、共通部分の除外計算が場合によって非常に困難になってくる。また、公式には符号が交互にあらわれる。
この公式はアブラーム・ド・モアブルによるものと考えられている。時にジェームス・ジョセフ・シルベスターまたはアンリ・ポアンカレによるとも言われる。
たとえば3つの有限集合 ''A'', ''B'', ''C'' に対しての包除原理は右図のようにあらわされる。
:\begin
\left| A \cup B \cup C \right|
=
&\left| A \right| + \left| B \right| + \left| C \right| \\
&\quad - \left| A \cap B \right| - \left| B \cap C \right| - \left| C \cap A \right| \\
&\qquad + \left| A \cap B \cap C \right|
\end

==証明==
包除原理を一般に証明するため、''X'' を ''A''1, ..., ''A''''n''上位集合とする。公式はまず恒等式
:
1_
=
\sum_i 1_
-\sum_1_
+ \cdots
+ (-1)^ 1_

指示関数の変形でもとめ、全ての ''x'' ∈ ''X'' について足しあわせることで示される。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「包除原理」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.