Intereting Posts

How to prove the existence of $b$ in $Q$ such that $a<b^2<c$ in $Q$?
Disprove the Twin Prime Conjecture for Exotic Primes
Rigorous proof that countable union of countable sets is countable
Understanding countable ordinals (as trees, step by step)
Example where closure of $A+B$ is different from sum of closures of $A$ and $B$
If $G$ is a finite group and $|G| < |A| + |B|$, then $G=AB$.
How many groups of 4 primes exist such that their sum is a prime and that $p^2+qs$ and $p^2+qr$ are squares?
$F:G\to B$ is an isomorphism between groups implies $F^{-1}$ is an isomorphism
Coordinate method for solving first order linear PDE
Fermat's equation with real exponents
Probability distribution in the coupon collector's problem
Is $\ell^1$ isomorphic to $L^1$?
Krein-Milman theorem and dividing pizza with toppings
Why the $O(t^2)$ part in $L(t) = L + t(\csc \alpha_i – \cot \alpha_i +\csc \alpha_{i+1} – \cot \alpha_{i+1}) + O(t^2)$?
Inscribed kissing circles in an equilateral triangle

I recently read Doron Zeilberger’s paper on Inclusion-Exclusion Principle.

Let’s say there are $n$ properties which are numbered $1,\cdots,n$.

And let $A$ be a set of elements which has some of these properties.

Then the Inclusion-Exclusion Principle states that the number of elements with no properties at all is

\begin{equation*}

\sum_{I\subset \{1,\cdots,n\}} (-1)^{|I|}\cdot |A_I|

\end{equation*}

where the summation runs over all subsets $I$ of $\{1,\cdots,n\}$ and $A_I$ denotes the set of elements having all the properties of $I$.

This is perfectly fine, but he finishes his two-page paper with a **Generalized** version of Inclusion-Exclusion Principle.

- Sum of Stirling numbers of both kinds
- How many $n$-digit decimal sequences (using the digits $0 = 9$) are there in which the digits $1$, $2$ and $3$ all appear?
- Count the number of n-bit strings with an even number of zeros.
- In how many ways can we colour $n$ baskets with $r$ colours?
- How can I prove this combinatorial identity $\sum_{j=0}^n j\binom{2n}{n+j}\binom{m+j-1}{2m-1}=m\cdot4^{n-m}\cdot\binom{n}{m}$?
- Showing probability no husband next to wife converges to $e^{-1}$

Let $t_1,\cdots,t_n$ be commuting indeterminates and for

$I=\{i_1,\cdots,i_k\} \subseteq\{1,\cdots,n\}$ denote

$t_I=t_1\cdots t_k$ and $(t-1)_{I}=(t_{i_1} – 1)\cdots(t_{i_k}-1)$.

For $a\in A$, let $prop(a)$ denotes the set of properties of $a$. Then

\begin{equation*}\sum_{a\in A}t_{prop(a)} = \sum_{I\subset\{1,\cdots,n\}}|A_I|\cdot (t-1)_I\end{equation*}

I’ve never heard of this generalized version before. Probably, the original version can be recovered by setting $t_{i_1}=\cdots=t_{i_k}=0$ and the LHS becomes ‘number of elements with no properties at all.’ Is there any textbooks or lecture notes explaining this generalized version of Inclusion-Exclusion Principle?

- Restricted Compositions
- Counting non-negative integral solutions
- Combinatorics Involving Seating People in a Line
- Steiner triple system with $\lambda \le 1$
- Probability that 2 appears at an earlier position than any other even number in a permutation of 1-20
- A sum of fractional parts.
- Counting Set Partitions with Constraints
- What is the probability of the sum of four dice being 22?
- General Leibniz rule for triple products
- Combinatorial proof of the identity ${n+1\choose k+1}={k\choose k}+{k+1\choose k}+…+{n-1\choose k}+{n\choose k}$

I’ve not seen it before, but I can derive it. For $I\in[n]=\{1,\ldots,n\}$ let $x_i=t_i-1$. Then

$$\begin{align*}

\sum_{a\in A}t_{prop(a)}&=\sum_{a\in A}\prod_{i\in prop(a)}(x_i+1)\\

&=\sum_{a\in A}\sum_{I\subseteq prop(a)}x_I\\

&=\sum_{I\subseteq[n]}\sum_{a \in A_I}x_I\\

&=\sum_{I\subseteq[n]}|A_I|x_I\\

&=\sum_{I\subseteq[n]}|A_I|(t-1)_I\;,

\end{align*}$$

where $x_I=\prod_{i\in I}x_i$.

If all of the indeterminates are the same, it becomes

$$\sum_{a\in A}t^{|prop(a)|}=\sum_{I\subseteq[n]}|A_I|(t-1)^{|I|}\;,$$

which is essentially the result presented in Section $4.2$, *A generatingfunctionological view of the sieve method*, in Herbert S. Wilf’s book *generatingfunctionology*, which is freely available here.

- Factorise: $2a^4 + a^2b^2 + ab^3 + b^4$
- Showing that the direct product does not satisfy the universal property of the direct sum
- Is the class of cardinals totally ordered?
- Hilbert's Original Proof of the Nullstellensatz
- About Euclid's Elements and modern video games
- Why is there no space whose dual is $C_\mathbb{R}$?
- If a sub-C*-algebra does not contain the unit, is it contained in a proper ideal?
- Showing that every finitely presented group has a $4$-manifold with it as its fundamental group
- Solving: $3^m-2=n^2$
- How to find $x$ when $2^{x}+3^{x}=6$?
- Value of cyclotomic polynomial evaluated at 1
- The alternating group is generated by three-cycles
- How do I prove that $\sum_{k=1}^{b-1} = \frac{(a-1)(b-1)}{2}$?
- What is the area of the apollonian gaskets?
- If $f\in L^1(\mathbb{R})$ is such that $\int_{\mathbb{R}}f\phi=0$ for all continuous compactly supported $\phi$, then $f\equiv 0$.