Conjecture on some combinatorial constant

In the process of computing Shapley values, 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$$.

• So, if I'm correctly understanding your question, you are claiming that if $a_1, a_2, \ldots, a_m$ are $m$ numbers, and if $k$ is a nonnegative integer, then $\sum\limits_{i=1}^k \dfrac{e_k\left(a_1, a_2, \ldots, \widehat{a_i}, \ldots, a_m\right)}{\dbinom{m-1}{k}} - \sum\limits_{i=1}^k a_i \dfrac{e_{k-1}\left(a_1, a_2, \ldots, \widehat{a_i}, \ldots, a_m\right)}{\dbinom{m-1}{k-1}}$ equals $0$ when $k$ is positive and equals $m$ if $k = 0$. Here, $e_k$ means the $k$-th elementary symmetric polynomial (which is $0$ if $k$ is negative). This should be easy: compute each monomial's coefficient. Nov 24, 2021 at 23:07
• And easy it is: The coefficient of a given monomial $a_{i_1} a_{i_2} \cdots a_{i_k}$ (with $i_1, i_2, \ldots, i_k$ being distinct) is $\dfrac{m-k}{\dbinom{m-1}{k}} - \dfrac{k}{\dbinom{m-1}{k-1}} = 0$. All other monomials have coefficient $0$ since they appear in neither of the two sums. Nov 24, 2021 at 23:10
• not completely sure I follow the newly constructed term, but $0 \in A$ is the condition, basically at least one of $a_1, \cdots, a_m$ is 0. Nov 24, 2021 at 23:11
• That condition isn't necessary. Nov 24, 2021 at 23:11
• @yupbank: I will after tomorrow's FPSAC deadline. Nov 25, 2021 at 5:19

1 Answer

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)$$

• I'm sure Darij won't mind me answering, even though the argument is essentially the same as his. Nov 25, 2021 at 14:37