Intereting Posts

Graph Theory: Forests
Prove that the $\lim_{(x,y) \to (0,0)}h(x,y)$ Does not Exist using Polar Coordinates
2013 Putnam A1 Proof understanding (geometry)
Simplify $Im \left(\frac{az+b}{cz+d}\right)$
$AB-BA$ is a nilpotent matrix if it commutes with $A$
A set $A \subseteq \mathbb{R}$ is closed if and only if every convergent sequence in $\mathbb{R}$ completely contained in $A$ has its limit in $A$
$\forall x \,\exists k$ s.t. $f^{(k)}(x)=0$, then $f$ is a polynomial
Typicality of boundedness of entries of continued fraction representations
Intuition behind the scaling property of Fourier Transforms
Distance between a point and a line in space
Prove $f(S \cup T) = f(S) \cup f(T)$
Find the singular values of $T: p(x)\mapsto xp'(x)+2x^2p''(x)$
Sum of all elements in a matrix
Alternative proof that the parity of permutation is well defined?
Justification for moving a limit outside an indefinite integral

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.

- Evaluating a limit involving binomial coefficients.
- 21 sided regular polygon and its diagonals
- inductive proof for $\binom{2n}{n}$
- Finding $\binom{999}{0}-\binom{999}{2}+\binom{999}{4}-\binom{999}{6}+\cdots +\binom{999}{996}-\binom{999}{998}$
- Number of different necklaces using $m$ red and $n$ white pebbles
- Simple combinations - Party Lamps

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?

- Combinatorics question about choosing non consecutive integers
- Probability/Combinatorics Question
- Generate Random Latin Squares
- Applications of the Fibonacci sequence
- How many ways can a sequence of $1$s be partitioned into pairs or singles?
- Number of 'unique' one bit binary functions with N-bit inputs
- What is the number of compositions of the integer n such that no part is unique?
- Number of ways to put N items into K bins with at least 1 per bin?
- Building a 3D matrix of positive integers
- General formula for this sum $\sum_{k=1}^n\frac{1}{k(k+1)…(k+m)}$

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.

- If $f(2x)=2f(x), \,f'(0)=0$ Then $f(x)=0$
- Why do we say the harmonic series is divergent?
- determinant of permutation matrix
- How to show that if two integral domains are isomorphic, then their corresponding field of quotients are isomorphic?
- Find a vector that is perpendicular to $u = (9,2)$
- Proving $\sqrt{2}\in\mathbb{Q_7}$?
- Why degree of a reducible projective variety is the sum of the degree of its irreducible components
- parity bias for trees?
- Area under a point
- Careful proof of $A \subseteq (B \cup C) \iff A \setminus C \subseteq B$
- injective and surjective
- Relationship between wild ramification and restriction in Galois extension
- Proving Holder's inequality using Jensen's inequality
- Fourier Transform of $sgn(t)$
- About the Continuum Hypothesis