Fracciones continuas y combinatoria

El grueso de este artículo es una colaboración enviada por fede a gaussianos (arroba) gmail (punto) com.

Introducción

Una fracción continua es una expresión del tipo:

x=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cfrac{1}{\ddots}}}}

donde a_0 es un número entero y los demás a_i son enteros positivos.

La representación de un número real de este tipo en fracción continua tiene varias propiedades que hacen que dicha representación sea más interesante que la representación decimal habitual:

  • La representación en fracción continua de un número es finita si y solo si ese número es racional.
  • La representación en fracción continua de un racional simple es generalmente corta.
  • La representación en fracción continua de un racional es única siempre que no acabe en 1.
  • Los términos de una fracción continua se repetirán si y solo si representa a un irracional cuadrático, es decir, si es solución de una ecuación cuadrática con coeficientes enteros. Por ejemplo, la fracción continua [1, 1, 1, \ldots ] representa al número áureo y [1, 2, 2, 2, \ldots ] a \sqrt{2}.
  • El truncado de la representación en fracción continua de un número x da una aproximación racional que es, en cierto sentido, la mejor posible.

Todo número real puede representarse como fracción continua, pero en este artículo vamos a centrarnos en la representación continua de ciertos números racionales.

Fracción continua de un número racional


Si a_0, a_1, \ldots, a_n son los cocientes parciales que obtenemos aplicando el algoritmo de Euclides a una fracción irreducible \textstyle{\frac{p}{q}}, con p > q, todos los a_i serán enteros positivos.

Escribimos:

\cfrac{p}{q}= \cfrac{N[a_0, a_1, \ldots, a_n]}{D[a_0, a_1, \ldots, a_n]}=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{\ddots+\cfrac{1}{a_n}}}} = [a_0, a_1, \ldots, a_n]

de forma que N[a_0,\ldots a_n] = p es el numerador de la fracción irreducible cuyo desarrollo en fracción continua tiene los cocientes parciales a_0,\ldots a_n y D[a_0,\ldots a_n] = q es el denominador de esa fracción.

En la teoría elemental de las fracciones continuas se demuestra fácilmente (por inducción) que

  • N[a_0]=a_0 y N[a_0,a_1]=a_0a_1+1
  • N[a_0,\ldots a_n] = a_nN[a_0,\ldots a_{n-1}]+N[a_0,\ldots a_{n-2}]
  • D[a_0]= 1 y D[a_0,a_1,\ldots a_n]=N[a_1,\ldots a_n]

Aunque en el resto del artículo no se va a utilizar esto es interesante resaltar que N[a_0,\ldots,a_n] también se puede expresar como un determinante:

N[a_0,\ldots,a_n]=\begin{vmatrix} a_0 & -1  & 0 & 0  & \ldots & 0 & 0 \\  1  & a_1 & -1   & 0  & \ldots & 0 & 0 \\ 0  & 1 & a_2 & -1 & \ldots & 0 & 0 \\ & & \ldots & & \ldots \\   & & \ldots & & \ldots \\ 0  & 0 & 0 & 0 & \ldots & a_{n-1} & -1 \\ 0  & 0 & 0 & 0 & \ldots &  1 & a_n \end{vmatrix}

Interpretación combinatoria

En este artículo (pdf, 488kb) Benjamin, Quinn y Su dan la siguiente interpretación combinatoria de las cantidades N[a_0,\ldots a_n], que hace visualmente inmediatas algunas relaciones entre ellas.

Supongamos una regla de longitud n+1, dividida en n+1 casillas C_i \ (i=0,\ldots,n) de longitud 1.
Asignamos a cada casilla C_i un peso máximo a_i (que será siempre un entero positivo).

Formamos configuraciones con dos tipos de piezas, unas simples, de longitud 1, y otras dobles, de longitud 2, colocándolas sobre la regla de longitud n+1 de la siguiente forma:

  • Cubrimos toda la regla con una fila de piezas simples y dobles, colocadas arbitrariamente.
  • A continuación apilamos un número arbitrario (cero o más) de piezas simples siempre encima de piezas simples ya colocadas y de forma que el número total de piezas situadas sobre la casilla C_i no supere el peso máximo a_i de esa casilla.

La figura adjunta es una configuración que cumple la condición anterior con n+1=9 y con los pesos máximos a_i anotados bajo cada casilla: a_0=5, a_1=4, \ldots ,a_8=6.

Si C[a_0, \ldots,a_n] es el número de las distintas configuraciones de piezas que se pueden formar cumpliendo las condiciones anteriores, resulta que C[a_0, \ldots ,a_n] =  N[a_0, \ldots ,a_n] , es decir, el número de configuraciones es el numerador de la fracción cuya fracción continua tiene los cocientes parciales a_i.

Usando por ejemplo esta calculadora obtenemos que el numero de posibles configuraciones distintas para los pesos máximos indicados en la figura es 225995.

Tenemos que C[a_0] = a_0 y contando las configuraciones que no tienen y que tienen una pieza doble cubriendo las 2 últimas casillas se ve enseguida que  C[a_0,a_1] = a_0a_1 +1 , y C[a_0, \ldots,a_n] = a_nC[a_0, \ldots,a_{n-1}]+C[a_0, \ldots,a_{n-2}].

Como C[a_0,\ldots,a_n] y N[a_0,\ldots,a_n] cumplen la misma relación de recurrencia con los mismos valores iniciales resulta que C[a_0,\ldots,a_n] = N[a_0,\ldots,a_n].

La regla de Euler

La anterior interpretación combinatoria no es más que una reformulación de la regla de Euler que dice que N[a_0,\ldots,a_n] es la suma de determinados productos de los cocientes parciales a_i, que son:

  • El producto de todos los cocientes parciales.
  • Los productos obtenidos suprimiendo de todas la formas posibles 1 pareja de cocientes parciales de indices consecutivos.
  • Los productos obtenidos suprimiendo de todas la formas posibles 2 parejas (disjuntas) de cocientes parciales de indices consecutivos.
  • Etc.

Por otro lado la regla de Euler se obtiene inmediatamente de la interpretación combinatoria.

Consecuencias

La interpretación combinatoria permite demostrar sin usar inducción, estableciendo biyecciones entre conjuntos, identidades relativas a las cantidades N[a_0,\ldots,a_n] .

Por ejemplo, resulta visualmente claro que N[a_0,\ldots ,a_n] = N[a_n,\ldots,a_0], pues hay tantas posibles configuraciones si los mismos pesos están situados de izquierda a derecha que de derecha a izquierda.

También es inmediato, considerando las configuraciones que tienen o no una pieza doble cubriendo las casillas de índices k y k+1, que:

N[a_0,\ldots,a_k,\ldots,a_n] =  N[a_0,\ldots,a_k] N[a_{k+1},\ldots,a_n]+N[a_0,\ldots,a_{k-1}]  N[a_{k+2},\ldots,a_n]

En el artículo referenciado anteriormente se dan demostraciones biyectivas de otras identidades, por ejemplo la que da la diferencia entre dos convergentes consecutivos, que en la notación que hemos usado, es equivalente a:

N[a_0 \ldots,a_n] N[a_1, \ldots,a_{n-1}] - N[a_0 \ldots,a_{n-1}] N[a_1, \ldots,a_n]=(-1)^{n-1}

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

5 Comentarios

  1. “…varias propiedades que hacen que dicha representación sea más interesante que la representación decimal habitual”

    Más interesante… digamos mejor que esas propiedades les confiere algunas ventajas de peso. Pero si lo dejamos ahí queda la duda de si no convendría adoptar esa representación globalmente, desplazando a la decimal común. Hay que agregar, entonces, que la representación en fracciones continuas también tiene sus desventajas. Creo que la más importante, en comparación con la decimal común, es que las operaciones aritméticas básicas (suma, multiplicación ) resultan MUY complicadas.

    Publica una respuesta
  2. Interesante el tema.

    Aprovecho para presentarme, pues he descubierto este blog hace poco y… me encanta 😀 Me queda mucho tiempo hasta que me haya leído todo lo que hay en el archivo.

    Felicidades a los autores, y seguid así.

    Publica una respuesta
  3. hernan, posiblemente el principal problema sea ese, operar con ellas.

    BBoy Gauss, bienvenido a Gaussianos. Busca tiempo libre porque el archivo es bien amplio, son cerca de tres años y medio de blog.

    Ah, por cierto, autor. Comenzamos dos el blog pero desde hace bastante tiempo me encargo únicamente yo de él.

    Publica una respuesta
  4. Iré despacito, a base de 2 o 3 entradas por día 🙂

    Decía lo de autores porque ya había leído la primera entrada del blog y ahí se comentaba que lo habían empezado dos personas. Perdón por el fallo 😉

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: No hay resumen disponible para esta anotación...
  2. Twitter Trackbacks for Fracciones continuas y combinatoria | Gaussianos [gaussianos.com] on Topsy.com - [...] Fracciones continuas y combinatoria | Gaussianos gaussianos.com/fracciones-continuas-y-combinatoria – view page – cached * 2 en ¿Cuánto vale…
  3. Factorización de un primo de la forma 4k+1 en el anillo de los enteros gaussianos | Gaussianos - [...] partir de los resultados mencionados en el post sobre fracciones continuas finitas, y con la notación usada alli, resulta…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *