Formulación de una suma alterna de combinaciones de productos

Question

Formulación de una suma alterna de combinaciones de productos

productos
suma
Matemáticas
combinatoria
exclusión inclusión

Gravitón

Considere alguna lista $A=(a_1,a_2,\cdots,a_n)$ . Me gustaría encontrar un formulario cerrado para la siguiente operación.

F (A) = \sum_{k = 1}^{norte} (- 1)^{k - 1} s_{k} = s_{1} - s_{2} + \dots (- 1)^{norte - 1} s_{norte} .

$f(A)=\sum_{k=1}^n(-1)^{k-1}s_k= s_1-s_2+\cdots(-1)^{n-1}s_n.$ Dónde

s_{k}

$s_k$ es la suma de todas las combinaciones de productos de

k

$k$ elementos únicos de

A

$A$ . Por ejemplo, si

A = (x, y, z)

$A=(x,y,z)$ , entonces

s_{1} = X + y + z,

$s_1=x+y+z,$

s_{2} = X y + X z + y z,

$s_2=xy+xz+yz,$

s_{3} = X y z .

$s_3=xyz.$ De este modo

f (A) = (x + y + z) - (x y + x z + y z) + (x y z)

$f(A)=(x+y+z)-(xy+xz+yz)+(xyz)$ .

¿Cuál es la forma "más agradable" de formular esta suma de productos?

¿Esta operación es conocida/común en combinatoria?

Lo mejor que se me ocurre es

\sum_{k = 1}^{norte} (- 1)^{k - 1} \prod_{a \in {PAG}_{norte} (A)} a

$\sum_{k=1}^n(-1)^{k-1}\prod_{a\in\mathcal{P}_n(A)}a$ dónde

P_{n} (A)

$\mathcal{P}_n(A)$ denota el conjunto de todos los subconjuntos en

A

$A$ con cardinalidad

n

$n$ . Sin embargo, sería bueno tener esto en alguna "forma estándar" sin el uso de powersets (y mucho menos la generalización de los mismos). Mi alarma del teorema del binomio está sonando; por lo tanto, imagino que hay una forma cerrada más agradable que hace uso de coeficientes binomiales.

Cualquier idea o consejo sería muy apreciado.

Gravitón

Al verificar algunos valores de prueba, parece igualar

1 - \prod_{k = 1}^{n} (1 - a_{k})

$1-\prod_{k=1}^n(1-a_k)$ al menos para los casos que he comprobado

n = 3

$n=3$ ; aunque la prueba no es inmediatamente obvia para mí.

Vezen BU

Este formulario me recuerda el llamado principio de inclusión-exclusión ( en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle )

Gravitón

@VezenBU ¡Guau! Parece que hemos encontrado una dualidad de hecho. Esto surgió mientras estudiaba lógica difusa, por lo que ciertamente hay una conexión.

Respuestas (1)

Formulación de una suma alterna de combinaciones de productos

Al verificar algunos valores de prueba, parece igualar $1-\prod_{k=1}^n(1-a_k)$ al menos para los casos que he comprobado $n=3$ ; aunque la prueba no es inmediatamente obvia para mí.
Este formulario me recuerda el llamado principio de inclusión-exclusión ( en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle )
@VezenBU ¡Guau! Parece que hemos encontrado una dualidad de hecho. Esto surgió mientras estudiaba lógica difusa, por lo que ciertamente hay una conexión.

Vezen BU · Answer 1

Lo que tienes es correcto. Usamos directamente la expansión binomial para obtener

\begin{aligned} \prod_{k = 1}^{norte} (1 - a_{k}) & = \sum_{j = 0}^{norte} \sum_{C \in (\binom{[norte]}{j})} \prod_{C \in C} - a_{C} \\ = \sum_{j = 0}^{norte} \sum_{C \in (\binom{[norte]}{j})} (- 1)^{j} \prod_{C \in C} a_{C} \\ = 1 + \sum_{j = 1}^{norte} \sum_{C \in (\binom{[norte]}{j})} (- 1)^{j} \prod_{C \in C} a_{C} \\ = 1 + \sum_{j = 1}^{norte} (- 1)^{j} \sum_{C \in (\binom{[norte]}{j})} \prod_{C \in C} a_{C} \\ = 1 - \sum_{j = 1}^{norte} (- 1)^{j - 1} \sum_{C \in (\binom{[norte]}{j})} \prod_{C \in C} a_{C} \\ = 1 - \sum_{j = 1}^{norte} (- 1)^{j - 1} s_{j} \end{aligned}

$\begin{align} \prod_{k =1}^n (1-a_k) &= \sum_{j = 0}^n \sum_{C \in \binom{[n]}{j}} \prod_{c \in C} -a_c \\ &= \sum_{j = 0}^n \sum_{C \in \binom{[n]}{j}} (-1)^{j} \prod_{c \in C} a_c \\ &= 1 + \sum_{j = 1}^n \sum_{C \in \binom{[n]}{j}} (-1)^{j} \prod_{c \in C} a_c \\ &= 1 + \sum_{j = 1}^n (-1)^{j} \sum_{C \in \binom{[n]}{j}} \prod_{c \in C} a_c \\ &= 1 - \sum_{j = 1}^n (-1)^{j - 1} \sum_{C \in \binom{[n]}{j}} \prod_{c \in C} a_c \\ &= 1 - \sum_{j = 1}^n (-1)^{j - 1} s_j \end{align}$

Formulación de una suma alterna de combinaciones de productos

Gravitón

Gravitón

Vezen BU

Gravitón

Respuestas (1)

Vezen BU

Simplificando el producto de múltiples expansiones binomiales

Reorganización de sumas alternas de productos de coeficientes binomiales

Prueba combinatoria de la identidad 3n=∑nk=0(nk)2k3n=∑k=0n(nk)2k3^n=\sum_{k=0}^n \binom nk 2^k

Cómo mostrar esta identidad ∏kq=111−qz=∑kj=1jz∏jq=111−qz+1∏q=1k11−qz=∑j=1kjz∏q=1j11−qz+1\prod_{q=1} ^k\frac{1}{1-qz}=\sum_{j=1}^{k}jz\prod_{q=1}^j\frac{1}{1-qz}+1 evitando una prueba por inducción

Pregunta de prueba de suma binomial/combinatoria

Suma del producto de coeficientes binomiales: ∑nk=0(−1)k(nk)(n+kk)=(−1)n∑k=0n(−1)k(nk)(n+kk)=(− 1)n\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n

Error lógico en problema de probabilidad sobre cartero entregando cartas para que cada casa reciba una carta equivocada

Problema de Combinatoria (Bajar de un ascensor)

Número de arreglos de asientos circulares si cada persona no puede sentarse junto a otras dos personas

Simplificar un producto de sumatorias