Problema de combinatoria

Question

Considerar el conjunto 1,2,3,4,5,6,7,8 y la ecuación

$a+2b+3c+4d+5e+6f+7g+8h=S$

donde $a,b,c,d,e,f,g,h$ siguen siendo el conjunto de $1,2,3,4,5,6,7,8$.

Las permutaciones de $8!$ de a, b,... h determinar la variación de S en la gama [120.204]. Ahora, ¿cuántas veces es igual, por ejemplo, a 156 o, mejor, ¿cuántas permutaciones determinan S tomar el valor 156?

¿En palabras cortas, podemos resolver la ecuación anterior (y también determinar la distribución de S), sin por supuesto simplemente suma ejecutora u ordenador?

Answer 1

Pregunta interesante.

Creo que se puede, al menos, restringir el espacio de búsqueda un poco si usted está buscando para el cálculo de la frecuencia para un único valor de $S$.

Tome $h=8$. De hecho, existen algunos casos en los que se $h=8$$S = 156$. El valor mínimo de $S$ $h=8$ es

$$1(7) + 2(6) + 3(5) + 4(4) + 5(3) + 6(2) + 7(1) + 8(8) = 148.$$

El valor de os $S$ es la más sensible al valor de $h$, y la segunda-más sensible al valor de $g$. Lo que si establecemos $h=8, g=2$? El valor mínimo de $S$ es

$$1(7) + 2(6) + 3(5) + 4(4) + 5(3) + 6(1) + 7(2) + 8(8) = 149.$$

Además, $g = 3$ tiene un mínimo de $151$, e $g=4$ tiene un mínimo de $154$. Pero $g=5$ da un mínimo de$158$, que es mayor que $156$. Así que usted no tiene que preocuparse acerca de la búsqueda de los valores de $h=8, g=5,6,7$. Más de dos mil casos (de cerca de cuarenta mil) usted no tiene que preocuparse acerca de.

A continuación, para cada una de las $h=8, g=1,2,3,4$, aumentar el valor de $f$ hasta su mínimo supera $156$, y tirar esos casos.

Para $h=7, g=6$ el mínimo es $156$. Ese es el único caso. Usted puede tirar todos los casos para $h=7, g=8$.

Para $h=6$ hacia abajo, usted tiene que comprobar todos los valores de $g$ con base en este criterio.

Empezar desde el otro extremo: $h=1$. El máximo valor de$S$$176$. Disminuir el $g$ a ver si usted puede conseguir la máxima cantidad por debajo de la $156$. Y usted puede: $h=1, g=2$. Lanzar los.

Como usted ve, usted también puede tomar ventaja del hecho de que $156$ es incluso. Usted puede tirar de los casos para que exactamente uno, o tres, de $a,c,e,g$ son impares, porque la suma es impar.

Por que ser inteligentes acerca de lo que usted calcular, usted puede deshacerse de un montón de sus casos y no un ciclo a través de todos ellos.

No veo una manera de obtener una distribución completa sin calcular todos ellos, sin embargo.