■包除原理(その11)

 集合の包除関係を表すのにベン図(あるいはオイラー図)が用いられている.2円が交差した場合,交差部A∩Bにはアーモンド型ができる.包除の組み合わせは2^2=4通りあるが,どれにも属さない集合が2円の外側の領域で表される.

 3円が交差した場合,3つのアーモンドが交差した部分A∩B∩Cにさらにルーローの三角型ができる.包除の組み合わせは2^3=8通りあるが,7通りと3円の外側の領域とですべて表される.

 4円が交差した場合,包除の組み合わせは2^4=16通りあるが,外側を含めても14の領域しかできないようにみえる.これでは16通りの包除関係を表現できないことになってしまうが,原因は円を用いているからダメなのであって,楕円などの閉曲線を適宜用いるしかない.図の危ないところといえるだろう.

===================================

 ベン図では,3個の円を重ねて8通りの部分集合を示すことができる.しかし,4個の円を重ねても16通りの部分集合を図示することはできない.

 2個の円は高々2カ所でしか交わらないので,4個の円を重ねても最大14通りの領域までしか増やすことはできないのである.

 しかし,楕円を使えばそれが可能になる.楕円を使えば32通りの部分集合も図示することができるのである.

===================================

 ところで,3円が交差した場合,3つのアーモンドが交差した部分A∩B∩Cにさらにルーローの三角型ができる.包除の組み合わせは2^3=8通りあるが,7通りと3円の外側の領域とですべて表される.

 しかし,各領域の要素数を面積比で正しく表現できる3円が交差したベン図を描くことはできないことは,以下の例を思い浮かべると直ちに理解できる.

{A}≠φ,{B}≠φ,{C}≠φ,{A∩B∩C}≠φ

{A∩B}=φ,{B∩C}=φ,{C∩A}=φ

===================================

ヘリーの定理

4円の場合、{A∩B∩C}≠φ,{B∩C∩D}≠φ,{C∩D∩A}≠φならば{A∩B∩C∩D}≠φ

一般に、N≧n+1として、n次元空間にN個の凸領域があり、凸領域の集合から任意のn+1個の領域を選択しても空でない交わりがある場合、

N個の凸領域の集合には空でない交わりがある。

n=2, N=4の場合が上述の例である。

===================================