• Author / Uploaded
• Andreu Correa Casablanca

Citation preview

Particiones. Representaci´on geom´etrica de particiones. La funci´on generadora de p(n). Otras funciones generadoras. Dos teoremas de Euler. Beihui Ye, Andreu Correa Casablanca 17 de Diciembre, 2010

´Indice 1. Particiones

1

2. Representaci´ on geom´ etrica de particiones

4

3. La funci´ on generadora de p(n)

7

4. Otras funciones generadoras

9

5. Dos teoremas de Euler

11

1

1. Particiones

1.

Particiones

En este tema introduciremos el concepto de partici´on de un n´ umero natural n dado, as´ı como las funciones que nos dan el n´ umero de particiones de n con y sin restricciones. Hablaremos tambi´en de algunos resultados te´oricos que relacionar´an las citadas funciones entre ellas. Empecemos entonces por algunas definiciones: Definici´ on 1. Una partici´ on de un n´ umero natural n es una tupla a ∈ Nr para alg´ un r ∈ N tal que si a = (a1 , a2 , . . . , ar ) entonces se cumple que a1 ≥ a2 ≥ · · · ≥ ar y adem´as a1 + a2 + · · · + ar = n. La condici´on de orden se establece para simplificar la definici´on y no tener que establecer relaciones de equivalencia entre tuplas que tengan los mismos elementos pero con distinto orden. Intuitivamente, una partici´on viene a ser una forma de descomponer n como suma de n´ umeros naturales m´as peque˜ nos que n. Definici´ on 2. Dado n ∈ N, sea X(n) el conjunto de todas las particiones de n (del que f´acilmente podemos ver que es necesariamente finito), entonces podemos definir la funci´ on partici´ on como p : N −→ N n 7−→ ]X(n) Por conveniencia, podremos extender la funci´on partici´on para todos los enteros, estableciendo p(0) = 1 y p(n) = 0 ∀n < 0. Ejemplo 3. Presentamos una tabla de los valores de p para los primeros 5 naturales: n 1 2 3 4 5

p(n) X(n) 1 {(1)} 2 {(1, 1), (2)} 3 {(1, 1, 1), (2, 1), (3)} 5 {(1, 1, 1, 1), (2, 1, 1), (2, 2), (3, 1), (4)} 7 {(1, 1, 1, 1, 1), (2, 1, 1, 1), (2, 2, 1), (3, 1, 1), (3, 2), (4, 1), (5)}

Es pr´acticamente obvio que la funci´on p es creciente, pero es m´as interesante a´ un notar que su crecimiento es realmente r´apido. Podemos comprobarlo en Wolfram Mathematica 1 con la funci´on PartitionP, que se encuentra en el paquete Combinatorica, o en la aplicaci´on online wolframalpha.com con la misma funci´on. Con el software SAGE 2 podemos encontrar el conjunto de particiones de un n´ umero n dado, as´ı como su cardinal mediante las expresiones Partitions(n).list() y Partitions(n).cardinality() respectivamente. Como ejemplos del crecimiento de p, tenemos que p(100) = 190569292, p(200) = 3972999029388 y p(1000) = 24061467864032622473692149727991.

1

Software cient´ıfico orientado a manipulaci´on de datos matem´aticos creado por Stephen Wolfram, se trata de un producto que comercializa su empresa Wolfram 2 SAGE es un sistema algebraico computacional escrito en lenguaje Python. Fue creado en el a˜ no 2005 con la intenci´ on de crear un subconjunto de la funcionalidad del software Magma en la Universidad de Washington, hoy en d´ıa aglutina una gran cantidad de funcionalidades y puede integrarse con muchas otras aplicaciones cient´ıficas. Se trata de software libre y puede ser encontrado en http://www.sagemath.org.

2

1. Particiones

Lema 4. La funci´on partici´on p es creciente. Demostraci´on. Sea p(n) = ]X(n), entonces podemos construir un conjunto de Y con elementos (a1 , . . . , as , 1), donde (a1 , . . . , as ) ∈ X(n). Claramente Y ⊂ X(n + 1) ya que a1 + . . . + as + 1 = n + 1, adem´as, podemos afirmar que ]Y = ]X(n). Como (n + 1) ∈ /Y y tambi´en (n + 1) ∈ X(n + 1), deducimos que ]X(n + 1) > ]X(n). Ahora que ya conocemos la funci´on partici´on y hemos visto algo sobre su crecimiento pasaremos a definir otras funciones partici´on, pero esta vez con ciertas restricciones. Definici´ on 5. pm (n) po (n) pd (n) q e (n) q o (n)

= = = = =

el el el el el

n´ umero n´ umero n´ umero n´ umero n´ umero

de de de de de

particiones particiones particiones particiones particiones

de de de de de

n n n n n

en en en en en

sumandos menores que o bien iguales a m. sumandos impares. sumandos distintos. un n´ umero par de sumandos distintos. un n´ umero impar de sumandos distintos.

Tomaremos la convenci´on pm (0) = po (0) = pd (0) = q e (0) = 1, q o (0) = 0 otra vez para facilitar c´alculos posteriores. Teorema 6. Podemos afirmar lo siguiente: a) pm (n) = p(n) si n ≤ m, b) pm (n) ≤ p(n) para todo n ≥ 0, c) pm (n) = pm−1 (n) + pm (n − m) si n ≥ m > 1, d) pd (n) = q e (n) + q o (n). Demostraci´on. Tanto (a), como (b) como (d) son inmediatas a partir de las definiciones, fij´emonos en el caso (c). Observemos que cada una de las particiones de n contada por pm (n) puede tener el sumando m o bien no tenerlo, las segundas son contadas por pm−1 (n), mientras que las primeras se pueden obtener a˜ nadiendo el entero m por la izquierda a las tuplas que cuenta pm (n − m) sin dejarnos ninguna. As´ı pues, la suma de ambas cantidades es precisamente pm−1 (n) + pm (n − m), como quer´ıamos probar. El siguiente teorema nos servir´a para establecer una equivalencia entre dos de las funciones que hemos definido anteriormente, lo que a su vez servir´a para facilitar c´alculos posteriores. Teorema 7. Si n ≥ 1 entonces pd (n) = po (n). Demostraci´on. La prueba consistir´a en demostrar dos desigualdades no estrictas que d´andose a la vez solo dejan como posibilidad que se cumpla pd (n) = po (n).

3

1. Particiones (po (n) ≤ pd (n)): Consideremos cualquier partici´on contada por po (n), que estar´a formada por sumandos impares. Esta partici´on estar´a formada por r1 sumandos a1 , r2 sumandos a2 , . . ., y rs sumandos as donde los ai son enteros impares distintos y n=

s X

r i ai

i=1

Podemos escribir ahora cada uno de los ri como suma de potencias de 2, de la forma P (i) (i) ri = j bj 2j , donde bj = 0 ´o 1. Ahora esto nos permite expresar n como n=

s X X i=1

(i)

bj 2j ai

j

Esta f´ormula nos proporciona una partici´on con sumandos 2j ai para cada parti(i) ci´on con sumandos impares (escogiendo los sumandos de la f´ormula con bj = 1). Adem´as, como todas las ai son diferentes tenemos que los sumandos de esta nueva partici´on son todos diferentes entre s´ı. Para acabar esta parte hace falta a˜ nadir un peque˜ no inciso. Tenemos que comprobar que la correspondencia que hemos establecido es inyectiva. Supongamos que dos particiones a y b con sumandos impares son distintas, es decir, que alguno de sus sumandos ai (que puede aparecer 0 o m´as veces) aparece m´as veces en una que en la otra. Escogemos el mayor de los sumandos en que difieran las dos particiones (en cuanto a n´ umero de apariciones). Sea ai ese sumando y ra y rb los respectivos n´ umeros de apariciones de ´este en a y en b. Es claro entonces que sus expresiones como sumas de potencias de 2, que son diferentes, dar´an lugar a particiones diferentes. (pd (n) ≤ po (n)): Consideremos cualquier partici´on contada por pd (n),P que estar´a formada por sumandos todos ellos diferentes entre s´ı. Tenemos que n = tk=1 ck . Podemos escribir los ck como ck = 2ek dk , con dk impar. Escojamos de entre los d1 , . . . , dt s´olo aquellos que sean diferentes, y llam´emosles a1 , . . . , as . (i)

(i)

Podemos escribir bj = 1 si 2j ai es igual a alg´ un ck , y en caso contrario bj = 0. As´ı pues tenemos que t s X X X (i) n= ck = bj 2j ai k=1

i=1

j

P Con lo que podemos regresar a la expresi´on de la forma si=1 ri ai con ai impares y ya estamos. La inyectividad de la correspondencia es m´as clara en este paso que en el anterior. As´ı pues, queda demostrado el teorema.

4

2.

2. Representaci´on geom´etrica de particiones

Representaci´ on geom´ etrica de particiones

En este cap´ıtulo trataremos la representaci´on gr´afica de particiones, que nos ayudar´a, entre otras cosas, a intuir algunos resultados te´oricos acerca de ´estas. Definici´ on 8. Un diagrama de Ferrers de una partici´on (a1 , . . . , ak ) es un conjunto de puntos sobre un plano dispuestos equiespaciadamente en filas consecutivas tambi´en equiespaciadas, de forma que haya k filas, y en la fila i-´essima haya ai puntos. Dichas filas generalmente estar´an alineadas por la izquierda. Ejemplo 9. Veamos algunos diagramas de Ferrers para algunas particiones. Sea n = 8 y (3, 2, 2, 1) una de sus particiones, entonces su diagrama de Ferrers es: • • • • • • • • fij´emonos en que este diagrama a veces nos permite encontrar otra partici´on de forma autom´atica, mirando las columnas en vez de en las filas. • • • • • • • • Este ejemplo en particular nos permitir´a introducir una nueva definici´on. Definici´ on 10. Decimos que una partici´on a es conjugada de otra partici´on b cuando el diagrama de Ferrers de b se corresponde con el diagrama traspuesto de a (entendiendo la transposici´on como en el caso de las matrices). Teorema 11. El n´ umero de particiones de n con m sumandos es el mismo que el n´ umero de particiones de n con el sumando m´aximo igual a m. Demostraci´on. A partir de los diagramas de Ferrers podemos ver que unas son conjugadas de las otras, y que por tanto existe una correspondencia biyectiva entre ellas y su n´ umero es el mismo. Definici´ on 12. Decimos que una partici´on es autoconjugada cuando es su propia conjugada. Ejemplo 13. Veamos un ejemplo de partici´on autoconjugada. Escogeremos n = 10 y la partici´on (4, 3, 2, 1). • • • • • • • • • • Veamos ahora un teorema menos intuitivo sobre el n´ umero de particiones con sumandos distintos, que demostraremos en parte gracias a la ayuda de los diagramas de Ferrers.

5

2. Representaci´on geom´etrica de particiones

Teorema 14. Sea n ≥ 0, entonces  2 (−1)j si n = 3j 2±j para alg´ un j ∈ {0} ∪ N e o q (n) − q (n) = 0 en cualquier otro caso Demostraci´on. Consideremos en primer lugar el caso n = 0. Cogiendo j = 0 estamos en el primer caso, y q e (0) − q o (0) = 1. Supongamos ahora n ≥ 1 y consideremos la partici´on n = a1 + · · · + ar en sumandos distintos. En la gr´afica de la partici´on daremos nombre a algunos puntos; al punto situado m´as a la derecha de la fila superior le daremos el nombre A1 , y iremos nombrando a los puntos situados m´as a la derecha de las filas anteriores mientras su n´ umero de puntos sea igual al n´ umero de puntos de la fila anterior menos uno. As´ı tendremos un conjunto de puntos A1 , . . . , As con cardinal menor o igual al n´ umero de filas de la gr´afica. Tambi´en daremos nombre a los puntos de la u ´ltima fila, empezando por el de m´as a la izquierda y avanzando hacia la derecha, los llamaremos B1 , . . . , Bt . • • • • • • • • • • B1 B2

• • • • • A1 • • • • A2 • • • A3 •

Ahora podr´ıamos contemplar la posibilidad de construir una nueva partici´on en sumandos distintos mediante transformaciones en el diagrama de Ferrers. En particular una posible forma consiste en tomar los puntos B1 , . . . , Bt y colocarlos a la derecha de los puntos A1 , . . . , At , B1 a la derecha de A1 , B2 a la derecha de A2 y as´ı sucesivamente. Es claro que esto no puede hacerse si t > s, ni tampoco si t = s y adem´as As = Bt , podr´a hacerse si t < s o bien t = s y As 6= Bt . Otra forma de conseguir una partici´on en sumandos distintos puede ser tomar los puntos A1 , . . . , As y ponerlos debajo de los puntos B1 , . . . , Bs , lo que podremos hacer si y solo si s < t − 1 o bi´en s = t − 1 y Bt 6= As . Observando las condiciones podemos ver f´acilmente que dada una partici´on en sumandos distintos, los dos cambios son incompatibles y solo podremos hacer uno de ellos, o bi´en ninguno en el caso (As = Bt ) ∧ ((s = t) ∨ (s = t − 1)). Adem´as, en caso de poder hacer uno de los cambios a una partici´on P dada, a la partici´on P 0 obtenida se le puede aplicar el cambio contrario, y una de ellas tendr´a un sumando m´as que la otra, por lo que la paridad tambi´en diferir´a. Esto significa que solo deberemos fijarnos en las particiones en sumandos distintos a las que no se les pueda aplicar este cambio. En las particiones en sumandos distintos a las que no se les puede aplicar el cambio se cumple que As = Bt , por lo que es claro que tienen s sumandos. La fila inferior tiene t puntos, as´ı que ar = t, como As = Bt se deduce que ai = t + r − i, y por tanto n=

r X i=1

ai = st +

(s − 1)s 2

6

2. Representaci´on geom´etrica de particiones

  • • • • • • s • • • • • ◦  • • • • ◦ ◦ | {z } |{z} t

s−1

2

2

En caso de ser s = t entonces n = 3s 2−s , y si s = t − 1 entonces se cumple n = 3s 2+s . Podemos ver muy f´acilmente que para cada s ∈ N y para cada f´ormula se obtienen n´ umeros diferentes, por lo que n solo podr´a ser igualada a una de las dos f´ormulas evaluadas en una sola s, lo que se puede interpretar como que para cada n ∈ N s´olo hay como mucho una partici´on a la que no se le pueda aplicar la transformaci´on descrita anteriormente (que no tiene otra partici´on con paridad diferente asociada). Como s da la paridad del n´ umero de sumandos de la partici´on, el teorema queda demostrado. Para aquellos que quieran ver en m´as detalle por qu´e no hay naturales diferentes tales que den el mismo n´ umero con esas f´ormulas aqu´ı hay una peque˜ na demostraci´on. Empecemos por comparar las mismas f´ormulas entre s´ı. Supongamos que existen s1 , s2 ∈ N 3s2 −s 3s2 −s tales que se cumple 12 1 = 22 2 . Por ser s2 6= s1 podemos escribir s2 = s1 + d. En lo que sigue escribiremos s y no s1 . 2

= 3(s+d) 2−(s+d) ⇒ 3(s2 − (s + d)2 ) + ((s + d) − s) = 0 √ 36s2 +12 ⇒ −3d − 6sd + d = 0 ⇒ d = 6s± −6 3s2 −s 2 2

Pero el siguiente cuadrado de 36 es 49 y los que le siguen tienen una diferencia entre ellos mayor a 12, por lo que la u ´nica soluci´on entera para d es 0. No Para los dem´as casos proceder´ıamos de forma similar.

7

3. La funci´on generadora de p(n)

3.

La funci´ on generadora de p(n)

En este tema trataremos el c´alculo de p(n) mediante f´ormulas anal´ıticas, lo que nos evitar´a realizar el conteo de particiones cada vez qie queramos saber su valor. Empecemos estudiando el concepto funci´on generadora. Definici´ on 15. Una funci´ on generadora (o funci´on generatriz) g de una funci´on f es una funci´on cuya expresi´on g(x) es una serie de pot´encias tal que sus coeficientes se calculan evaluando f en la posici´on donde se encuentran: g(x) =

∞ X

f (n)xn

n=0

Las funciones generadoras tambi´en pueden ser definidas en base a una sucesi´on, cambiando los t´erminos f (n) por an , siendo (an ) una sucesi´on. La funci´on generadora de p(n) fue encontrada por Euler, y es ∞ Y

n −1

(1 − x )

=

∞ X

p(n)xn

n=0

n=1

Daremos una idea intuitiva de como llegar a este resultado, aunque una prueba p´ uramente formal requiere la introducci´on de muchos conceptos que nos alejar´ıan demasiado de la tem´atica de este texto. P∞ kn P∞ kn 1 = Demostraci´on. Podemos expresar (1 − xn )−1 = 1−x n como k=0 x k=0 x , ya que l´ımN →∞ ∞ Y

(xn )N −1 xn −1

=

−1 xn −1

(para |x| ≤ 1). As´ı pues, podremos escribir

(1 − xn )−1 = (1 + x + x2 + x3 + · · · )(1 + x2 + x4 + x6 + · · · )(1 + x3 + x6 + x9 + · · · ) . . .

n=1

Ahora, antes de continuar, introduciremos brevemente el producto de s´eries de Cauchy, aunque no justificaremos nada sobre la convergencia del producto ni porqu´e el producto de Cauchy de s´eries se corresponde con el producto de las funciones generadoras asociadas a las series, as´ı como tampoco otras propiedades b´asicas tales como su conmutatividad o asociatividad. Definici´ on 16. El producto de Cauchy de dos s´eries formales3 ∞ X

an ,

∞ X

n=0

bn

n=0

se define como ∞ X n=0 3

! an

·

∞ X n=0

! bn

=

∞ X n=0

cn donde cn =

n X

ak bn−k

k=0

La definici´ on de s´erie formal es, v´ agamente hablando, una generalizaci´on del concepto de s´erie ideada para aprovechar la teor´ıa (y notaci´ on) anal´ıtica de s´eries en otros campos. En el caso de s´eries formales, asuntos como la convergencia pasan a no tener importancia (la tendr´an solo los coeficientes), de forma que se puede pensar en ellas como en sucesiones cuyos elementos son los coeficientes de la s´erie.

8

3. La funci´on generadora de p(n)

Afirmaremos sin demostrar que el producto de s´eries de Cauchy de dos s´eries de pot´encias a y b da como resultado una s´erie de potencias con funci´on generadora asociada igual al producto de las funciones generadoras asociadas a a y b. As´ı pues, podemos escribir: m Y

n −1

(1 − x )

=

n=1

∞ X ∞ X

···

j1 =0 j2 =0

∞ X

x

j1 ·1+j2 ·2+···+jm ·m

jm =0

=

∞ X

cj x j

j=0

donde cj es el n´ umero de soluciones de la ecuaci´on m variables 1·j1 +2·j2 +· · ·+m·jm = n en los enteros no negativos. Lo que tambi´en se puede entender como cj = pm (j). Por lo que podemos afirmar m ∞ Y X (1 − xn )−1 = pm (n)xn n=1

n=0

Es claro que siempre se cumple pm (n) ≤ p(n), y que pm (n) → p(m) cuando m → ∞, si escribimos la expresi´on anterior (la funci´on generadora de pm ) como Fm (x) =

∞ X

n

pm (x)x = 1 +

m X

n

p(x)x +

pm (x)xn

n=m+1

n=1

n=0

∞ X

y a la funci´on generadora de p la llamamos F , podemos establecer la siguiente desigualdad: 1+

m X

p(x)xn < Fm (x) < F (x)

n=1

es f´acil ver que el lado izquierdo de la igualdad se puede hacer tender a F (x) haciendo tender m a infinito, dado que Fm (x) est´a en medio tiene que tender tambi´en a F (x), o lo que es lo mismo: l´ım

m→∞

como quer´ıamos.

m Y

n −1

(1 − x )

n=1

=

∞ Y

n −1

(1 − x )

n=1

=

∞ X n=1

p(x)xn

9

4.

4. Otras funciones generadoras

Otras funciones generadoras

De igual forma que en el cap´ıtulo anterior, en ´este trataremos las funciones generadoras relacionadas con el n´ umero de particiones bajo ciertas restricciones. Enumeraremos algunas de ellas sin escribir el proceso de c´alculo que nos lleva a poder establecerlas. La funci´on generadora de p(n), escrita en forma de fracci´on, la volvemos a escribir para hacer notar las similitudes entre ´esta y las que siguen. ∞ Y

F (x) =

(1 − xn )−1

n=1

La funci´on generadora del n´ umero de particiones de n en sumandos impares. F (x) =

∞ Y

1 − x2n−1


−1

n=1

La funci´on generadora del n´ umero de particiones de n en sumandos pares. ∞ Y

F (x) =

1 − x2n


−1

n=1

La funci´on generadora del n´ umero de particiones de n en sumandos diferentes. F (x) =

∞ Y

(1 + xn )

n=1

La funci´on generadora del n´ umero de particiones de n en sumandos diferentes e impares. ∞ Y
F (x) = 1 + x2n−1 n=1

La funci´on generadora del n´ umero de particiones de n en sumandos de la forma 5m + 1 o 5m + 4 con m ∈ N ∪ {0}. F (x) =

∞ Y n=0

1−x


5n+1 −1

∞ Y

1 − x5n+4


−1

n=0

Estas f´ormulas pueden ser recordadas f´acilmente si nos fijamos en el patr´on que siguen. Los factores est´an elevados a −1 si no se exige que los sumandos de las particiones sean diferentes entre s´ı, mientras que de exigirse eso, no se elevan los factores. Adem´as, el signo que acompa˜ na a la x que aparece dentro de los factores tambi´en cambia en ese caso, siendo positivo para particiones con sumandos diferentes, y negativo para el caso contrario. Otra ayuda que podemos encontrar es el exponente de las x que aparecen en los factores, que

10

4. Otras funciones generadoras

siguen las mismas restricciones que los factores, exponentes pares si los sumandos son pares, exponentes impares si los sumandos son impares, etc. Introduciremos una u ´ltima funci´on generadora que nos servir´a para demostrar un teorema en el cap´ıtulo posterior. F (x) = x

N

m Y

1 − x2n


−1

(17)

n=1

´ Esta es la funci´on generadora de la funci´on que cuenta el n´ umero de particiones de n−N con sumandos pares menores o iguales que 2m, o bi´en (por el teorema 11) el n´ umero 1 de particiones de 2 (n − N ) en como mucho m sumandos. Veamos en m´as detalle por qu´e el teorema 11 nos da otra forma de entender la funci´on generadora. El teorema 11 nos permite establecer una correspondencia biyectiva entre las particiones con como mucho m sumandos y las particiones con sumandos no mayores que m. As´ı pues, en virtud de dicho teorema podemos establecer una relaci´on biyectiva entre particiones de n − N en sumandos pares no mayores que 2m y particiones de n − N en un n´ umero par de sumandos no mayor que 2m. Como en las particiones los sumandos estan ordenados, y en este caso particular los podemos agrupar en pares de sumandos iguales, si quitamos uno por pareja tenemos una partici´on de 21 (n − N ) con no m´as de m sumandos, como quer´ıamos ver.

11

5.

5. Dos teoremas de Euler

Dos teoremas de Euler

En ´este u ´ltimo cap´ıtulo trataremos dos identidades dadas por Euler que nos daran una idea sobre los m´etodos necesarios para demostrar que las expresiones dadas para las funciones generadoras mencionadas anteriormente son efectivamente correctas. Antes de llegar a las identidades que buscamos pasaremos por algunos resultados previos. Teorema 18. (1 + x)(1 + x3 )(1 + x5 ) · · · = 1 +

x x9 x4 + +. . . + 1 − x2 (1 − x2 )(1 − x4 ) (1 − x2 )(1 − x4 )(1 − x6 )

Teorema 19. (1+x2 )(1+x4 )(1+x6 ) · · · = 1+

x12 x6 x2 + +. . . + 1 − x2 (1 − x2 )(1 − x4 ) (1 − x2 )(1 − x4 )(1 − x6 )

Aqu´ı los exponentes son de la forma 1 · 2, 2 · 3, 3 · 4, 4 · 5, . . . Demostraci´on. Demostraremos ´estas identidades a˜ nadiendo un segundo par´ametro a, lo haremos de dos formas distintas: (i) Escribimos K(a) = K(a, x) = (1 + ax)(1 + ax3 )(1 + ax5 ) · · · = 1 + c1 a + c2 a2 + · · · donde cn = cn (x) es independiante de a. M´as brevemente: K(a) = (1 + ax)K(ax2 ) o bi´en 1 + c1 a + c2 a2 + · · · = (1 + ax)(1 + c1 ax2 + c2 a2 x4 + · · · ). Ahora, si igualamos coeficientes obtendremos las siguientes expresiones para ci : c1 c2 cm

= x + c1 x 2 = c1 x 3 + c2 x 4 ... = cm−1 x2m−1 + cm x2m ...

con lo que podemos definirlos de forma que dependan de los anteriores: cm =

x2m−1 c 1−x2m m−1

= =

x1+3+...+(2m−1) (1−x2 )(1−x4 )···(1−x2m ) 2 xm 2 4 (1−x )(1−x )···(1−x2m )

De lo que se sigue que (1 + ax)(1 + ax3 )(1 + ax5 ) · · · = 1 +

ax a2 x 4 + + ··· 1 − x2 (1 − x2 )(1 − x4 )

y los teoremas 18 y 19 son casos particulares de esto, con a = 1 y a = x.

12

5. Dos teoremas de Euler

(ii) La segunda forma es algo m´as visual y no necesita usar teor´ıa de s´eries infinitas. Este tipo de pruebas suelen ser descritas como “combinatorias”. Ve´amos el caso del teorema 18 Sabemos que la parte de la izquierda de la igualdad enumera las particiones en partes impares y diferentes (se trata de una funci´on generadora), por ejemplo, 15 tiene 4 de esas particiones: 15 = 11 + 3 + 1 = 9 + 5 + 1 = 7 + 5 + 3 podemos representar estas particiones uniendo los puntos de diagramas de Ferrers asociados a particiones autoconjugadas tal como vemos en los diagramas A, B, C y D. • • • • • • • • • • • • • • • A

• • • • • • • • • • • • • • • A0

• • • • • • • • • • • • • • • A00

• • • • • • • • • • • • • • • B

• • • • • • • • • • • • • • • B0

• • • • • • • • • • • • • • • B 00

• • • • •

• • • • • • • • • • C

• • • •

• • • • • • • • • • • D

• • • • •

• • • • • • • • • • C0

• • • •

• • • • • • • • • • 0• D

• • • • •

• • • • • • • • • • C 00

• • • •

• • • • • • • • • • 00• D

13

5. Dos teoremas de Euler

Con la ayuda de estos diagramas podemos ver que hay una correspondencia directa entre las particiones en sumandos impares distintos y las particiones autoconjugadas. La parte izquierda de la igualdad es exactamente la funci´on generadora del n´ umero de particiones de n en sumandos distintos e impares, as´ı pues nos quedar´a ver que la parte derecha de la igualdad se corresponde con la funci´on generadora del n´ umero de particiones autoconjugadas de n. Podemos leer los diagramas de una forma ligeramente distinta, fij´emonos en que est´an formados por un cuadrado de m2 puntos (color azul) con dos colas que a su vez podr´ıan representar particiones de 12 (n − m2 ), lo que nos pone en situaci´on de poder usar la u ´ltima funci´on generadora explicada en el cap´ıtulo anterior (17). Sustituimos N por m2 y m juega el mismo papel que en (17), quedando: x

m2

m Y

2

1−x


2n −1

n=1

xm = (1 − x2 )(1 − x4 ) · · · (1 − x2m )

Esta f´ormula es la funci´on generadora del n´ umero de particiones de 21 (n − m2 ) en como mucho m sumandos, cada una de las cuales se corresponde con una partici´on autoconjugada de n. Ahora, si consideramos la suma con respecto m (para considerar todos los cuadrados que vemos en las particiones autoconjugadas, no confundir con hacer variar la cantidad m´axima de sumandos) tendremos lo que quer´ıamos: ∞ X

2

xm 1+ (1 − x2 )(1 − x4 ) · · · (1 − x2m ) m=1

Corolario 20. El n´ umero de particiones de n en sumandos impares y distintos es igual al n´ umero de particiones autoconjugadas de n.

14

5. Dos teoremas de Euler

Referencias [1] Ferrers diagram. http://mathworld.wolfram.com/FerrersDiagram.html. [2] Partition. http://en.wikipedia.org/wiki/Partition (number theory). [3] G.H. Hardy and Wright E.M. An introduction to the theory of numbers. Sixth edition. Revised by D.R. Heath-Brown and J.H. Silverman. Oxford University Press, Oxford, 2008. [4] I. Niven and H.S. Zuckerman. Introducci´on a la teor´ıa de los n´ umeros. Limusa, 1976.