ĐẲNG THỨC QUAN TRỌNG TRONG TỔ HỢP_MỞ RỘNG

Đây là một đẳng thức vô cùng quan trọng,thương áp dụng được vào các bài toán về tập hợp hoặc 2 ways
Định lí:Cho tập S gồm n phần tử,F là một họ tập con của S.Với mỗi phần tử x của S,gọi d(x) là số lần xuất hiện của x trong F,khi đó
i/  $\sum_{x\in S}d(x)=\sum_{A\subset F}|A|$
ii/ $\sum_{x\in S}d(x)^2=\sum_{A,B\subset F}|A\cap B|$
iii/ $\sum_{x\in S}d(x)^2-\sum_{x\in S}d(x)=2\sum_{A=! B\subset F}|A\cap B|$

Bằng cách chứng minh tương tự của vấn đề trên,ta có thể mở rộng thành giao của nhiều hơn hai tập hợp:
Định lí:Cho tập S gồm n phần tử,$F=\{A_1,A_2,...,A_t\}$ với $t<2^n$
với $m=<t$ đặt $f(m)=\sum_{1=<i_1<i_2<...<i_m<t}|\cap A_{i_1}A_{i_2}...A{i_m}|$
Khi đó ta có thể tính $f(m)$ qua công thức truy hồi;
$f(1)=\sum_{x\in S}d(x),f(2)=\sum_{x\in S}d(x)^2-\sum_{x\in S}d(x)$
$f(m)=\frac{-f(m-1)+\sum_{x\in S}d(x)}{m!}$