¿De cuántas maneras puede particionar un conjunto de n enteros consecutivos para que la suma de cada conjunto en la partición sea la misma?

Answer 1

Creo que lo que está preguntando es “¿de cuántas maneras hay para dividir los primeros N enteros de modo que la suma de cada conjunto sea la misma?” Es decir, “¿los conjuntos exhaustivos no superpuestos? asignarse a un conjunto y no se asignará ningún número a más de un conjunto. La definición estándar para tal asignación es una partición .

Las razones por las que restringí el problema a los primeros N enteros es porque, de lo contrario, la respuesta depende de dónde empiezas a contar, de una manera que parece difícil de acomodar en una respuesta general. Por ejemplo, {1, 2, 3} y se particionará en {1,2}, {3}, pero {10, 11, 12} no se puede particionar de ninguna otra forma que no sea la partición trivial en un solo conjunto. Del mismo modo, {4, 5, 6, 7, 8} se pueden particionar {4, 5, 6}, {7, 8} pero el conjunto {1, 2, 3, 4, 5} no tiene esa partición. Tampoco elegí cero como inicio porque eso agrega muchas posibilidades simplemente barajando el cero.

No veo de inmediato cómo calcular esto, así que tomemos algunos pequeños ejemplos y veamos si podemos hacer algunas conjeturas o encontrar una respuesta en el OEIS.

{1} se puede dividir solo de 1 manera, y de esa manera se cumple la condición de suma igual trivialmente.

{1,2} solo se puede particionar de manera trivial también.

{1,2,3} se puede dividir como {1,2,3} o {1,2} {3}

{1,2,3,4} se puede dividir como {1,2,3,4} o {1,4}, {2,3}

{1,2,3,4,5} se da y {1,4}, {2,3}, {5}. Debido a que la suma es impar, no se puede dividir en dos conjuntos iguales, por lo que no tenemos que seguir buscando.

{1,2,3,4,5,6} se da a sí mismo y a los pares {1,6}, {2,5}, {3,4}. Su suma 21 es impar y divisible por 3 pero no por 4.

{1,2,3,4,5,6,7} sigue el patrón de N = 5, dando {1,6}, {2,5}, {3,4}, {7}. Sin embargo, la suma 28 es divisible por 14, dándonos nuestros primeros ejemplos no triviales, con las particiones adicionales que suman 14: {3,4,7}, {1,2,5,6} y {1,2,4, 7}, {3,5,6} y {1,6,7}, {3,4,5,6} y {2,5,7}, {1,3,4,6}. Eso nos da un total de 6 particiones.

{1,2,3,4,5,6,7,8} tiene un total de 36. Mirando sistemáticamente los grandes divisores de 36, tenemos particiones:

36 = {1,2,3,4,5,6,7,8}

18 = {1,2,7,8} {3,4,5,6} y variaciones donde dividimos los pares que suman a 9 en los dos conjuntos. Pero también {8,7,3} {1,2,4,5,6} y {8,6,4}, {1,2,3,5,7} y {8,1,2,3, 4} {5,6,7} y tal vez otros.

9 = emparejamientos triviales

Así que estamos haciendo demasiados para asegurarme de que estoy contando con precisión, escribamos un código. Podemos aplicar fuerza bruta a todas las particiones hasta N = 13 más o menos sin demasiada dificultad. Usé el código aquí: establecer particiones en Python.

La secuencia resultante es 1, 1, 2, 2, 2, 2, 6, 12, 11, 2, 80, 166, 2

Como se esperaba, encontramos exactamente esa secuencia en OEIS: A035470 donde hay 34 entradas en la lista, y algo de código Maple para calcular el resultado (que usa un algoritmo algo más eficiente, pero aún realiza fundamentalmente la búsqueda). Los valores conocidos son:

# A035470 (archivo b sintetizado a partir de la entrada de secuencia)
1 1
2 1
3 2
4 2
5 2
6 2
7 6
8 12
9 11
10 2
11 80
12 166
13 2
14 665
15 2918
16 3309
17 9296
18 23730
19 31875
20 301030
21 422897
22 2
23 13716867
24 71504980
25 100664385
26 54148591
27 880696662
28 498017759
29 27450476787
30 111911522819
31 179459955554
32 2144502175214
33 59115423983
34 45837019664552

Si tuviera que calcular con éxito valores para 35 o más, ¡probablemente pueda agregarlos a la lista! Pero parece que nadie tiene un enfoque que sea mejor que escribir un algoritmo para contar.

Podemos encontrar los casos en los que la respuesta es ‘2’ buscando casos en los que [math] n (n + 1) / 2 [/ math] tenga solo un divisor no trivial más pequeño que [math] n [/ math]. Por ejemplo, N = 22 nos da la suma de números consecutivos [matemática] 253 = 11 \ por 23 [/ matemática]. Eso significa que solo se puede dividir en un conjunto o en 11 conjuntos.

Los siguientes valores con esta propiedad son N = 46, N = 58, N = 82, N = 106, N = 166 y N = 178.