2
$\begingroup$

I'm trying to find a way to derive a generalized inclusion exclusion principle for the number of elements which are in the intersection of at least $s$ sets from $A_1,A_2,...,A_n$ using this identity:

let $k$ and $s$ be positive integers and let $k\ge s\ge 1$ $$\sum_{i=0}^{k-s} (-1)^i{s-1+i \choose s-1}{k \choose s+i} = 1$$

I'm coming from this question: proof that the binomial sum is equal to 1

It appears from the sum that what determines whether we add or substract the product of binomial coefficient is whether it has even or odd number of elements and it can be applied to every subset of $s.

But I don't quite understand the concept of the generalized form of inclusion exclusion principle.

$\endgroup$
0
$\begingroup$

For a generalized inclusion-exclusion theorem, see this answer. In that answer, the Theorem says that the number of items in exactly $k$ of the sets is $$ \sum_{j=0}^m(-1)^{j-k}\binom{j}{k}N(j) $$ Corollary 2 says that the number of items in at least $k$ of the sets is $$ \bbox[5px,border:2px solid #C0A000]{\sum_{j=k}^m(-1)^{j-k}\binom{j-1}{j-k}N(j)} $$ where $\binom{-1}{n}=$$(-1)^n\binom{n}{n}$$=(-1)^n$$[n\ge0]$.


Proof of the Identity

If $k\ge s$, then $$ \begin{align} \sum_{i=0}^{k-s}(-1)^i\binom{s-1+i}{s-1}\binom{k}{s+i} &=\sum_{i=0}^{k-s}(-1)^i\binom{s-1+i}{i}\binom{k}{k-s-i}\tag{1}\\ &=\sum_{i=0}^{k-s}\binom{-s}{i}\binom{k}{k-s-i}\tag{2}\\ &=\binom{k-s}{k-s}\tag{3}\\[8pt] &=1\tag{4} \end{align} $$ Explanation:
$(1)$: $\binom{n}{k}=\binom{n}{n-k}$ for $n\ge0$ and $n\in\mathbb{Z}$
$(2)$: $\binom{-n}{k}=(-1)^k\binom{n+k-1}{k}$
$(3)$: Vandermonde's Identity
$(4)$: $\binom{n}{n}=1$ for $n\ge0$ and $n\in\mathbb{Z}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.