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

Número de formas de emparejar n objetos

El gráfico completo K ₄ tiene diez coincidencias, correspondientes al valor T (4) = 10 del cuarto número de teléfono.

En matemáticas , los números de teléfono o los números de involución forman una secuencia de números enteros que cuentan las formas en que n personas pueden conectarse mediante llamadas telefónicas de persona a persona. Estos números también describen el número de coincidencias (el índice de Hosoya ) de un gráfico completo en n vértices, el número de permutaciones en n elementos que son involuciones , la suma de valores absolutos de los coeficientes de los polinomios de Hermite , el número de cuadros estándar de Young. con n celdas, y la suma de los grados de las representaciones irreducibles del grupo simétrico . Los números de involución fueron estudiados por primera vez en 1800 por Heinrich August Rothe , quien dio una ecuación de recurrencia mediante la cual se pueden calcular, ^[1] dando los valores (comenzando desde n = 0 )

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ... (secuencia A000085 en el OEIS ).

Aplicaciones

John Riordan proporciona la siguiente explicación para estos números: supongamos que n personas se suscriben a un servicio telefónico que puede conectar a dos de ellas mediante una llamada, pero no puede realizar una sola llamada que conecte a más de dos personas. ¿Cuántos patrones diferentes de conexión son posibles? Por ejemplo, con tres abonados, hay tres formas de realizar una única llamada telefónica y un patrón adicional en el que no se realizan llamadas, para un total de cuatro patrones. ^[2] Por esta razón, los números que cuentan cuántos patrones son posibles a veces se denominan números de teléfono. ^{[3] [4]}

Cada patrón de conexiones por pares entre n personas define una involución , una permutación de las personas que es su propia inversa. En esta permutación, cada dos personas que se llaman se intercambian y las personas que no participan en las llamadas permanecen fijas en su lugar. Por el contrario, toda involución posible tiene la forma de un conjunto de intercambios por pares de este tipo. Por tanto, los números de teléfono también cuentan las involuciones. El problema de contar involuciones fue el problema de enumeración combinatoria original estudiado por Rothe en 1800 ^[1] y estos números también han sido llamados números de involución. ^{[5] [6]}

En teoría de grafos , un subconjunto de las aristas de un gráfico que toca cada vértice como máximo una vez se llama coincidencia . Contar las coincidencias de un gráfico determinado es importante en la teoría química de grafos , donde los gráficos modelan moléculas y el número de coincidencias es el índice de Hosoya . El índice de Hosoya más grande posible de un gráfico de n -vértices viene dado por los gráficos completos , para los cuales es posible cualquier patrón de conexiones por pares; por tanto, el índice de Hosoya de un gráfico completo en n vértices es el mismo que el n -ésimo número de teléfono. ^[7]

Un cuadro joven estándar

Un diagrama de Ferrers es una forma geométrica formada por una colección de n cuadrados en el plano, agrupados en un poliomino con un borde superior horizontal, un borde izquierdo vertical y una única cadena monótona de bordes desde arriba a la derecha hasta abajo a la izquierda. Un cuadro de Young estándar se forma colocando los números del 1 al n en estos cuadrados de tal manera que los números aumentan de izquierda a derecha y de arriba a abajo en todo el cuadro. Según la correspondencia Robinson-Schensted , las permutaciones se corresponden uno por uno con pares ordenados de cuadros estándar de Young . Invertir una permutación corresponde a intercambiar los dos cuadros, por lo que las permutaciones autoinversas corresponden a cuadros únicos, emparejados entre sí. ^[8] Así, los números de teléfono también cuentan el número de cuadros de Young con n cuadrados. ^[1] En la teoría de la representación , los diagramas de Ferrers corresponden a las representaciones irreducibles del grupo simétrico de permutaciones, y los cuadros de Young con una forma dada forman una base de la representación irreducible con esa forma. Por tanto, los números de teléfono dan la suma de los grados de las representaciones irreductibles. ^[9]

Una colocación diagonalmente simétrica y no ofensiva de ocho torres en un tablero de ajedrez.

En las matemáticas del ajedrez , los números de teléfono cuentan el número de formas de colocar n torres en un tablero de ajedrez de n × n de tal manera que no haya dos torres que se ataquen entre sí (el llamado rompecabezas de las ocho torres ), y de tal manera que la configuración de las torres es simétrica bajo un reflejo diagonal del tablero. A través del teorema de enumeración de Pólya , estos números forman uno de los componentes clave de una fórmula para el número total de configuraciones "esencialmente diferentes" de n torres que no se atacan entre sí, donde dos configuraciones se cuentan como esencialmente diferentes si no hay simetría de las tablero que lleva uno al otro. ^[10]

Propiedades matemáticas

Reaparición

Los números de teléfono satisfacen la relación de recurrencia.

$${\displaystyle T(0)=1,}$$

$${\displaystyle T(n)=T(n-1)+(n-1)T(n-2),\quad \mathrm {for~} n\geq 1,}$$

Heinrich August Rothe^[1]T ( n )nT ( n − 1)n − 1T ( n − 2) patrones de conexión para las n − 2^[11]

Fórmula de suma y aproximación.

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!}}.}$$

coeficiente binomialfactorial doble ${\displaystyle k}$ ${\displaystyle {\tbinom {n}{2k}}}$ ${\displaystyle 2k}$

$${\displaystyle (2k-1)!!={\frac {(2k)!}{2^{k}\,k!}}}$$

2 k^{[1] [11] De la fórmula de suma y} de la aproximación de Stirlingasintóticamente^{[1] [11] [12]}

$${\displaystyle T(n)\sim \left({\frac {n}{e}}\right)^{n/2}{\frac {e^{\sqrt {n}}}{(4e)^{1/4}}}\,.}$$

función generadora

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).}$$

serie de Taylorexp( x + x ² /2)nnT ( n )x ^{n −1} / ( n − 1).n ≥ 1

$${\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 {,~which~is} }$$

$${\displaystyle G'(x)=G(x)+xG(x)\,.}$$

G ( x ) ∝ exp( x + x ² /2)T (0) = 1

Esta función está estrechamente relacionada con la función generadora exponencial de los polinomios de Hermite , que son los polinomios coincidentes de las gráficas completas. ^[13] La suma de los valores absolutos de los coeficientes del n -ésimo polinomio de Hermite (probabilista) es el n -ésimo número de teléfono, y los números de teléfono también se pueden representar como ciertos valores especiales de los polinomios de Hermite: ^{[5] [ 13]}

$${\displaystyle T(n)={\frac {{\mathit {He}}_{n}(i)}{i^{n}}}.}$$

factores primos

Para valores grandes de n , el n -ésimo número de teléfono es divisible por una potencia grande 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 probar 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 números primos que dividen al menos a un número de teléfono son ^[15]

2, 5, 13, 19, 23, 29, 31, 43, 53, 59, ... (secuencia A264737 en el OEIS )

Los números primos impares de esta secuencia se han denominado ineficientes . Cada uno de ellos divide infinitos números de teléfono. ^[dieciséis]

Referencias

1. Knuth, Donald E. (1973), El arte de la programación informática , volumen 3: clasificación y búsqueda , lectura, Massachusetts: Addison-Wesley, págs. 65–67, MR  0445948
2. Riordan, John (2002), Introducción al análisis combinatorio , Dover, págs. 85–86
3. Peart, Paul; Woan, Wen-Jin (2000), "Generación de funciones mediante matrices de Hankel y Stieltjes" (PDF) , Journal of Integer Sequences , 3 (2), artículo 00.2.1, Bibcode :2000JIntS...3...21P, MR  1778992
4. Getu, Seyoum (1991), "Evaluación de determinantes mediante funciones generadoras", Mathematics Magazine , 64 (1): 45–53, doi :10.2307/2690455, JSTOR  2690455, MR  1092195
5. Salomón, AI; Blasiak, P.; Duchamp, G.; Horzela, A.; Penson, KA (2005), "Física combinatoria, orden normal y gráficos modelo de Feynman", en Gruber, Bruno J.; Marmo, Giuseppe; Yoshinaga, Naotaka (eds.), Symmetries in Science XI , Kluwer Academic Publishers, págs. 527–536, arXiv : quant-ph/0310174 , doi :10.1007/1-4020-2634-X_25, ISBN 1-4020-2633-1, S2CID  5702844
6. Blasiak, P.; Dattoli, G.; Horzela, A.; Penson, KA; Zhukovsky, K. (2008), "Números de Motzkin, coeficientes trinomiales centrales y polinomios híbridos", Journal of Integer Sequences , 11 (1), artículo 08.1.1, arXiv : 0802.0075 , Bibcode : 2008JIntS..11...11B, Señor  2377567
7. Tichy, Robert F.; Wagner, Stephan (2005), "Problemas extremos para índices topológicos en química combinatoria" (PDF) , Journal of Computational Biology , 12 (7): 1004–1013, doi :10.1089/cmb.2005.12.1004, PMID  16201918
8. ^ Beissinger, Janet Simpson (1987), "Construcciones similares para cuadros e involuciones de Young, y su aplicación a cuadros desplazables", Matemáticas discretas , una biyección directa entre involuciones y cuadros, inspirada en la relación de recurrencia de los números de teléfono . 67 (2): 149–163, doi : 10.1016/0012-365X(87)90024-0 , SEÑOR  0913181
9. Halverson, Tom; Reeks, Mike (2015), "Modelos de Gelfand para álgebras de diagramas", Journal of Algebraic Combinatorics , 41 (2): 229–255, arXiv : 1302.6150 , doi : 10.1007/s10801-014-0534-5 , MR  3306071, S2CID  7419411
10. Holt, DF (1974), "Torres invioladas", The Mathematical Gazette , 58 (404): 131–134, doi :10.2307/3617799, JSTOR  3617799, S2CID  250441965
11. Chowla, S .; Herstein, IN ; Moore, WK (1951), "Sobre recursiones conectadas con grupos simétricos. I", Canadian Journal of Mathematics , 3 : 328–334, doi : 10.4153/CJM-1951-038-3 , MR  0041849, S2CID  123802787
12. Moser, Leo ; Wyman, Max (1955), "Sobre soluciones de x ^d = 1 en grupos simétricos", Canadian Journal of Mathematics , 7 : 159–168, doi : 10.4153/CJM-1955-021-8 , MR  0068564
13. Banderier, Cirilo; Bousquet-Mélou, Mireille ; Denise, Alain; Flajolet, Philippe ; Gardy, Danièle; Gouyou-Beauchamps, Dominique (2002), "Generación de funciones para generar árboles", Matemáticas discretas , 246 (1–3): 29–55, arXiv : math/0411250 , doi :10.1016/S0012-365X(01)00250-3 , SEÑOR  1884885, S2CID  14804110
14. Kim, Dongsu; Kim, Jang Soo (2010), "Un enfoque combinatorio de la potencia de 2 en el número de involuciones", Journal of Combinatorial Theory , Serie A, 117 (8): 1082–1094, arXiv : 0902.4311 , doi :10.1016/j .jcta.2009.08.002, SEÑOR  2677675, S2CID  17457503
15. Sloane, N. J. A. (ed.), "Sequence A264737", La enciclopedia en línea de secuencias enteras , Fundación OEIS
16. Amdeberhan, Tewodros; Moll, Victor (2015), "Involuciones y sus progenies", Journal of Combinatorics , 6 (4): 483–508, arXiv : 1406.2356 , doi :10.4310/JOC.2015.v6.n4.a5, MR  3382606, S2CID  119708272