Conjetura sobre una constante combinatoria

Question

En el proceso de cálculo Valores de Shapley observé una interesante constante combinatoria. No estoy exactamente seguro de dónde viene este comportamiento. Y aquí está la conjetura.

Anotaciones

Para cualquier secuencia finita no vacía de números $Q \subset \mathbb{R}$ puedo construir un vector $C = (c_0, c_1, c_2, \cdots, c_{|Q|})$ utilizando dicho mapeo $C(Q)$ : $$ \sum_{i=0}^{|Q|} c_i x^ i = \prod_{q_i \in Q} (1+q_ix) $$

Dada una secuencia $A = a_1, a_2, \cdots, a_m $ , denotan $A_{\neg i}$ como $A \setminus \{a_i\}$ . $|A| = m$ denota el tamaño/longitud de $A$ es $m$ . Con el tamaño $m \in \mathbb{N}$ , denotan un vector constante $N(m)$ como $(1/{m-1 \choose 0}, 1/{m-1 \choose 1}, \cdots, 1/{m-1 \choose m-1 } )$ . Y $\langle\cdot, \cdot \rangle$ es la operación de producto interno.

Conjetura

Para cualquier secuencia finita no vacía $A \subset \mathbb{R}$ con $|A| = m$ , conjeturo que si $0 \in A$ entonces:

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

Soy capaz de obtener resultados consistentes a partir de simulaciones, pero no sé cómo demostrarlo. ¡Se agradecería cualquier ayuda sobre una prueba/descomprobación!

Ejemplo

Para $A = 1, 2, 3$ el tamaño $m$ es claramente 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 $$ que no es $m$ .

Por otro lado: Para $A=0, 2, 3$ el tamaño $m$ sigue siendo 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 $$ que es $m$ .

Answer 1

Podemos reescribir $$\sum_{i=0}^{|Q|} c_i x^ i = \prod_{q_i \in Q} (1+q_ix)$$ como $$c_i = \sum_{\substack{S \subseteq Q \\ |S| = i}} \prod_{q \in S} q$$

Entonces $$\sum_{a \in A} (1 - a) \langle C(A_{\neg a}), N(m) \rangle$$ puede dividirse en dos sumas: $$\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)$$ Llama a la primera suma $L$ (para los más bajos) y la segunda suma $U$ (para arriba). Tenga en cuenta que $L$ sólo contiene términos con productos de $0$ a $m-1$ elementos de $A$ y $U$ sólo contiene términos con productos de $1$ a $m$ elementos de $A$ .

Considere un subconjunto $S \subset A$ de tamaño $0 < k < m$ . Se produce en $L$ una vez por cada $a \in A \setminus S$ y cada vez con peso $\binom{m-1}{k}^{-1}$ del producto punto, para un peso total de $(m-k)\binom{m-1}{k}^{-1} = \frac{(m-k)!k!}{(m-1)!}$ ; se produce en $U$ una vez por cada $a \in S$ y cada vez con peso $\binom{m-1}{k-1}^{-1}$ del producto punto, para un peso total de $k\binom{m-1}{k-1}^{-1} = \frac{(m-k)!k!}{(m-1)!}$ y así todos estos términos se anulan.

Por lo tanto, los únicos términos que sobreviven son el término de $L$ correspondiente al subconjunto de tamaño $0$ y el término de $U$ correspondiente al subconjunto de tamaño $m$ . El primero se produce con el peso $\frac{(m-0)!0!}{(m-1)!} = m$ ; este último con peso $\frac{(m-m)!m!}{(m-1)!} = m$ (pero negado por la sustracción).

Por lo tanto, la suma se evalúa como $$m\left(1 - \prod_{a \in A}a\right)$$