Rewriting summation in binomial form - counting problem

40 Views Asked by At

Let $A$ be a player set and $Q$ a subset, which has been given. Furthermore, players $x,y,z \in A$. I have already managed to rewrite the following summation (where I set $n=|A|-|Q \cup \{ x,y \}|$ and $i=|S|-|Q \cup \{ x,y \}|$):

$\sum_{\substack{Q \subseteq S \subseteq A \\ \{x,y\} \subseteq S }} (-1)^{|S|-|Q|} = \begin{cases} \sum_{i=0}^{n} {n \choose i} (-1)^{i} \ \text{for $Q$ containing both $x,y$ or neither.} \\ \sum_{i=0}^{n} {n \choose i} (-1)^{i+1} \ \text{for $Q$ containing $x$ or $y$ (not both).} \end{cases}$

The latter expression is a form which gives more insight in terms of counting. Now I am trying to rewrite a similar summation, in the same way as the example above, but I am not succeeding yet:

$\sum_{\substack{Q \subseteq S \subseteq A \\ \{x,z\} \subseteq S \ \text{or} \ \{y,z\} \subseteq S }} (-1)^{|S|-|Q|} = ... $.

I have already tried doing this by taking easy examples with a small number of players, e.g. $A=\{a,x,y,z\}$ and $Q = \emptyset$. Then the choices for $S$ would be $\{ x,z \}$, $\{ y,z \}$, $\{ a,x,z \}$, $\{ a,y,z \}$, $\{ x,y,z \}$, $\{ a,x,y,z \}$, and thus the summation should equal $0$. However, I can't find an equivalent representation of this summation, like in the example.

I hope anyone can help me with finding this! :)

In the comment below I stated my suspected expression, for which the challenge is: how to prove the equality with the Kronecker Delta function?