Árbol Culkin - Wilf

El árbol de Calkin-Wilf es un árbol binario orientado cuyos vértices contienen fracciones racionales positivas según la siguiente regla:

la raíz del árbol es una fracción ; ${\frac{1}{1}}$
el vértice con una fracción tiene dos hijos: (izquierda) y (derecha). ${\frac{m}{n))$ ${\frac{m}{m+n))$ ${\frac {m+n}{n))$

El árbol fue descrito por Neil Culkin y Herbert S. Wilf (2000 [1] ) en relación con el problema del recálculo explícito [2] del conjunto de números racionales.

Propiedades del árbol de Culkin-Wilph

Propiedades básicas

Todas las fracciones ubicadas en los vértices del árbol son irreducibles;
Cualquier fracción racional irreducible ocurre exactamente una vez en el árbol.

La secuencia de Culkin-Wilph

De las propiedades anteriores se deduce que la secuencia de números racionales positivos obtenida como resultado de la amplitud - primer recorrido [3] del árbol de Calkin-Wilf (también llamada secuencia de Culkin-Wilf ; véase la ilustración),

{\frac {1}{1)),{\frac {1}{2)),{\frac {2}{1)),{\frac {1}{3)),{\frac {3}{2)),{\frac {2}{3)),{\frac {3}{1)),{\frac {1}{4)),{\frac {4}{3} },{\frac {3}{5)),{\frac {5}{2)),{\frac {2}{5)),{\frac {5}{3)),{\frac { 3}{4}},\puntos

define una correspondencia uno a uno entre el conjunto de números naturales y el conjunto de números racionales positivos.

Esta sucesión puede estar dada por la relación de recurrencia [4]

{\ estilo de visualización q_ {1} = 1;}

q_{i+1}={\frac {1}{\lpiso q_{i}\rpiso +1-\{q_{i}\))}={\frac {1}{2\lpiso q_ {i}\rpiso -q_{i}+1}},\quad i=1,2,\puntos,

donde y denotan las partes entera y fraccionaria del número , respectivamente . $\lpiso x\rpiso$ $\{X\}$ $X$

En la sucesión de Culkin-Wilf, el denominador de cada fracción es igual al numerador de la siguiente.

funcion fusc

En 1976, E. Dijkstra definió la función entera fusc( n ) sobre el conjunto de los números naturales mediante las siguientes relaciones recursivas [5] :

{\ estilo de visualización \ nombre del operador {fusc} (1) = 1}

;

{\ estilo de visualización \ nombre del operador {fusc} (2n) = \ nombre del operador {fusc} (n)}

;

\nombre del operador {fusc} (2n+1)=\nombre del operador {fusc} (n)+\nombre del operador {fusc} (n+1)

La secuencia de valores coincide con la secuencia de numeradores de fracciones en la secuencia de Calkin-Wilf, es decir, la secuencia ${\ estilo de visualización \ nombre del operador {fusc} (n), n = 1,2,3, \ puntos}$

1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, …

Así (dado que el denominador de cada fracción en la sucesión de Culkin-Wilf es igual al numerador de la siguiente), el término de la sucesión de Culkin-Wilf es , y la correspondencia $norte$ ${\ estilo de visualización \ nombre del operador {fusc} (n)/\ nombre del operador {fusc} (n+1)}$

n\mapsto {\frac {\operatorname {fusc} (n)}{\operatorname {fusc} (n+1))),\quad n=1,2,3,\dots

es una correspondencia biunívoca entre el conjunto de los números naturales y el conjunto de los números racionales positivos.

La función puede definirse, además de las relaciones de recurrencia anteriores, como sigue. ${\ estilo de visualización \ nombre del operador {fusc}}$

El valor es igual al número de representaciones hiperbinarias de un número , es decir, representaciones en forma de suma de potencias no negativas de dos, donde cada grado ocurre no más de dos veces [6] . Por ejemplo, el número 6 se representa de tres formas: $\operatorname {fusc} (n+1),n\geqslant 0$ $norte$ $2^k$

6 = 4 + 2 = 4 + 1 + 1 = 2 + 2 + 1 + 1, entonces .

{\displaystyle\operatorname {fusc} (6+1)=3}

El valor es igual al número de todos los coeficientes binomiales impares de la forma , donde [7] . $\operatorname {fusc} (n+1),n\geqslant 0$ ${\binom {nr}{r))$ $0\leqslant 2r<n$

El artículo original de Calkin y Wilf no menciona la función, pero considera una función entera definida para , igual al número de representaciones hiperbinarias de , y prueba que la correspondencia ${\ estilo de visualización \ nombre del operador {fusc}}$ ${\ estilo de visualización b (n)}$ ${\ estilo de visualización n = 0,1,2, \ puntos}$ $norte$

n\mapsto {\frac {b(n)}{b(n+1))),\quad n=0,1,2,\dots

es una correspondencia uno a uno entre el conjunto de números enteros no negativos y el conjunto de números racionales. Así, por ${\ estilo de visualización n = 0,1,2, \ puntos}$

b(n)=\operatorname {fusc} (n+1),

{\ estilo de visualización b (2n + 1) = b (n),}

{\ estilo de visualización b (2n + 2) = b (n) + b (n + 1).}

Árbol de Kepler y Saltus Gerberti

Véase también

Árbol de popa - Broko

Notas

↑ Véase Calkin, Wilf (2000) en la bibliografía.
↑ Es decir, una asignación explícita de una correspondencia biunívoca entre el conjunto de los números naturales y el conjunto de los números racionales (positivos) . Las pruebas estándar de la contabilidad del conjunto de números racionales generalmente no usan explícitamente la correspondencia especificada.
↑ En este caso, el recorrido de "ancho" corresponde al recorrido secuencial de cada nivel (comenzando desde la parte superior) del árbol Calkin-Wilf de izquierda a derecha (ver la primera ilustración).
↑ Encontrado por Moshe Newman; ver Aigner y Ziegler en la bibliografía, p. 108.
↑ Documento EWD 570: Un ejercicio para el Dr. R. M. Burstall Archivado el 15 de agosto de 2021 en Wayback Machine ; reproducido en Dijkstra (1982) (ver bibliografía), pp. 215-216.
↑ En este caso, se considera que el número 0 tiene una representación hiperbinaria única ("vacía") 0 = 0, por lo tanto . ${\ estilo de visualización \ nombre del operador {fusc} (0+1) = 1}$
↑ Véase Carlitz, L. Un problema de particiones relacionado con los números de Stirling // Bulletin of the American Mathematical Society. - 1964. - Vol. 70, núm. 2 . - Pág. 275-278. Este artículo define una función que resulta estar relacionada con la función fusc por la relación . ${\ estilo de visualización \ theta _ {0} (n)}$ ${\ estilo de visualización \ theta _ {0} (n) = \ nombre del operador {fusc} (n + 1)}$

Literatura

Calkin, N., Wilf HS Recuento de los Racionales // The American Mathematical Monthly. - 2000. - vol. 107, núm. 4 . - Pág. 360-363. ( JSTOR 2589182 )
Aigner M., Ziegler G. Evidencia del libro. La mejor evidencia desde la época de Euclides hasta nuestros días (traducido del inglés) . - M. : Mir, 2006. - S. 105 -109. — 256 págs. — ISBN 5-03-003690-3 . ( NB : en esta traducción, el apellido Wilf se transcribe como "Wilf".)
Dijkstra, E. W. Escritos seleccionados sobre computación: una perspectiva personal . - Springer-Verlag, 1982. - ISBN 0-387-90652-5 . (Ver EWD 570 y EWD 578 reproducidos en este libro).
Stern M. Über eine zahlentheoretische Funktion // Journal für die reine und angewandte Mathematik. - 1858. - T. 55 . - S. 193-220 .
Shchetnikov AI Algoritmo para desarrollar todas las relaciones numéricas a partir de la relación de igualdad y los números ideales de Platón // ΣΧΟΛΗ . - 2008. - T. 2 . - S. 55-74 . — ISSN 1995-4328 .