The Method of Special Cases in Combinatorial Theory and Probability

摘要

Renyi has given a very simple and elegant approach to proving inclusion-exclusion relations. We reformulate Renyi's method as a theorem on non-negative additive set functions on finite sets. The set is then assumed to be partially ordered and the theorem is applied to prove the Mobius inversion formula. In analogy with results on the lattice of subsets we are led to conjecture and prove relations for other partially ordered sets in particular the lattice of subspaces of a finite vector space and the lattice of partitions of a set. (Author)