組み合わせ論では、ポアンカレのふるいの公式またはポアンカレの公式は、ふるいの公式とも呼ばれ、有限数の集合の和集合の基数とその共通部分の基数との間の関係です。
定理
A 1 , …, A n n有限集合とします。我々は持っています
- $$ {\left|\,\bigcup_{i=1}^n A_i\,\right|=\sum_{i=1}^n\left|A_i\right| -\sum_{(i,j)\,/\,1\leq i$$ {+\sum_{(i,j,k)\,/\,1\leq i
ここで |あ|は有限集合Aの基数を表します。
この式は、より圧縮された方法で書くこともできます
- $$ {\left|\,\bigcup_{i=1}^n A_i\,\right|=\sum_{k=1}^n \left((-1)^{k-1} \sum_{1\leq i_1。
これは、 nの帰納法によって、またはインジケーター関数を使用して実証できます。
特殊な場合
たとえば、 n = 2 の場合を考えてみましょう。A とBを2 つの有限集合とすると、式は次のようになります。
- $$ {|A\cup B|=|A|+|B|-|A\cap B|} $$
ここで |あ|と | B |はAとBのそれぞれの基数を表します。
言い換えれば、2 つのセットAとBの和集合の要素は、これら 2 つのセットの基数を加算し、それらの共通部分の基数を減算することで数えることができます。
この原則は、寛大な包摂とそれに続く代償的な排除に基づいています (ムーブルの包含-排除原則)。
n > 2 の場合、セットのペアの共通部分からの基数の除外は (一般に) 強すぎるため、より多くのセットから基数を加算および減算することによって修正されます。したがって、一般式の符号が交互になります。
アプリケーション
ふるいの公式の最もよく知られた応用は、間違いなく、組み合わせ論における有限集合の乱れの数の決定です。
集合Aの外乱は、固定点を持たないAのそれ自体への全単射です。
モアブルの包含排除原理のおかげで、 Aの基数がnに等しい場合、 Aの撹乱の数は次の値に最も近い整数であることを証明できます。
したがって、すべての全単射が選択される確率が同じである場合、ランダムに取得された全単射が外乱である確率は、 n が無限大になる傾向があるため、すぐに 1/e に近づく傾向があります。
多くの場合 (特に、エラトステネスのふるいを使用して特定の整数未満の素数を数える場合)、ポアンカレの公式は含まれる項の数が多すぎることが判明するため、あまり役に立ちません。合計の各項を正確に評価できる場合、加算における計算エラーが蓄積すると、式が適用できなくなる可能性があります。
整数論では、この難しさはヴィゴ・ブランによって提起されました。ずっと後になって、彼のアイデアは他の数学者によって採用され、さまざまなふるい法が開発されました。たとえば、それらの中には、過度に面倒な式で正確な値を与えるのではなく、「スクリーンされた」セットの基数を非常に細かくフレーム化できるものもあります。このようなフレームは、ふるいの公式の最初の項の合計が和集合の基数の上限と下限を交互に表すことに注目することによって得られます。