convolución de todos los arreglos de un multiconjunto

Question

Te dan el conjunto de números 2,7,8,9,9,23,33,41,41,57 y quieres hallar la suma de todas las circunvoluciones de la posible disposición de estos diez términos. Cada disposición se convoluciona consigo misma. Se puede hallar la respuesta examinando caso por caso cada disposición, pero esto resulta impracticable si el número de términos es superior a diez. ¿Existe algún método más rápido para hallar la suma de todas estas circunvoluciones?

Answer 1

Supongamos que el multiconjunto $M$ tiene términos únicos $x_1,x_2,x_3,\ldots,x_k$ con estos términos que aparecen $n_1,n_2,n_3,\ldots,n_k$ veces cada uno.

Entonces el número total de elementos únicos es $\displaystyle T(M)=\sum_{i=1}^k n_i$ y el número total de arreglos es $\displaystyle A(M)=\frac{T(M)!}{\prod_i n_i!}$ con la advertencia de que $A(M)=0$ si alguno de los $n_i$ son negativos.

Considera también los conjuntos múltiples: $M_{-i}$ donde $n_i$ se reduce en $1$ y $M_{-i-j}$ donde $n_i$ y $n_j$ se reducen en $1$ ( $i$ y $j$ pueden ser iguales o diferentes: si son iguales, significa que $n_i$ se reduce en $2$ ).

Entonces sospecho que su resultado es algo así como

$$\displaystyle 2\big\lfloor \tfrac{T(M)}{2} \big\rfloor\left( \sum_{i=1}^k \sum_{j=1}^k x_i x_j A(M_{-i-j}) \right) + \left(T(M)-2\big\lfloor\tfrac{T(M)}{2}\big\rfloor \right)\left( \sum_{i=1}^k x_i^2 A(M_{-i}) \right) $$ y puede factorizar $A(M)$ utilizando $A(M_{-i}) = A(M)\frac{n_i}{T(M)}$ , $A(M_{-i-i}) = A(M)\frac{n_i(n_i-1)}{T(M)(T(M)-1)}$ y $A(M_{-i-j}) = A(M)\frac{n_i n_j}{T(M)(T(M)-1)}$ cuando $i\not = j$ . [Añadido] En $2\big\lfloor \tfrac{T(M)}{2} \big\rfloor$ término es $T(M)$ cuando este es par y $T(M)-1$ cuando $T(M)$ es impar, mientras que el $\left(T(M)-2\big\lfloor\tfrac{T(M)}{2}\big\rfloor \right)$ término es $0$ cuando $T(M)$ es par y $1$ cuando $T(M)$ es impar.

Si haces eso y luego dejas que $\displaystyle S(M)=\sum_{i=1}^k n_i x_i$ es decir, la suma sobre el multiconjunto, y que $\displaystyle Q(M)=\sum_{i=1}^k n_i x_i^2$ es decir, la suma de cuadrados sobre el multiconjunto, entonces creo que se obtiene el bastante simple

$$\dfrac{A(M)\left(S(M)^2 - Q(M) \right) }{(T(M)-1)} \text{ when } T(M) \text{ is even}$$

$$\dfrac{A(M)\,S(M)^2 }{T(M)} \text{ when } T(M) \text{ is odd}$$

Para el ejemplo de juguete de $M=\{8,9,9\}$ Esto tiene $x_1=8,x_2=9,n_1=1,n_2=2$ y así $T(M)=1+2=3$ y $A(M)=\frac{3!}{1! \times 2!}=3$ , $S(M)=8+9+9=26$ , $Q(M) = 8^2+9^2+9^2 = 226$ por lo que el resultado es $\frac{3\times 26^2}{3} = 676$ como se esperaba

Answer 2

[Nota: Creo que mi solución es ligeramente diferente a la de Henry y ya tenía gran parte escrita, así que la publicaré de todos modos].

Supongamos en primer lugar que el multiconjunto no contiene ningún elemento repetido, de modo que sus elementos $\{a_1, \ldots, a_n\}$ son distintos.

Supongamos primero $n$ es par. Sea $a_i$ y $a_j$ sea cualquier par de elementos del multiconjunto, y cuente el número de arreglos en los que el producto $a_ia_j$ se utiliza en la convolución. Existen $n$ lugares para $a_i$ y sólo una opción para $a_j$ ; los elementos restantes pueden distribuirse arbitrariamente en $(n-2)!$ formas. Para cada una de estas $n(n-2)!$ este par aporta un sumando de $2a_ia_j$ a la convolución; por tanto, a la suma de todas las convoluciones, este par contribuye con un total de $2a_ia_jn(n-2)!$ . Por lo tanto, la suma de todas las circunvoluciones es: $$\displaystyle 2n(n-2)!\sum_{1 \le i < j \le n} a_ia_j$$

Si $n$ es impar, podemos dejar de nuevo que $a_i$ y $a_j$ sea cualquier par de elementos del multiconjunto, y cuente el número de arreglos en los que el producto $a_ia_j$ se utiliza en la convolución. Dado que $n$ es impar, sólo hay $n-1$ lugares para $a_i$ ya que no puede ir en la posición central. Pero el resto del cálculo es el mismo, lo que significa que esta pareja aporta un total de $2a_ia_j(n-1)!$ a la suma de todas las circunvoluciones. A diferencia del caso par, un solo elemento $a_i$ puede contribuir a la circunvolución sin pareja situándose en la posición intermedia, donde aporta $a_i^2$ a la convolución. Este término aparece en $(n-1)!$ de acuerdos, añadiendo un total de $a_i^2(n-1)!$ a la suma de todas las circunvoluciones. Por lo tanto, la suma total de convolución en este caso es: $$\displaystyle 2(n-1)!\sum_{1 \le i < j \le n} a_ia_j + (n-1)!\sum_{i=1}^n a_i^2$$

Supongamos ahora que nuestro multiconjunto está formado por elementos distintos $b_1 \ldots b_m$ , $b_i$ tiene multiplicidad $n_i$ y que $n = \sum n_i$ . Por el momento, trate el $n$ elementos del multiconjunto como objetos distintos, aunque algunos puedan tener el mismo valor numérico. Entonces, el análisis anterior seguiría dando la suma total de la convolución sobre todos los $n!$ arreglos.

Al querer tratar los objetos del mismo valor numérico como equivalentes, estamos creando esencialmente clases de equivalencia sobre el conjunto de $n!$ arreglos de nuestros objetos distintos de tal manera que dos arreglos son equivalentes si ambos arreglos tienen el mismo ordenamiento de valores numéricos. Evidentemente, cada clase de equivalencia tiene $\prod_{i=1}^m n_i!$ y, además, la convolución de cada elemento de la clase de equivalencia es la misma. Dado que cada sumando que contribuye a la suma total de la convolución se cuenta exactamente este número de veces, podemos obtener la respuesta deseada simplemente dividiendo las cantidades anteriores por $\prod_{i=1}^m n_i!$ para obtener las fórmulas:

Para $n$ incluso: $$\frac{2n(n-2)!}{\prod_{i=1}^m n_i!} \left( \displaystyle \sum_{1 \le i < j \le m}b_in_ib_jn_j + \sum_{i=1}^m\frac{n_i(n_i-1)}{2}b_i^2 \right)$$

Para $n$ impar: $$\frac{(n-1)!}{\prod_{i=1}^m n_i!} \left( \displaystyle \sum_{1 \le i < j \le m}2b_in_ib_jn_j + \sum_{i=1}^m n_i^2b_i^2 \right)$$

Answer 3

Supongamos por el momento que el multiconjunto $S$ contiene $n$ enteros únicos y que $x$ sea un vector de estos números enteros. Sea $R$ denotan el $n\times n$ matriz de orden inverso y que $P$ denotan un $n\times n$ matriz de permutación correspondiente a cualquiera de las $n!$ permutaciones $\sigma$ de $\{1,\ldots,n\}$ . Entonces la convolución de cualquier arreglo de $S$ puede expresarse como $x^TP^TRPx$ . Sea $Q$ denota la suma de todas las matrices de la forma $P^TRP$ . De ello se deduce que la suma de todas las convoluciones posibles viene dada por $x^TQx$ . Sólo queda determinar los elementos de $Q$ . Consideremos una matriz de la forma $P^TRP$ correspondiente a la permutación $\sigma$ . Por la naturaleza de $P$ y $R$ se deduce que $$ (P^TRP)_{ij} = p_i^TRp_j = \left\{ \begin{array}{ll} 1 & \text{if}~\sigma^{-1}(i) = n - \sigma^{-1}(j) + 1\\ 0 & \text{otherwise} \end{array}\right. $$ para todos $i,j = 1,\ldots,n$ . Por lo tanto, por un simple argumento de recuento $$ q_{ij} = \left\{ \begin{array}{ll} 0 & n~\text{even},~i = j\\ n(n-2)! & n~\text{even},~i \neq j\\ (n-1)! & n~\text{odd}\\ \end{array}\right. $$ Consideremos ahora el caso en que $S$ consiste en $k$ elementos distintos repetidos $n_1,\ldots,n_k$ veces. Sea $n = n_1 + \cdots + n_k$ . Luego están $$ \frac{n!}{n_1!n_2!\cdots n_k!} $$ permutaciones únicas de $S$ por lo que hemos contado de más por un factor de $N = (n_1!n_2!\cdots n_k!)$ . Así pues, la solución general es $$ \frac{1}{N}x^TQx. $$ Por último, observamos que $Q$ es simétrica, lo que reduce aún más el trabajo para calcular la suma. Evidentemente, una rutina de cálculo no formaría $Q$ explícitamente pero preferiría codificar el producto $x^TQx$ para reducir la sobrecarga de memoria.