An improvement of the inclusion-exclusion principle
type: Item
instance of: scholarly article
title: An improvement of the inclusion-exclusion principle
zbMATH Open document ID: 0934.05011
author: Klaus Dohmen
published in: Archiv der Mathematik
publication date: 2000-04-10T00:00:00Z
review text: The formula known as the inclusion-exclusion principle has been studied extensively by many authors, e.g. \textit{J. Riordan} [An introduction to combinatorial analysis (1958; Zbl 0078.00805)] and \textit{G.-C. Rota} [On the foundations of combinatorial theory. I: Theory of Möbius functions. Z. Wahrscheinlichkeitstheor. Verw. Geb. 2, 340-368 (1964; Zbl 0121.02406)]. The present paper establishes an improvement of the formula reducing the number of its terms by predicted cancellation. The improvement generalizes \textit{H. Whitney's} broken-circuit-theorem [A logical expansion in mathematics. Bull. Am. Math. Soc. 38, 572-579 (1932; Zbl 0005.14602)], as well as a related result of \textit{H. Narushima} [Principle of inclusion-exclusion on partially ordered sets, Discrete Math. 42, 243-250 (1982; Zbl 0497.06003)]. Applications are given to chromatic polynomials and permanents of \((0,1)\)-matrices.
Mathematics Subject Classification ID: 05A19
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1309647
zbMATH Keywords: inclusion-exclusion principle
reviewed by: Andreas N. Philippou
MaRDI profile type: Publication
full work available at URL: s000130050336
OpenAlex ID: W2065094840
DOI: 10.1007/S000130050336
Recommended article: Q4550547
Recommended article: Q3679192
Recommended article: Q4923670
Recommended article: Inclusion-exclusion redux
Recommended article: Q3012568
Recommended article: The inclusion-exclusion principle without distributivity
Recommended article: On an inclusion-exclusion formula based on the reflection principle
Recommended article: The inclusion-exclusion principle for finitely many isolated sets
Recommended article: Improving the efficiency of exclusion algorithms
Recommended article: Q3202928
description: scientific article; zbMATH DE number 1309647