Inclusion-Exclusion-Like identities

arXiv1911.03634MaRDI QIDQ6328832FDOQ6328832

Publication date: 9 November 2019

Abstract: An expression

E (X_{1}, ..., X_{n})

built using union, intersection, and complements is called inclusion-exclusion-like if, like the union in the exclusion-inclusion principle, there are constants

c_{1}, c_{2}, ..., c_{n}

so that for any sequence of sets

A = (A_{1}, ..., A_{n})

the cardinality of

E (A_{1}, ..., A_{n})

can be expressed as

l e f t | E (A_{1}, ..., A_{n}) i g h t | =

s u m_{k = 1}^{n} c_{k} i_{n, k} (A)

where

i_{n, k} (A) = s u m_{I s u b s e t e q o v e r l i n e n, l e f t | I = k i g h t |}^{n} l e f t | c a p_{i i n I} A_{i} i g h t |

is the sum of the cardinalities of all intersections of

k

sets in the sequence

A

. In this paper, we construct, from the expression

E

, a set of nonempty subsets of

l e f t 1, l d o t s, n i g h t

called the characteristic set of

E

, and using this set to give a necessary and sufficient condition for the expression to be inclusion-exclusion-like . Furthermore, we give a method for determining the constants

c_{1}, c_{2}, ..., c_{n}

in the expression for the cardinality of

E (A_{1}, ..., A_{n})

when it exists. The content of the paper is illustrated by a simple detailed example given in the introduction.

This page was built for publication: Inclusion-Exclusion-Like identities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6328832)