Suma de los elementos de todos los subconjuntos

Tomemos el conjunto formado por los n primeros números naturales {1, 2, 3, …, n}. Imagina que formamos todos los subconjuntos posibles y que en cada uno sumamos los elementos, acumulando después todas las sumas en un total general ¿Cuánto valdrá esa suma S(n) de todos los elementos de todos los subconjuntos? Al conjunto vacío le asignamos suma 0.

Te damos un ejemplo:

S(4)=80, porque tendríamos que sumar (escribimos entre paréntesis la suma parcial de cada subconjunto) lo siguiente: (0)+(1)+(2)+(3)+(4)+(1+2)+(1+3)+(1+4)+(2+3)+(2+4)+(3+4)+(1+2+3)+(1+2+4)+(1+3+4)+(2+3+4)+(1+2+3+4)=10+3+4+5+5+6+7+6+7+8+9+10=27+26+27=80

Los primeros resultados para la función S son S(1)=1; S(2)=6; S(3)=24; S(4)=80; S(5)= 240; S(6)=672, formando la sucesión 1, 6, 24, 80, 240, 672, 1792, 4608, 11520, 28160, 67584, 159744...

Intentemos justificar estos resultados

Podemos encontrar una definición por recurrencia. Que S(1)=1 y S(2)=6 es fácil de justificar. A partir de ahí razonamos de una forma muy común en Combinatoria: Sea S_n-1 la suma de los subconjuntos de {1, 2, 3, …, n-1}. Para formar la suma S_n deberemos añadir el elemento n a los subconjuntos.

Entonces estos serán de dos formas:

(a) Subconjuntos que no contienen al elemento n. Su suma será la misma S_n-1

(b) Subconjuntos que contienen al elemento n. Estarán formados por los subconjuntos de 1, 2, 3, …, n-1} a los que añadimos a cada uno el elemento nuevo n. El número de tales subconjuntos equivale a 2^n-1. Como cada uno se ha incrementado en el elemento n, la suma se habrá incrementado en n*2^n-1. Luego será S_n-1+ n*2^n-1.

Si reunimos las sumas (a) y (b) nos resulta la fórmula de recurrencia:

       S_n=2S_n-1+ n*2^n-1

En efecto: S(3)=2*6+3*4=12+12=24;  S(4)=2*24+4*8=48+32=80; S(5)=2*80+5*16=160+80=240.

Es fácil programarlo en hoja de cálculo. Sólo incluimos una tabla creada así sin dar más detalles:

S(n)      2n-1    n
1           1         1
6           2         2
24         4         3
80         8         4
240      16        5
672      32        6
1792    64        7
4608  128        8

Generalmente nos sentimos más a gusto con una fórmula algebraica. Ahí va:

        S(n)=n(n+1)2^n-2

S(1)=1*2*(1/2)=1; S(2)=2*3*1=6; S(3)=3*4*2=24; S(4)=4*5*4=80…

Se puede demostrar por inducción. Vemos que se cumple para los primeros casos, luego podemos suponer que se cumple para n-1, es decir, que S_n-1=(n-1)*n*2^n-3.

Aplicamos la fórmula de recurrencia presentada más arriba y nos queda:

S_n=2*(n-1)*n*2^n-3+n*2^n-1=(n²-n)* 2^n-2+2*n*2^n-2=(n²-n+2n)* 2^n-2=n(n+1)2^n-2  lo que completa la demostración.

Otra demostración

La suma T=1+2+3+4+…+n equivale al número triangular n(n+1)/2. Esta suma se repite en S(n) varias veces. Por ejemplo, la suma de todos los elementos unitarios es T. También vale T la suma de elementos del conjunto total. Veamos los demás conjuntos:

Clasifiquemos los subconjuntos por su número de elementos.  El número de los que tienen r elementos es Cn,r. Por razones de simetría, los elementos 1,2,3,…n se repiten en total, para un mismo r, igual número de veces, luego la suma de los elementos de estos subconjuntos es múltiplo de T.

Cada elemento se repite en los conjuntos de r elementos tantas veces como indique Cn-1,r-1, luego la suma de todos equivaldrá a Cn-1,r-1*T. Si sumamos todos nos dará:

T*Cn-1,0+T* Cn-1,1+ T* Cn-1,2+ T* Cn-1,3+…+ T* Cn-1,n-1 = T*2^n-1 = n(n+1)/2*2^n-1 = n(n+1)*2^n-2 , que es la fórmula propuesta.

¿Se te escapó algún detalle? Repasa, repasa…

Quienes acostumbráis a visitar OEIS habréis descubierto que estas sumas forman la secuencia http://oeis.org/A001788.  Si la estudiáis  podréis descubrir la gran cantidad de interpretaciones que tiene.