An improvement of the inclusion-exclusion principle (Q1293322): Difference between revisions

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.