Artículos

1.1: Composiciones y particiones


Consideramos problemas relacionados con el número de formas en que un número puede escribirse como una suma. Si no se tiene en cuenta el pedido, la suma es un dividir y el número de particiones de (n ) se denota por (p (n) ). Por tanto, las composiciones de 3 son

3 = 3, 3 = 1 + 2, 3 = 2 + 1 y 3 = 1 + 1 + 1,

de modo que (c (3) = 4 ). Las particiones de 3 son

3 = 3, 3 = 2 + 1 y 3 = 1 + 1 + 1,

entonces (p (3) = 3 ).

Básicamente, existen tres métodos para obtener resultados en composiciones y particiones. Primero por argumentos puramente combinatorios, segundo por argumentos algebraicos con series generadoras y finalmente por operaciones analíticas sobre la serie generadora. Analizaremos solo los dos primeros de estos métodos.

Consideramos primeras composiciones, siendo estas más fáciles de manejar que las particiones. La función (c (n) ) se determina fácilmente de la siguiente manera. Considere (n ) escrito como una suma de unos. Tenemos (n - 1 ) espacios entre ellos y en cada uno de los espacios podemos insertar una barra, dando (2 ^ {n - 1} ) posibilidades correspondientes a las (2 ^ {n - 1} ) composición de (n ). Por ejemplo

3 = 1 1 1, 3 = 1/1 1, 3 = 1 1/1, 3 = 1/1/1.

Solo para ilustrar el método algebraico en este caso bastante trivial, consideramos

( sum _ { infty} ^ {n = 1} c (n) x ^ n ).

Se verifica fácilmente que

( begin {matriz} {rcl} { sum_ {n = 1} ^ { infty} c (n) x ^ n} & = & { sum_ {m = 1} ^ { infty} (x + x ^ 2 + x ^ 3 + cdot cdot cdot) ^ m} {} & = & { sum_ {m = 1} ^ { infty} ( dfrac {x} {1 - x}) ^ m = dfrac {x} {1 - 2x} = sum_ {n = 1} ^ { infty} x ^ {n - 1} x ^ n.} end {matriz} )

Ejemplo ( PageIndex {1} )

Como ejercicio, sugeriría usar tanto el método combinatorio como el enfoque algebraico para probar los siguientes resultados:

  1. El número de composiciones de (n ) en exactamente (m ) partes es ({n - 1 choose m -1} ) (catalán);
  2. El número de composiciones de (n ) en partes pares es (2 ^ { dfrac {n} {2} - 1} ) si (n ) es par y 0 si (n ) es impar ;
  3. El número de composiciones de (n ) en un número par de partes es igual al número de composiciones de (n ) en un número impar de partes.

Solución

Agrega texto aquí.

Algo más interesante es la determinación del número de composiciones (c ^ {*} (n) ) de (n ) en partes impares. Aquí el enfoque algebraico produce

( begin {array} {rcl} { sum_ {n = 1} c ^ {*} (n) x ^ n} & = & { sum_ {m = 1} ^ { infty} (x + x ^ 3 + x ^ 5 + cdot cdot cdot) ^ m} {} & = & { sum_ {m = 1} ^ { infty} ( dfrac {x} {1 - x ^ 2} ) ^ m = dfrac {x} {1 - x - x ^ 2} = sum F (n) x ^ n.} end {matriz} )

Al multiplicar de forma cruzada las dos últimas expresiones, vemos que

(F_ {n + 2} = F_ {n} + F_ {n + 1} ), (F_0 = 0, F_1 ​​= 1 )

Por lo tanto, las F son los llamados números de Fibonacci

1, 1, 2, 3, 5, 8, 13, ....

La función generadora produce dos expresiones explícitas para estos números. Primero, al "fraccionamiento parcial" ( dfrac {x} {1 - x - x ^ 2} ), expandiendo cada término como una serie de potencias y comparando coeficientes, obtenemos

(F_n = dfrac {1} { sqrt {5}} {( dfrac {1 + sqrt {5}} {2}) ^ n - ( dfrac {1 - sqrt {5}} {2 }) ^ n}. )

Otra expresión para (F_n ) se obtiene al observar que

( dfrac {x} {1 - x - x ^ 2} = x (1 + (x + x ^ 2) ^ 1 + (x + x ^ 2) ^ 2 + (x + x ^ 2) ^ 3 + cdot cdot cdot). )

Comparando los coeficientes aquí obtenemos (Lucas)

(F_n = {n - 1 elija 0} + {n - 2 elija 1} + {n - 3 elija 2} + cdot cdot cdot). )

Podría considerar el problema de deducir esta fórmula mediante argumentos combinatorios.

Suponga que denotamos por (a (n) ) el número de composiciones de n con todos los sumandos como máximo 2, y por b (n) el número de composiciones de (n ) con todos los sumandos al menos 2. Una interesante el resultado es que (a (n) = b (n + 2) ). Probaré este resultado y sugeriré el problema de encontrar una generalización razonable.

Primero observe que (a (n) = a (n - 1) + a (n - 2) ). Esto se deriva del hecho de que toda composición admisible termina en 1 o 2. Al eliminar este último sumando, obtenemos una composición admisible de (n - 1 ) y (n - 2 ) respectivamente. Dado que (a (1) = 1 ) y (a (2) = 2 ), se sigue que (a (n) = F_n ). La función (b (n) ) satisface la misma fórmula de recursividad. De hecho, si el último sumando en una composición admisible de (n ) es 2, elimínelo para obtener una composición admisible de (n - 2 ); si el último sumando es mayor que 2, redúzcalo en 1 para obtener una composición admisible de (n - 1 ). Dado que (b (2) = b (3) = 1 ), se deduce que (b (n) = F_ {n − 2} ) de modo que (a (n) = F_n = b (n + 2) ).

Una idea interesante para las composiciones es la del peso de una composición. Supongamos que asociamos con cada composición un número llamado peso, que es el producto de los sumandos. Determinaremos la suma (w (n) ) de los pesos de las composiciones de (n ). La función generadora de (w (n) ) es

( sum_ {n = 1} ^ { infty} w (n) x ^ n = sum_ {m = 1} ^ { infty} (x + 2x ^ 2 + 3x ^ 3 + cdot cdot cdot) ^ m = dfrac {x} {1 - 3x + x ^ 2}. )

De esto encontramos que (w (n) = 3w (n - 1) - w (n - 2) ). Lo dejo como ejercicio para demostrar a partir de esto que (w (n) = F_ {2n − 1} ).

Pasamos ahora a las particiones. No existe una fórmula explícita simple para (p (n) ). Nuestro principal objetivo aquí será probar la fórmula de recursividad

(p (norte) = p (norte - 1) + p (norte - 2) - p (norte - 5) - p (norte - 7) + p (norte - 12) + p (norte - 15) + cdot cdot cdot )

descubierto por Euler. El enfoque algebraico de la teoría de la partición depende de manipulaciones algebraicas con la función generadora

( sum_ {n = 0} ^ { infty} p (n) x ^ n = dfrac {1} {(1 - x) (1 - x ^ 2) (1 - x ^ 3) cdot cdot cdot} )

y funciones relacionadas para particiones restringidas. El enfoque combinatorio depende del uso de diagramas de partición (Ferrer). Por ejemplo, el diagrama de Ferrer de la partición 7 = 4 + 2 + 1 es

Aquí es útil la noción de partición conjugada. Esto se obtiene al reflejar el diagrama en una línea (45 ^ { circ} ) que desciende desde la esquina superior izquierda. Por ejemplo,

las particiones

y

se conjugan entre sí. Esta correspondencia produce casi inmediatamente los siguientes teoremas:

El número de particiones de (n ) en (m ) partes es igual al número de particiones de (n ) en partes, la mayor de las cuales es (m );
El número de particiones de (n ) en no más de (m ) partes es igual al número de particiones de (n ) en partes que no exceden (m ).

De una naturaleza algo diferente es la siguiente: El número de particiones de (n ) en partes impares es igual al número de particiones de (n ) en partes distintas. Para esto damos una prueba algebraica. Usando funciones generadoras bastante obvias para las particiones requeridas, el resultado se reduce a mostrar que

( dfrac {1} {(1 - x) (1 - x ^ 3) (1 - x ^ 5) (1 - x ^ 7) cdot cdot cdot} = (1 + x) (1 + x ^ 2) (1 + x ^ 3) (1 + x ^ 4) cdot cdot cdot. )

La multiplicación cruzada hace que el resultado sea intuitivo.
Ahora procedemos a un teorema más importante debido a Euler:

((1 - x) (1 - x ^ 2) (1 - x ^ 3) cdot cdot cdot = 1 - x ^ 1 - x ^ 2 + x ^ 5 + x ^ 7 - x ^ {12 } - x ^ {15} + cdot cdot cdot, )

donde los exponentes son los números de la forma ( dfrac {1} {2} k (3k pm 1) ). Primero notamos que

((1 - x) (1 - x ^ 2) (1 - x ^ 3) cdot cdot cdot = sum ((E (n) - O (n)) x ^ n, )

donde (E (n) ) es el número de particiones de (n ) en un número par de partes distintas y (O (n) ) el número de particiones de (n ) en un número impar de partes distintas.

Intentamos establecer una correspondencia uno a uno entre las particiones de los dos tipos considerados. Naturalmente, tal correspondencia no puede ser exacta, ya que una correspondencia exacta probaría que (E (n) = O (n) ).

Tomamos una gráfica que representa una partición de (n ) en cualquier número de partes desiguales. Llamamos a la línea más baja (AB ) la base del gráfico. Desde (C ), el nodo extremo noreste, trazamos la línea suroeste más larga posible en el gráfico; esto puede contener solo un nodo. Esta recta (CDE ) se llama ala del gráfico

Por lo general, podemos mover la base a la posición de una nueva ala (paralela y a la derecha de la “vieja” ala). En ocasiones podemos realizar la operación inversa (mover el ala para que quede sobre la base, debajo de la base anterior). Cuando la operación descrita o su inversa es posible, se lleva de una partición con un número impar de partes a un número par de partes o viceversa. Por tanto, en general (E (n) = O (n) ). Sin embargo, dos casos requieren una atención especial. Están tipificados por los diagramas

y

En estos casos (n ) tiene la forma

(k + (k + 1) + cdot cdot cdot + (2k - 1) = dfrac {1} {2} (3k ^ 2 - k) )

y

((k + 1) + (k + 2) + cdot cdot cdot + (2k) = (3k ^ 2 + k) ).

En ambos casos hay un exceso de una partición en un número par de partes, o una en un número impar, según que (k ) sea par o impar. Por tanto, (E (n) - O (n) = 0 ), a menos que (n = dfrac {1} {2} (3k pm k) ), cuando (E (n) - O (n ) = (-1) ^ k ). Esto da el teorema de Euler.

Ahora, de

( sum p (n) x ^ n (1 - x - x ^ 2 + x ^ 5 + x ^ 7 - x ^ {12} - cdot cdot cdot) = 1 )

obtenemos una relación de recurrencia para (p (n) ), a saber

(p (n) = p (n - 1) + p (n - 2) - p (n - 5) - p (n - 7) + p (n - 12) + cdot cdot cdot. )


Ver el vídeo: Rogers-Ramanujan Identities. Part 1: Introduction to Integer Partitions (Septiembre 2021).