Número de teléfono (matemáticas)

Los números de teléfono satisfacen la relación de recurrencia.$${\displaystyle T(0)=T(1)=1,}$$$${\displaystyle T(n)=T(n-1)+(n-1)T(n-2),\quad \mathrm {para~} n\geq 2,}$$ Publicado por primera vez en 1800 por Heinrich August Rothe , mediante el cual se pueden calcular fácilmente. ^{[ 1 ]} Una forma de explicar esta recurrencia es dividir los T ( n ) patrones de conexión de los n suscriptores a un sistema telefónico en patrones en los que la primera persona no llama a nadie más y patrones en los que la primera persona realiza una llamada. Hay T ( n − 1 ) patrones de conexión en los que la primera persona está desconectada, lo que explica el primer término de la recurrencia. Si la primera persona está conectada con alguien, hay n − 1 opciones para esa persona y T ( n − 2 ) patrones de conexión para las n − 2 personas restantes, lo que explica el segundo término de la recurrencia. ^{[ 11 ]}

Los números de teléfono pueden expresarse exactamente como una suma.$${\displaystyle T(n)=\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}(2k-1)!!=\sum _{k=0}^{\lfloor n/2\rfloor }{\frac {n!}{2^{k}(n-2k)!k!}}.}$$ En cada término de la primera suma,${\displaystyle k}$da el número de pares coincidentes, el coeficiente binomial${\displaystyle {\tbinom {n}{2k}}}$cuenta el número de formas de elegir el${\displaystyle 2k}$elementos que deben coincidir y el factorial doble$${\displaystyle (2k-1)!!={\frac {(2k)!}{2^{k}\,k!}}}$$es el producto de los enteros impares hasta su argumento y cuenta el número de maneras de hacer coincidir completamente los 2 k elementos seleccionados. ^{[ 1 ] [ 11 ]} Se deduce de la fórmula de suma y la aproximación de Stirling que, asintóticamente , ^{[ 1 ] [ 11 ] [ 12 ]}$${\displaystyle T(n)\sim \left({\frac {n}{e}}\right)^{n/2}{\frac {e^{\sqrt {n}}}{(4e)^{1/4}}}\,.}$$

La función generadora exponencial de los números de teléfono es ^{[ 11 ] [ 13 ]}$${\displaystyle G(x)=\sum _{n=0}^{\infty }{\frac {T(n)x^{n}}{n!}}=\exp \left(x+{\frac {x^{2}}{2}}\right).}$$ En otras palabras, los números de teléfono pueden leerse como los coeficientes de la serie de Taylor de exp( x + x ² /2) y, en particular, el n -ésimo número de teléfono es el valor en cero de la n -ésima derivada de esta función. La función generadora exponencial puede derivarse de varias maneras; por ejemplo, tomando la relación de recurrencia para T ( n ) anterior, multiplicándola por x ^{n −1} / ( n − 1)! , y sumando sobre n ≥ 1 se obtiene $${\displaystyle \sum _{n}T(n){\frac {x^{n-1}}{(n-1)!}}=\sum _{n}T(n-1){\frac {x^{n-1}}{(n-1)!}}+x\sum _{n}T(n-2){\frac {x^{n-2}}{(n-2)!}}\,\mathrm {,~que~es} }$$$${\displaystyle G'(x)=G(x)+xG(x)\,.}$$ La solución general de esta ecuación diferencial es G ( x ) ∝ exp( x + x ² /2) , y T (0) = 1 muestra que la constante de proporcionalidad es 1.

Esta función está estrechamente relacionada con la función generadora exponencial de los polinomios de Hermite , que son los polinomios correspondientes de los grafos completos. ^{[ 13 ]} La suma de los valores absolutos de los coeficientes del n -ésimo polinomio de Hermite (probabilístico) es el n -ésimo número de teléfono, y los números de teléfono también pueden realizarse como ciertos valores especiales de los polinomios de Hermite: ^{[ 5 ] [ 13 ]}$${\displaystyle T(n)={\frac {{\mathit {He}}_{n}(i)}{i^{n}}}.}$$

Para valores grandes de n , el n -ésimo número de teléfono es divisible por una gran potencia de dos , 2 ^{n /4 + O (1)} . Más precisamente, el orden 2-ádico (el número de factores de dos en la factorización prima ) de T (4 k ) y de T (4 k + 1) es k ; para T (4 k + 2) es k + 1 , y para T (4 k + 3) es k + 2 . ^{[ 14 ]}

Para cualquier número primo p , se puede comprobar si existe un número de teléfono divisible por p calculando la recurrencia de la secuencia de números de teléfono, módulo p , hasta llegar a cero o detectar un ciclo . Los primos que dividen al menos un número de teléfono son ^{[ 15 ].}

Los números primos impares de esta secuencia se han denominado ineficientes . Cada uno de ellos divide una cantidad infinita de números de teléfono. ^{[ 16 ]}