In the process of computing [Shapley values](https://en.wikipedia.org/wiki/Shapley_value), I observed an interesting combinatorial constant. I am not exactly sure where such behavior comes. And here is the conjecture.


**Notations**


For any finite non-empty sequence of number $Q \subset \mathbb{R}$, I can construct a vector $C = (c\_0, c\_1, c\_2, \cdots, c\_{|Q|})$ using such a mapping $C(Q)$:
$$
 \sum\_{i=0}^{|Q|} c\_i x^ i = \prod\_{q\_i \in Q} (1+q\_ix)
$$


Given a sequence $A = a\_1, a\_2, \cdots, a\_m $, denote $A\_{\neg i}$ as $A \setminus \{a\_i\}$. $|A| = m$ denotes size/length of $A$ is $m$.
With size $m \in \mathbb{N}$, denote a constant vector $N(m)$ as $(1/{m-1 \choose 0}, 1/{m-1 \choose 1}, \cdots, 1/{m-1 \choose m-1 } )$. And $\langle\cdot, \cdot \rangle$ is the inner product operation.


**Conjecture**


For any finite non-empty sequence $A \subset \mathbb{R}$ with $|A| = m$, i conjecture if $0 \in A$ then:


$$
 \sum\_{i \in A} (1 - i) \langle C(A\_{\neg i}), N(m) \rangle = m
$$


I'm able to obtain consistent results from simulations, but I don't know how to prove it. Any help on a proof/dis-proof would be appreciated!


**Example**


For $A = 1, 2, 3$, the size $m$ is clearly 3.


$A\_{\neg 1} = 2, 3$, $A\_{\neg 2} = 1, 3$, $A\_{\neg 3} = 1, 2$


$C(A\_{\neg 1}) = (1, 5, 6)$, $C(A\_{\neg 2}) = (1, 4, 3)$, $C(A\_{\neg 3}) = (1, 3, 2)$.


$N(3) = (1, 0.5, 1)$


$$
(1-1)\* \langle (1, 5, 6), (1, 0.5, 1) \rangle \\
+ (1-2)\* \langle (1, 4, 3), (1, 0.5, 1) \rangle \\
 + (1-3)\* \langle (1, 3, 2), (1, 0.5, 1) \rangle \\
= -15
$$
which is not $m$.


On the other hand:
For $A=0, 2, 3$, the size $m$ is still 3.


$A\_{\neg 0} = 2, 3$, $A\_{\neg 2} = 0, 3$, $A\_{\neg 3} = 0, 2$


$C(A\_{\neg 0}) = (1, 5, 6)$, $C(A\_{\neg 2}) = (1, 3, 0)$, $C(A\_{\neg 3}) = (1, 2, 0)$.


$N(3) = (1, 0.5, 1)$


$$
(1-0)\* \langle (1, 5, 6), (1, 0.5, 1) \rangle \\
+ (1-2)\* \langle (1, 3, 0), (1, 0.5, 1) \rangle \\
 + (1-3)\* \langle (1, 2, 0), (1, 0.5, 1) \rangle \\
= 3
$$
which is $m$.



Conjecture on some combinatorial constant
We can rewrite $$\sum\_{i=0}^{|Q|} c\_i x^ i = \prod\_{q\_i \in Q} (1+q\_ix)$$ as $$c\_i = \sum\_{\substack{S \subseteq Q \\ |S| = i}} \prod\_{q \in S} q$$


Then $$\sum\_{a \in A} (1 - a) \langle C(A\_{\neg a}), N(m) \rangle$$ can be split into two sums: $$\left(\sum\_{a \in A} \langle C(A\_{\neg a}), N(m) \rangle \right) - \left(\sum\_{a \in A} a \langle C(A\_{\neg a}), N(m) \rangle \right)$$ Call the first sum $L$ (for lower) and the second sum $U$ (for upper). Note that $L$ only contains terms with products of $0$ to $m-1$ elements of $A$, and $U$ only contains terms with products of $1$ to $m$ elements of $A$.


Consider a subset $S \subset A$ of size $0 < k < m$. It occurs in $L$ once for every $a \in A \setminus S$ and each time with weight $\binom{m-1}{k}^{-1}$ from the dot product, for a total weight of $(m-k)\binom{m-1}{k}^{-1} = \frac{(m-k)!k!}{(m-1)!}$; it occurs in $U$ once for every $a \in S$ and each time with weight $\binom{m-1}{k-1}^{-1}$ from the dot product, for a total weight of $k\binom{m-1}{k-1}^{-1} = \frac{(m-k)!k!}{(m-1)!}$; and so all of these terms cancel.


Therefore the only terms which survive are the term from $L$ corresponding to the subset of size $0$ and the term from $U$ corresponding to the subset of size $m$. The former occurs with weight $\frac{(m-0)!0!}{(m-1)!} = m$; the latter with weight $\frac{(m-m)!m!}{(m-1)!} = m$ (but negated because of the subtraction).


Therefore the sum evaluates to $$m\left(1 - \prod\_{a \in A}a\right)$$


