hallar la suma para cada n, k

Question

Para cada n, k hallar la suma de $ \sum {|A_{i_1} \cup A_{i_2} \cup ... \cup A_{i_k} | } $ en todos los conjuntos ordenados de $ (A_{i_1}, A_{i_2}, ... ,A_{i_k}) $ donde cada $ A_{i_j} \subseteq \{1, ..., n\} $

He descubierto que el número de términos diferentes en sigma es $ 2^{nk} $ y para $ k=1 $ obtuvo la respuesta de $ \sum_1^n i \binom{n}{i}$ que no estoy seguro de que sea correcto

Sólo quiero saber si hay una manera más fácil de resolver esto o si hay una fórmula para cada n,k

Answer 1

Llame a $c(n,k)$ el número de formas de escribir un conjunto con $n$ elementos como unión (exacta) de $k$ subconjuntos. Entonces tenemos $$ c(n,k)=\sum_{i=0}^n{n\choose i}\sum_{l=0}^i{i\choose l}c(n-i+l,k-1). $$ En efecto, supongamos $A_1\cup\ldots\cup A_k=\{1,\ldots,n\}$ . En primer lugar, supongamos que $A_1$ tiene $i$ elementos, donde $i=0,1,2\ldots,n$ . Entonces existe exactamente $n\choose i$ opciones para $A_1$ . Pero entonces, $A_2\cup\cdots\cup A_k$ debe contener al menos todos los elementos restantes de $\{1,\ldots,n\}$ Además, puede contener $l$ elementos de $A_1$ también. Así que supongamos que $A_2\cup\cdots\cup A_k$ contiene exactamente $l$ elementos de $A_1$ donde $l=0,1,2\ldots,i$ . Por lo tanto, existe exactamente $i\choose l$ opciones para $l$ elementos de $A_1$ y $c(n-i+l,k-1)$ posibles opciones para $A_2\cup\cdots\cup A_k$ .

Una inducción elemental revela que $c(n,k)=(2^k-1)^n$ .

Ahora, dejemos que $s(n,k)$ sea el valor de la suma que se quiere calcular. Podemos escribir \begin{align*} s(n,k)&=\sum_{i=0}^ni{n\choose i}c(i,k)=\sum_{i=0}^ni{n\choose i}(2^k-1)^i\\ &=n(2^k-1)\sum_{i=0}^n{n-1\choose i-1}(2^k-1)^{i-1}=n(2^k-1)2^{k(n-1)}. \end{align*}