Inclusion-exclusion type identity

Question

Let $t_0,t_1,\ldots,t_m$ be variables, let $k$ be a non-negative integer. Denote also $[m]=\{1,2,\ldots,m\}$.

Fact. The following identity holds: $$ \sum_{I\subset [m]}(-1)^{m-|I|}\left(t_0+\sum_{i\in I}t_i\right)^k=\sum_{\substack{0\le i_1,\ldots,i_k\le m\\ [m]\subset\{i_1,\ldots,i_k\}}}t_{i_1}\ldots t_{i_k}. $$ Example. For $m=2$ and $k=3$ we have $$ (t_0+t_1+t_2)^3-(t_0+t_1)^3-(t_0+t_2)^3+t_0^3=6t_0t_1t_2. $$

Basically the identity says that by taking this alternating sum one can extract from multinomial $(t_0+t_1+\ldots+t_m)^k$ all terms that contain at least one $t_1$, at least one $t_2$ and so on. In other words, the right hand side can be rewritten as $$ \sum_{\substack{d_0\ge 0,\,d_1\ldots,d_m\geq 1\\ d_0+d_1+\ldots+d_m=k}}t_{0}^{d_0}t_{1}^{d_1}\ldots t_{m}^{d_{m}}, $$ which is part of the multinomial.

The identity can be proved in various ways (e.g. induction, via difference operators), but my question is whether this inclusion-exclusion-like identity can be actually deduced from the inclusion-exclusion formula.

Let me now show some ideas in this direction. Let $A=\{t_0,t_1,\ldots,t_m\}$ and $A_{i}=A\setminus\{t_i\}$ for $1\le i\le m$. For each subset $S\subset A$ define $$ f(S)=\sum_{x_1,\ldots,x_k\in S}x_1x_2\ldots x_k=\left(\sum_{x\in S}x\right)^k. $$ Then, the left hand side of the identity can be rewritten as $$ f(A)-\sum_{i}f(A\cap A_i)+\sum_{i<j}f(A\cap A_i\cap A_j)-\ldots=\sum_{I\subset[m]}(-1)^{|I|}f\left(A\cap\bigcap_{i\in I}A_i\right) $$ Note the similar looking identity (this is basically the inclusion-exclusion formula) $$ |A|-\sum_{i}|A\cap A_i|+\sum_{i<j}|A\cap A_i\cap A_j|-\ldots=\sum_{I\subset[m]}(-1)^{|I|}\left|A\cap\bigcap_{i\in I}A_i\right|=|A\setminus (A_1\cup A_2\cup\ldots\cup A_m)|. $$ Now let us proceed to the proof of the identity (one can notice that the inclusion-exclusion formula above can be shown in the same way). The sketch is as follows: take any monomial $x_1\ldots x_k$, where $\{x_1,\ldots,x_k\}\subset A$ and denote $X=\{x_1,\ldots,x_k\}\setminus\{t_0\}\subset\{t_1,\ldots,t_m\}$, then in the summation above this monomial is "counted" with sign $(-1)^{|S|}$ for all subsets $S\subset\{t_1,\ldots,t_m\}$ such that $X\cap S=\varnothing$. Thus, the total coefficient of $x_1\ldots x_k$ is one if $X=\{t_1,\ldots,t_m\}$ and zero otherwise which proves the identity.

However, I think that it is possible to derive the identity directly from the inclusion-exclusion formula itself (instead of repeating the same argument). Is it really possible?

One possible approach is to pass to the indicator functions of subsets and "integrate" some function (i.e. consider expressions of the form $\int_{A\cap A_i}f$), but I do not see how apply it here.

An help would be appreciated.

Answer 1

Yes, this can be proven using the principle of inclusion exclusion. I will prove your identity in the case where $t_0,\dots,t_m$ are nonnegative integers. You can then use the theorem which states that, whenever two multivariate polynomials, $p(t_0,\dots,t_m)$ and $q(t_0,\dots,t_m)$, are equal for all nonnegative integer inputs, they have equal coefficients.

Let $T_0,T_1,\dots,T_m$ be disjoint sets such that $|T_i|=t_i$ for each $i\in \{0,1,\dots,m\}$.

Question: How many functions $f:[k]\to (T_0\cup T_1\cup \dots \cup T_m)$ are there, such that $\newcommand{\im}{\text{im}\,}(\im f)\cap T_j$ is nonempty for each $j\in \{1,\dots,m\}$?

I claim that both sides of your identity are answers to this question.

Right hand side

We need to prove that the number of functions is $$\sum_{\substack{0\le i_1,\ldots,i_k\le m\\ [m]\subseteq\{i_1,\ldots,i_k\}}}t_{i_1}\ldots t_{i_k}.$$ Given a function $f$, let $(i_1,\dots,i_k)$ be the integer list for which $f(j)\in T_{i_j}$ for each $j \in [k]$. That is, each $i_j\in \{0,1,\dots,m\}$ is the index of the $T$-part containing $f(j)$. The number of functions corresponding to the list $(i_1,\dots,i_k)$ is $t_{i_1}\cdots t_{i_k}$, because there are $t_{i_j}$ choices for the image of $j$. We then sum over all possible lists, with the condition that $[m]\subseteq \{i_1,\dots,i_k\}$ to ensure that $(\im f)\cap T_j$ is nonempty for each $j \in \{1,\dots,m\}$.

Left hand side

Here is where PIE comes into play. If we ignore the condition that $(\im f)\cap T_j$ must be nonempty for each $j\in [m]$, then the total number of functions is $(t_0+\dots+t_m)^k$. Let $A$ be the set of all such functions. Then, for each $j\in \{1,\dots,m\}$, let $A_j$ be the set of functions for which $(\im f)\cap A_j$ is empty. We want to count $|A\setminus (A_1\cup \dots \cup A_m)|$. Using PIE, this is exactly $$ |A|+\sum_{\varnothing \neq I\subseteq[m]}(-1)^{|I|}\left| \bigcap_{i\in I}A_i\right|\tag1 $$ It should be clear that $$ A_i=\Big((t_0+t_1+\dots++t_m)-t_i\Big)^k $$ because for each $j\in [k]$, $f(j)$ can be anything except for any element of $T_j$. Similarly, you can show, for any $I\subseteq [m]$, that $$ \left|\bigcap_{i\in I} A_i\right|=\left((t_0+\dots+t_m)-\sum_{i\in I} t_i\right)^k\tag2 $$ Combining $(1)$ and $(2)$, you get the sum on the LHS.