Creo que puede haber querido preguntar sobre pares de enteros positivos que suman n. Pero los conjuntos de enteros positivos que suman n es una pregunta más interesante.
Veamos algunos pequeños ejemplos y veamos si hay un patrón (o haz trampa y búscalo en OEIS).
n = 1: {1}, un conjunto
n = 2: {2}, un conjunto
- ¿Es (A x B) intersección B x B, lo mismo que (A x B) intersección (B x B)?
- ¿Por qué el elemento de un conjunto no es un subconjunto del conjunto, y viceversa?
- ¿Cuáles son los dos últimos dígitos de 111 subir a 222 subir a 333?
- ¿Cuáles son algunos algoritmos que pueden experimentar beneficios de rendimiento al reemplazar funciones con búsquedas de tablas? (es decir, seno, cuadrar un número, raíz cuadrada, coseno)?
- Cómo encontrar n números para que el producto de los números sea igual a su suma, siempre que cada uno de los números sea un entero positivo
n = 3, {3}, {1,2}, dos conjuntos
n = 4, {4}, {1,3}, dos conjuntos
n = 5, {5}, {1,4}, {3,2}, tres conjuntos
n = 6, {6}, {1,5}, {2,4}, {3,2,1}, cuatro conjuntos
n = 7, {7}, {1,6}, {2,5}, {3,4}, {4,2,1}, cinco conjuntos
n = 8, {8], {1,7}, {2,6}, {3,5}, {5,2,1}, {4,3,1}, seis conjuntos
n = 9, {9}, {1,8}, {2,7}, {3,6}, {4,5}, {6,2,1}, {5,3,1}, {4 , 3,2}, ocho juegos
n = 10, {10}, {1,9}, {2,8}, {3,7}, {4,6}, {7,2,1}, {6,3,1}, {5 , 4,1}, {5,3,2}, {4,3,2,1}: diez conjuntos
A diferencia del caso normal de contar particiones enteras, aquí estamos requiriendo que las partes en cada partición sean distintas. Esto aparece en la Enciclopedia en línea de secuencias enteras como A000009. Lamentablemente, no existe una fórmula elemental, pero sí una práctica función generadora.
El coeficiente de [matemáticas] x ^ n [/ matemáticas] en
[matemáticas] \ displaystyle \ prod_ {m \ geq 1} (1 + x ^ m) [/ matemáticas]
da el recuento deseado de particiones. ¿Cómo podemos probar esto?
Elija un valor más grande en una partición de [math] n [/ math], llámelo [math] k [/ math]. Entonces, el número de formas de particionar [math] n [/ math] como valores distintos [math] \ {k, \ ldots \} [/ math] debe ser igual al número de formas de particionar [math] nk [/ math ] usando números más pequeños que [math] k [/ math]. (Debido a que los números restantes son todos más pequeños que [math] k [/ math], son distintos de [math] k [/ math], y recursivamente distintos entre sí).
Como una recurrencia, eso dice que el recuento de particiones dado un elemento máximo [math] m [/ math] es
[matemáticas] \ displaystyle P (n, m) = \ sum_ {1 \ leq k \ leq m} P (n – k, k – 1) [/ matemáticas]
con [matemática] P (0, x) = 1 [/ matemática] y [matemática] P (-n, x) = 0 [/ matemática].
Pero una forma más útil es
[matemáticas] \ displaystyle P (n, m) = P (n, m-1) + P (nm, m-1) [/ matemáticas]
(Ejercicio: verifique que sean equivalentes).
Podemos construir una secuencia de funciones generadoras [math] G_m [/ math] a partir de esta recurrencia, indexada por el elemento más grande permitido [math] m [/ math] en nuestras particiones
[matemáticas] G_1 (x) = 1 + x [/ matemáticas]. Una forma de particionar 0, y una forma de particionar 1, no hay forma de particionar elementos más grandes.
[matemáticas] G_2 (x) = 1 + x + x ^ 2 + x ^ 3 [/ matemáticas]. Una forma de particionar 0, 1, 2 y 3.
[matemáticas] G_3 (x) = 1 + x + x ^ 2 + 2x ^ 3 + x ^ 4 + x ^ 5 + x ^ 6 [/ matemáticas]. Ahora tenemos dos formas de particionar 3, como {3} o {1,2}, y una forma de particionar 4, 5 y 6.
El coeficiente de [matemática] x ^ n [/ matemática] en [matemática] G_m (x) [/ matemática] es [matemática] P (n, m) [/ matemática]. Entonces, traduciendo la recurrencia:
[matemáticas] G_ {m} (x) = G_ {m-1} (x) + x ^ mG_ {m-1} (x) [/ matemáticas]
[matemáticas] G_ {m} (x) = G_ {m-1} (x) (1 + x ^ m) [/ matemáticas]
Por lo tanto, dejamos que [matemáticas] m [/ matemáticas] vaya al infinito que obtenemos
[matemáticas] G (x) = \ prod_ {m \ geq 1} (1 + x ^ m) [/ matemáticas]
[matemáticas] G (x) = 1 + x + x ^ 2 + 2x ^ 3 + 2x ^ 4 + 3x ^ 5 + 4x ^ 6 + 5x ^ 7 + 6x ^ 8 + 8x ^ 9 + 10x ^ {10} + 12x ^ {11} + 15x ^ {12} + 18x ^ {13} + \ ldots [/ math]