Symmetric Inclusion-Exclusion

Ira M. Gessel

Séminaire lotharingien de combinatoire, Tome 54 (2006-2007)

Résumé

One form of the inclusion-exclusion principle asserts that if A and B are functions of finite sets then the formulas $ A(S) = \sum_{T\subseteq S}B(T)$ and $ B(S) = \sum_{T\subseteq S}(-1)^{\vert S\vert-\vert T\vert}A(T)$ are equivalent. If we replace B(S)$ by (-1)$ which we call symmetric inclusion-exclusion. We study instances of symmetric inclusion-exclusion in which the functions A and B have combinatorial or probabilistic interpretations. In particular, we study cases related to the Pólya-Eggenberger urn model in which A(S) and B(S) depend only on the cardinality of S.