If an element x of S satisfies exactly r of the t conditions, how many times is x counted in the following expressions?

130 Views Asked by At

Use the standard notation for Inclusion-Exclusion ($S$ is a set of $N$ elements, ${c_1} {c_2} ...{c_t}$ are conditions on the elements of $S$, and $N({c_i}_1 {c_i}_2...{c_i}_m)$ is the number of elements of $S$ satisfying all of conditions ${c_i}_1 {c_i}_2...{c_i}_m)$. If an element x of S satisfies exactly r of the t conditions, how many times is x counted in the following expressions?

Here are the notations used: $$1)\sum_{i<j}N(c_ic_j)$$ This the summation of all possible combinations without repetition of elements in $1\leq i\lt j\le t$, then is the answer $\binom{t}{2} \binom{t}{x}$?

$$2) \sum_{i\ne j}N(c_ic_j)$$ I guessing that notation $(1)=(2)$

The following notations I don't understand: $$3)\sum_{i,j,k}N(c_i c_j c_k)$$ $$4)\sum_{i,j,k,l \textrm{ distinct and } i<j \textrm{ and } k>l} N(c_i c_j c_k c_l)$$ $$5)\sum_{i,j,k,l \textrm{ satisfying } l<j<k } N(c_i c_j c_k c_l)$$