An improvement of the inclusion-exclusion principle (Q1293322): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 11:52, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An improvement of the inclusion-exclusion principle |
scientific article |
Statements
An improvement of the inclusion-exclusion principle (English)
0 references
10 April 2000
0 references
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.
0 references
inclusion-exclusion principle
0 references