離散數學(8)

第八章 The Principle of Inclusion and Exclusion

The Principle of Inclusion and Exclusion. Cosider a set S, with |S|=N, and coditions ci, 1<=i<=t, each of which way be satisfied by some of the elements of s of S. The number of elements of S that satisfy none of the conditions ci, 1<=i<=t, is denoted by N'=N(c1'c2'c3'...ct') where

N'=N-[N(c1)+N(c2)+...+N(ct)]+[N(c1c2)+n(c1c3)+...+N(c1ct)+N(c2c3)+...+N(ct-1ct)]-[N(c1c2c3)+N(c1c2c4)+...+N(c1c2ct)_N(c1c3c4)+...+N(c1c3ct)+...+N(ct-2ct-1ct)]+...+
(-1)^tN(c1c2c3...ct)

N'=N-1<=i<=t∑N(ci)+1<=i<j<=t∑N(cicj)-1<=i<j<k<=t∑N(cicjck)+...+
     (-1)^tN(c1c2c3...ct)