Número de timbre ordenado

Número de pedidos débiles

Los 13 posibles ordenamientos débiles estrictos en un conjunto de tres elementos { a , b , c }

En teoría de números y combinatoria enumerativa , los números de Bell ordenados o los números de Fubini cuentan los ordenamientos débiles de un conjunto de elementos. Los ordenamientos débiles organizan sus elementos en una secuencia que permite vínculos , como los que podrían surgir como resultado de una carrera de caballos . ^{[1] [2]} ${\displaystyle n}$

Los números ordenados de Bell fueron estudiados en el siglo XIX por Arthur Cayley y William Allen Whitworth . Llevan el nombre de Eric Temple Bell , quien escribió sobre los números de Bell , que cuentan las particiones de un conjunto ; Los números de Bell ordenados cuentan las particiones que han sido equipadas con un pedido total . Su nombre alternativo, números de Fubini, proviene de una conexión con Guido Fubini y el teorema de Fubini sobre formas equivalentes de integrales múltiples. Debido a que los ordenamientos débiles tienen muchos nombres, los números de Bell ordenados también pueden recibir esos nombres, por ejemplo, como números de arreglos preferenciales ^[3] o números de órdenes débiles generalizados asimétricos. ^[4]

Estos números se pueden calcular mediante una fórmula de suma que incluya coeficientes binomiales o utilizando una relación de recurrencia . También cuentan objetos combinatorios que tienen una correspondencia biyectiva con los ordenamientos débiles, como las particiones multiplicativas ordenadas de un número libre de cuadrados ^[5] o las caras de todas las dimensiones de un permutoedro . ^[6]

Definiciones y ejemplos

Los ordenamientos débiles organizan sus elementos en una secuencia que permite vínculos . Esta posibilidad describe diversos escenarios del mundo real, incluidas determinadas competencias deportivas como las carreras de caballos . ^{[1] [2]} Un ordenamiento débil puede formalizarse axiomáticamente mediante un conjunto parcialmente ordenado para el cual la incomparabilidad es una relación de equivalencia . Las clases de equivalencia de esta relación dividen los elementos del ordenamiento en subconjuntos de elementos mutuamente vinculados, y estas clases de equivalencia pueden luego ordenarse linealmente mediante el ordenamiento débil. Así, un ordenamiento débil puede describirse como una partición ordenada , una partición de sus elementos y un orden total sobre los conjuntos de la partición. ^[7] Por ejemplo, la partición ordenada { a , b }, { c }, { d , e , f } describe una partición ordenada en seis elementos en los que a y b están empatados y ambos son menores que los otros cuatro elementos, y c es menor que d , e y f , todos relacionados entre sí.

El número de Bell ordenado, denotado aquí , proporciona el número de ordenamientos débiles distintos de los elementos. ^[8] Por ejemplo, hay tres ordenamientos débiles en los dos elementos a y b : se pueden ordenar con a antes de b , con b antes de a , o con ambos empatados. La figura muestra los 13 ordenamientos débiles de tres elementos. ${\displaystyle n}$ ${\displaystyle a(n)}$ ${\displaystyle n}$

A partir de , los números de Bell ordenados son ${\displaystyle n=0}$ ${\displaystyle a(n)}$

1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, ... (secuencia A000670 en el OEIS ).

Cuando los elementos a ordenar no están etiquetados (solo importa el número de elementos en cada conjunto vinculado, no sus identidades), lo que queda es una composición o partición de enteros ordenados, una representación de como una suma ordenada de números enteros positivos. Por ejemplo, la partición ordenada { a , b }, { c }, { d , e , f } discutida anteriormente corresponde de esta manera a la composición 2 + 1 + 3. El número de composiciones de es exactamente . Esto se debe a que una composición está determinada por su conjunto de sumas parciales , que pueden ser cualquier subconjunto de los números enteros del 1 al . ^[4] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 2^{n-1}}$ ${\displaystyle n-1}$

Historia

13 plátanos con hojas ordenadas y caminos de raíces y hojas de igual longitud, con los espacios entre hojas adyacentes etiquetados por la altura sobre las hojas del ancestro común más cercano. Estas etiquetas inducen un ordenamiento débil en los espacios, lo que muestra que los árboles de este tipo se cuentan según los números de Bell ordenados.

Los números ordenados de Bell aparecen en el trabajo de Cayley (1859), quien los utilizó para contar ciertos plátanos con hojas totalmente ordenadas. En los árboles considerados por Cayley, cada camino de raíz a hoja tiene la misma longitud, y el número de nodos a distancia de la raíz debe ser estrictamente menor que el número de nodos a distancia , hasta llegar a las hojas. ^[9] En tal árbol, hay pares de hojas adyacentes, que pueden estar débilmente ordenadas por la altura de su ancestro común más bajo ; este orden débil determina el árbol. Mor y Fraenkel (1984) llaman a los árboles de este tipo "árboles de Cayley", y denominan a las secuencias que pueden usarse para etiquetar sus espacios (secuencias de números enteros positivos que incluyen al menos una copia de cada número entero positivo entre uno y el máximo). valor en la secuencia) "Permutaciones de Cayley". ^[10] ${\displaystyle n+1}$ ${\displaystyle i}$ ${\displaystyle i+1}$ ${\displaystyle n}$ ${\displaystyle n}$

Pippenger (2010) remonta el problema de contar ordenamientos débiles, que tienen la misma secuencia como solución, al trabajo de Whitworth (1886). ^{[8] [11]} Estos números fueron llamados números de Fubini por Louis Comtet, porque cuentan las diferentes formas de reordenar las sumas o integrales en el teorema de Fubini , que a su vez lleva el nombre de Guido Fubini . ^[12] Los números de Bell , que llevan el nombre de Eric Temple Bell , cuentan las particiones de un conjunto , y los ordenamientos débiles que se cuentan mediante los números de Bell ordenados pueden interpretarse como una partición junto con un orden total de los conjuntos en la partición. ^[13]

La equivalencia entre contar árboles de Cayley y contar ordenamientos débiles fue observada en 1970 por Donald Knuth , utilizando una versión temprana de la Enciclopedia en línea de secuencias enteras (OEIS). Este se convirtió en uno de los primeros usos exitosos del OEIS para descubrir equivalencias entre diferentes problemas de conteo. ^[4]

Fórmulas

Suma

Debido a que los ordenamientos débiles pueden describirse como ordenamientos totales en los subconjuntos de una partición, se pueden contar los ordenamientos débiles contando los ordenamientos totales y las particiones, y combinando los resultados de manera apropiada. Los números de Stirling del segundo tipo , denotados , cuentan las particiones de un conjunto de elementos en subconjuntos no vacíos. Se puede obtener un ordenamiento débil de dicha partición eligiendo uno de los ordenamientos totales de sus subconjuntos. Por lo tanto, los números de Bell ordenados se pueden contar sumando los números posibles de subconjuntos en una partición (el parámetro ) y, para cada valor de , multiplicando el número de particiones por el número de ordenamientos totales . Es decir, como fórmula de suma : ^{[14] [15]} Según los resultados generales de sumas que involucran números de Stirling, se deduce que los números de Bell ordenados son log-convexos , lo que significa que obedecen a la desigualdad para todos . ^[dieciséis] ${\displaystyle \{{\scriptstyle {n \atop k}}\}}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k!}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \{{\scriptstyle {n \atop k}}\}}$ ${\displaystyle k!}$ $${\displaystyle a(n)=\sum _{k=0}^{n}k!\left\{{\begin{matrix}n\\k\end{matrix}}\right\}}$$ ${\displaystyle a(n-1)a(n+1)\geq a(n)^{2}}$ ${\displaystyle n>0}$

Un octaedro truncado tridimensional , con sus vértices etiquetados por sus coordenadas cuatridimensionales como un permutoedro.

Una interpretación alternativa de los términos de esta suma es que cuentan las características de cada dimensión en un permutoedro de dimensión , con el término ésimo contando las características de dimensión . Un permutoedro es un politopo convexo , la capa convexa de puntos cuyos vectores de coordenadas son las permutaciones de los números del 1 al . Estos vectores están definidos en un espacio de dimensión , pero ellos y su casco convexo se encuentran todos en un subespacio afín de dimensión . Por ejemplo, el permutoedro tridimensional es el octaedro truncado , la capa convexa de puntos cuyas coordenadas son permutaciones de (1,2,3,4), en el subespacio tridimensional de puntos cuya suma de coordenadas es 10. Este poliedro tiene un volumen ( ), 14 caras bidimensionales ( ), 36 aristas ( ) y 24 vértices ( ). El número total de estas caras es 1 + 14 + 36 + 24 = 75, un número de Bell ordenado, correspondiente a la fórmula de suma anterior para . ^[17] ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n-k}$ ${\displaystyle n}$ ${\displaystyle n+1}$ ${\displaystyle n}$ ${\displaystyle k=0}$ ${\displaystyle k=1}$ ${\displaystyle k=2}$ ${\displaystyle k=3}$ ${\displaystyle n=3}$

Al expandir cada número de Stirling en esta fórmula a una suma de coeficientes binomiales , la fórmula para los números de Bell ordenados se puede expandir a una suma doble. Los números de Bell ordenados también pueden estar dados por una serie infinita : ^{[8] [13]} $${\displaystyle a(n)=\sum _{k=0}^{n}\sum _{j=0}^{k}(-1)^{k-j}{\binom {k}{j}}j^{n}={\frac {1}{2}}\sum _{m=0}^{\infty }{\frac {m^{n}}{2^{m}}}.}$$

Otra fórmula de suma expresa los números de Bell ordenados en términos de los números eulerianos , que cuentan las permutaciones de elementos en los que pares de elementos consecutivos están en orden creciente: ^[18] donde está el ésimo polinomio euleriano . Una forma de explicar esta fórmula de suma implica un mapeo de ordenamientos débiles de los números del 1 al 1 , obtenido al clasificar cada conjunto vinculado en orden numérico. Según este mapeo, cada permutación con pares crecientes consecutivos proviene de ordenamientos débiles, que se distinguen entre sí por el subconjunto de pares crecientes consecutivos que están empatados en el ordenamiento débil. ^[18] ${\displaystyle \langle {\scriptstyle {n \atop k}}\rangle }$ ${\displaystyle n}$ ${\displaystyle k}$ $${\displaystyle a(n)=\sum _{k=0}^{n-1}2^{k}\left\langle {\begin{matrix}n\\k\end{matrix}}\right\rangle =A_{n}(2),}$$ ${\displaystyle A_{n}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle 2^{k}}$

Función generadora y aproximación.

Como ocurre con muchas otras secuencias de números enteros, reinterpretar la secuencia como los coeficientes de una serie de potencias y trabajar con la función que resulta de sumar esta serie puede proporcionar información útil sobre la secuencia. El rápido crecimiento de los números de Bell ordenados hace que su función generadora ordinaria diverja; en su lugar , se utiliza la función generadora exponencial . Para los números de Bell ordenados, es: ^{[8] [13] [15] [19]} Aquí, el lado izquierdo es solo la definición de la función generadora exponencial y el lado derecho es la función obtenida de esta suma. La forma de esta función corresponde a que los números de Bell ordenados son los números de la primera columna de la matriz infinita . Aquí está la matriz identidad y es una forma matricial infinita del triángulo de Pascal . Cada fila comienza con los números en la misma fila del triángulo de Pascal y luego continúa con una secuencia infinita y repetida de ceros. ^[20] $${\displaystyle \sum _{n=0}^{\infty }a(n){\frac {x^{n}}{n!}}={\frac {1}{2-e^{x}}}.}$$ ${\displaystyle (2I-P)^{-1}}$ ${\displaystyle I}$ ${\displaystyle P}$ ${\displaystyle P}$

Basándose en una integración de contorno de esta función generadora, los números de Bell ordenados se pueden expresar mediante la suma infinita ^{[21] [5]} Aquí, representa el logaritmo natural . Esto conduce a una aproximación de los números de Bell ordenados, obtenidos utilizando sólo el término for en esta suma y descartando los términos restantes: ^{[21] [3] [5] [15] [22]} donde . Por tanto, los números de Bell ordenados son mayores que los factoriales en un factor exponencial. Aquí, como en la aproximación de Stirling al factorial, indica equivalencia asintótica . Es decir, la relación entre los números de Bell ordenados y su aproximación tiende a uno en el límite a medida que crece arbitrariamente. Como se expresa en notación o pequeña , el error relativo es y el término de error decae exponencialmente a medida que crece. ^[5] $${\displaystyle a(n)={\frac {n!}{2}}\sum _{k=-\infty }^{\infty }(\log 2+2\pi ik)^{-(n+1)},\qquad n\geq 1.}$$ ${\displaystyle \log }$ ${\displaystyle k=0}$ $${\displaystyle a(n)\sim {\frac {1}{2}}{n!}\,c^{n+1},}$$ ${\displaystyle c={\tfrac {1}{\log 2}}\approx 1.4427}$ ${\displaystyle \sim }$ ${\displaystyle n}$ ${\displaystyle 1\pm o(1)}$ ${\displaystyle o(1)}$ ${\displaystyle n}$

Comparando las aproximaciones para y se muestra que , por ejemplo, al tomar se obtiene la aproximación a . Esta secuencia de aproximaciones, y este ejemplo de ella, fueron calculados por Ramanujan , utilizando un método general para resolver ecuaciones numéricamente (aquí, la ecuación ). ^{[4] [23]} ${\displaystyle a(n-1)}$ ${\displaystyle a(n)}$ $${\displaystyle \lim _{n\to \infty }{\frac {n\,a(n-1)}{a(n)}}=\log 2.}$$ ${\displaystyle n=5}$ ${\displaystyle 375/541\approx 0.693161}$ ${\displaystyle \log 2\approx 0.693145}$ ${\displaystyle e^{x}=2}$

Recurrencia y periodicidad modular.

Además de las fórmulas anteriores, los números de Bell ordenados se pueden calcular mediante la relación de recurrencia ^{[3] [8]}

${\displaystyle a(n)=\sum _{i=1}^{n}{\binom {n}{i}}a(n-i).}$

El significado intuitivo de esta fórmula es que un orden débil de elementos puede descomponerse en una elección de algún conjunto no vacío de elementos que entran en la primera clase de equivalencia del orden, junto con un orden débil más pequeño de los elementos restantes. Hay opciones del primer conjunto y opciones del orden débil en el resto de los elementos. Al multiplicar estos dos factores y luego sumar las opciones de cuántos elementos incluir en el primer conjunto, se obtiene el número de ordenamientos débiles, . Como caso base para la recurrencia (hay un orden débil en cero elementos). Con base en esta recurrencia, se puede demostrar que estos números obedecen ciertos patrones periódicos en aritmética modular : para , suficientemente grandes , ${\displaystyle n}$ ${\displaystyle i}$ ${\displaystyle n-i}$ ${\displaystyle {\tbinom {n}{i}}}$ ${\displaystyle a(n-i)}$ ${\displaystyle a(n)}$ ${\displaystyle a(0)=1}$ ${\displaystyle n}$

${\displaystyle a(n+4)\equiv a(n){\pmod {10}},}$^[3]

${\displaystyle a(n+20)\equiv a(n){\pmod {100}},}$

${\displaystyle a(n+100)\equiv a(n){\pmod {1000}},}$y

${\displaystyle a(n+500)\equiv a(n){\pmod {10000}}.}$^[24]

Se conocen muchas más identidades modulares, incluidas identidades módulo cualquier potencia primaria . ^{[14] [25] [26]} Peter Bala ha conjeturado que esta secuencia es eventualmente periódica (después de un número finito de términos) módulo cada entero positivo , con un período que divide la función totiente de Euler de , el número de residuos mod que son relativamente cebar a . ^[4] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

Aplicaciones

enumeración combinatoria

Como ya se ha mencionado, los números ordenados de Bell cuentan ordenamientos débiles, caras de permutoedro , árboles de Cayley, permutaciones de Cayley y fórmulas equivalentes en el teorema de Fubini. Los ordenamientos débiles, a su vez, tienen muchas otras aplicaciones. Por ejemplo, en las carreras de caballos , las finales fotográficas han eliminado la mayoría, pero no todos los empates, llamados en este contexto empates , y se puede describir el resultado de una carrera que puede contener empates (incluidos todos los caballos, no solo los tres primeros clasificados). utilizando un orden débil. Por esta razón, los números ordenados de Bell cuentan el número posible de resultados de una carrera de caballos. ^[1] Por el contrario, cuando los elementos se ordenan o clasifican de una manera que no permite empates (como ocurre con el orden de las cartas en una baraja de cartas o el orden de bateo entre los jugadores de béisbol ), el número de ordenamientos de los elementos es un número factorial , ^[27] que es significativamente menor que el número de Bell ordenado correspondiente. ^[28] ${\displaystyle n}$ ${\displaystyle n!}$

Los problemas en muchas áreas se pueden formular utilizando ordenamientos débiles, y las soluciones se cuentan utilizando números de Bell ordenados. Velleman y Call (1995) consideran cerraduras de combinación con un teclado numérico, en las que se pueden presionar varias teclas simultáneamente y una combinación consiste en una secuencia de pulsaciones de teclas que incluye cada tecla exactamente una vez. Como muestran, el número de combinaciones diferentes en dicho sistema viene dado por los números de Bell ordenados. ^[18] En seru , una técnica japonesa para equilibrar líneas de montaje , los trabajadores con capacitación cruzada se asignan a grupos de trabajadores en diferentes etapas de una línea de producción. El número de asignaciones alternativas para un número determinado de trabajadores, teniendo en cuenta las opciones de cuántas etapas usar y cómo asignar trabajadores a cada etapa, es un número de Bell ordenado. ^[29] Como otro ejemplo, en la simulación por computadora de origami , los números de Bell ordenados dan el número de ordenaciones en las que se pueden doblar los pliegues de un patrón de pliegue , lo que permite doblar conjuntos de pliegues simultáneamente. ^[30]

En teoría de números , una partición multiplicativa ordenada de un número entero positivo es una representación del número como producto de uno o más de sus divisores . Por ejemplo, 30 tiene 13 particiones multiplicativas, como producto de un divisor (el propio 30), dos divisores (por ejemplo 6 · 5 ) o tres divisores ( 3 · 5 · 2 , etc.). Un número entero no tiene cuadrados cuando es producto de números primos distintos ; 30 no tiene cuadrados, pero 20 no, porque su factorización prima 2 · 2 · 5 repite el primo 2. Para números libres de cuadrados con factores primos, una partición multiplicativa ordenada se puede describir mediante un ordenamiento débil de sus factores primos, que describe qué primo aparece en qué plazo de la partición. Por tanto, el número de particiones multiplicativas ordenadas viene dado por . Por otro lado, para una potencia prima con exponente , una partición multiplicativa ordenada es un producto de potencias del mismo número primo, con exponentes que suman , y esta suma ordenada de exponentes es una composición de . Así, en este caso, existen particiones multiplicativas ordenadas. Los números que no son libres de cuadrados ni potencias primas tienen un número de particiones multiplicativas ordenadas que (en función del número de factores primos) se encuentran entre estos dos casos extremos. ^[31] ${\displaystyle n}$ ${\displaystyle a(n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 2^{n-1}}$

Una función de estacionamiento , en matemáticas, es una secuencia finita de números enteros positivos con la propiedad de que, para cada longitud de la secuencia, la secuencia contiene al menos valores que son como máximo . Una secuencia de este tipo, de longitud , describe el siguiente proceso: una secuencia de coches llega a una calle con plazas de aparcamiento. Cada coche tiene una plaza de aparcamiento preferida, determinada por su valor en la secuencia. Cuando un coche llega a la calle, aparca en su lugar preferido o, si está lleno, en el siguiente lugar disponible. Una secuencia de preferencias forma una función de estacionamiento si y sólo si cada automóvil puede encontrar un lugar para estacionar en o después de su lugar preferido. El número de funciones de aparcamiento de longitud es exactamente . Para una clase restringida de funciones de aparcamiento, en la que cada coche aparca en su lugar preferido o en el siguiente, el número de funciones de aparcamiento viene dado por los números de timbre ordenados. Cada función de estacionamiento restringido corresponde a un ordenamiento débil en el que los automóviles que obtienen su lugar preferido están ordenados por estos lugares, y cada automóvil restante está vinculado con el automóvil en su lugar preferido. Las permutaciones , contadas mediante factoriales, son funciones de aparcamiento por las que cada coche aparca en su lugar preferido. ^[32] Esta aplicación también proporciona una prueba combinatoria para los límites superior e inferior de los números de Bell ordenados de forma simple, ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle (n+1)^{n-1}}$ $${\displaystyle n!\leq a(n)\leq (n+1)^{n-1}.}$$

El complejo de Coxeter corta el espacio en 24 conos triangulares, mostrados aquí por sus intersecciones con una esfera unitaria . Los planos de reflexión cortan la esfera en grandes círculos . Las caras del complejo intersecan la esfera en 24 triángulos, 36 arcos y 14 vértices; una cara más, en el centro de la esfera, no es visible. ${\displaystyle A_{3}}$ ${\displaystyle A_{3}}$

El número de Bell ordenado cuenta el número de caras en el complejo de Coxeter asociadas con un grupo de tipo Coxeter . Aquí, se puede pensar en un grupo de Coxeter como un sistema finito de simetrías de reflexión, cerrado bajo reflexiones repetidas, cuyos espejos dividen un espacio euclidiano en las celdas del complejo de Coxeter. Por ejemplo, corresponde a , el sistema de reflexiones del plano euclidiano a través de tres rectas que se encuentran en el origen formando ángulos. El complejo formado por estas tres líneas tiene 13 caras: el origen, seis rayos desde el origen y seis regiones entre pares de rayos. ^[4] ${\displaystyle a(n)}$ ${\displaystyle A_{n-1}}$ ${\displaystyle a(3)=13}$ ${\displaystyle A_{2}}$ ${\displaystyle 60^{\circ }}$

Kemeny (1956) utiliza los números de Bell ordenados para analizar relaciones n -arias , enunciados matemáticos que pueden ser verdaderos para algunas elecciones de los argumentos de la relación y falsos para otras. Define la "complejidad" de una relación como el número de otras relaciones que uno puede derivar de la dada permutando y repitiendo sus argumentos. Por ejemplo, para , una relación sobre dos argumentos y podría tomar la forma . Según el análisis de Kemeny, tiene relaciones derivadas. Estas son la relación dada , la relación inversa obtenida al intercambiar los argumentos y la relación unaria obtenida al repetir un argumento. (La repetición del otro argumento produce la misma relación). ^[33] ${\displaystyle n}$ ${\displaystyle n=2}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y=f(x)}$ ${\displaystyle a(n)=3}$ ${\displaystyle y=f(x)}$ ${\displaystyle x=f(y)}$ ${\displaystyle x=f(x)}$

Ellison y Klein (2001) aplican estos números a la teoría de la optimización en lingüística . En esta teoría, las gramáticas de los lenguajes naturales se construyen clasificando ciertas restricciones y (en un fenómeno llamado tipología factorial) el número de gramáticas diferentes que se pueden formar de esta manera se limita al número de permutaciones de las restricciones. Un artículo revisado por Ellison y Klein sugirió una extensión de este modelo lingüístico en el que se permiten vínculos entre restricciones, de modo que la clasificación de las restricciones se convierta en un orden débil en lugar de un orden total. Como señalan, la magnitud mucho mayor de los números de Bell ordenados, en relación con los factoriales correspondientes , permite que esta teoría genere un conjunto de gramáticas mucho más rico. ^[28]

Otro

Si se lanza repetidamente una moneda justa (con igual probabilidad de que salga cara o cruz) hasta que la primera vez el resultado sea cara, el número de cruces sigue una distribución geométrica . Los momentos de esta distribución son los números de Bell ordenados. ^[4]

Aunque la función generadora ordinaria de los números de Bell ordenados no converge, describe una serie de potencias que (evaluada en y luego multiplicada por ) proporciona una expansión asintótica para la distancia de resistencia de los vértices opuestos de un gráfico de hipercubo bidimensional . Truncar esta serie a un número acotado de términos y luego aplicar el resultado para valores ilimitados de aproxima la resistencia a un orden arbitrariamente alto. ^[8] ${\displaystyle {\tfrac {1}{n}}}$ ${\displaystyle {\tfrac {2}{n}}}$ ${\displaystyle n}$ ${\displaystyle n}$

En el álgebra de anillos no conmutativos , una construcción análoga a las funciones cuasisimétricas (conmutativas) produce un álgebra graduada WQSym cuyas dimensiones en cada grado están dadas por los números de Bell ordenados. ^{[34] [35]}

En el filtrado de spam , el problema de asignar pesos a secuencias de palabras con la propiedad de que el peso de cualquier secuencia excede la suma de los pesos de todas sus subsecuencias se puede resolver usando el peso para una secuencia de palabras, que se obtiene de la ecuación de recurrencia. con estuche base . Esta recurrencia difiere de la dada anteriormente para los números de Bell ordenados, en dos aspectos: omitir el término de la suma (porque sólo se consideran secuencias no vacías) y agregar uno por separado de la suma (para que el resultado exceda, en lugar de igualar). , la suma). Estas diferencias tienen efectos compensatorios y los pesos resultantes son los números de Bell ordenados. ^[36] ${\displaystyle W(n)}$ ${\displaystyle n}$ ${\displaystyle W(n)}$ $${\displaystyle W(n)=1+\sum _{k=1}^{n-1}{\binom {n}{k}}W(n-1),}$$ ${\displaystyle W(1)=0}$ ${\displaystyle W(0)}$

Referencias

1. de Koninck, JM (2009), Esos números fascinantes, Sociedad Matemática Estadounidense, p. 4, ISBN 9780821886311. Debido a esta aplicación, de Koninck llama a estos números "números de caballos", pero este nombre no parece tener un uso generalizado.
2. Mendelson, Elliott (1982), "Carreras con empates", Revista de Matemáticas , 55 (3): 170–175, doi :10.2307/2690085, JSTOR  2690085, MR  0653432
3. Gross, OA (1962), "Acuerdos preferenciales", The American Mathematical Monthly , 69 (1): 4–8, doi :10.2307/2312725, JSTOR  2312725, MR  0130837
4. Sloane, N. J. A. (ed.), "Sequence A000670", La enciclopedia en línea de secuencias enteras , Fundación OEIS
5. Sklar, Abe (1952), "Sobre la factorización de enteros libres de cuadrados", Actas de la Sociedad Matemática Estadounidense , 3 (5): 701–705, doi : 10.1090/S0002-9939-1952-0050620-1 , JSTOR  2032169 , SEÑOR  0050620
6. Ziegler, Günter M. (1995), Conferencias sobre politopos , Textos de posgrado en matemáticas, vol. 152, Springer, pág. 18
7. Luce, R. Duncan (1956), "Semiórdenes y una teoría de la discriminación de utilidad", Econometrica , 24 : 178–191, doi : 10.2307/1905751, JSTOR  1905751, MR  0078632
8. Pippenger, Nicholas (2010), "El hipercubo de resistencias, expansiones asintóticas y arreglos preferenciales", Mathematics Magazine , 83 (5): 331–346, arXiv : 0904.1757 , doi : 10.4169/002557010X529752, JSTOR  10.4169/002557 010X529752, SEÑOR  2762645, S2CID  17260512
9. Cayley, A. (1859), "Sobre las formas analíticas llamadas árboles, segunda parte", Revista Filosófica , Serie IV, 18 (121): 374–378, doi :10.1017/CBO9780511703706.026, ISBN 9781108004961, en Obras completas de Arthur Cayley, p. 113
10. Mor, M.; Fraenkel, AS (1984), "Permutaciones de Cayley", Matemáticas discretas , 48 ​​(1): 101–112, doi :10.1016/0012-365X(84)90136-5, SEÑOR  0732206
11. Whitworth, WA (1886), Elección y oportunidad , Deighton: Bell and Co., Proposición XXII, p. 93, citado por Pippenger (2010)
12. Comtet, Louis (1974), Combinatoria avanzada: el arte de las expansiones finitas e infinitas (PDF) (edición revisada y ampliada), D. Reidel Publishing Co., p. 228, archivado desde el original (PDF) el 4 de julio de 2014 , consultado el 12 de marzo de 2013
13. , A.; Mays, ME (2005), "Un estudio de las funciones de conteo de factorización", Revista Internacional de Teoría de Números , 1 (4): 563–581, doi :10.1142/S1793042105000315, MR  2196796
14. Good, IJ (1975), "El número de ordenamientos de n candidatos cuando se permiten empates" (PDF) , Fibonacci Quarterly , 13 : 11–18, MR  0376367
15. Sprugnoli, Renzo (1994), "Matrices de Riordan y sumas combinatorias", Matemáticas discretas , 132 (1–3): 267–290, doi : 10.1016/0012-365X(92)00570-H , SEÑOR  1297386
16. Liu, Lily L.; Wang, Yi (2007), "Sobre la convexidad logarítmica de secuencias combinatorias", Avances en Matemáticas Aplicadas , 39 (4): 453–476, arXiv : math/0602672 , doi :10.1016/j.aam.2006.11.002, Señor  2356431
17. Para la interpretación de como el número de caras dimensionales de un asociaedro dimensional, consulte Sloane, N. J. A. (ed.), "Sequence A019538", The On-Line Encyclopedia of Integer Sequences , Fundación OEIS ${\displaystyle k!\{{\scriptstyle {n \atop k}}\}}$ ${\displaystyle k}$ ${\displaystyle n}$, que da el orden fila por fila de un triángulo infinito de números con el enésimo número en la enésima fila del triángulo. ${\displaystyle k!\{{\scriptstyle {n \atop k}}\}}$ ${\displaystyle k}$ ${\displaystyle n}$
18. Velleman, Daniel J.; Call, Gregory S. (1995), "Permutaciones y cerraduras de combinación", Mathematics Magazine , 68 (4): 243–253, doi :10.2307/2690567, JSTOR  2690567, MR  1363707
19. Getu, Seyoum; Shapiro, Luis W .; Woan, Wen Jin; Woodson, Leon C. (1992), "Cómo adivinar una función generadora", Revista SIAM de Matemáticas Discretas , 5 (4): 497–499, doi :10.1137/0405040, MR  1186818
20. Lewis, Barry (2010), "Revisitando la matriz de Pascal", American Mathematical Monthly , 117 (1): 50–66, doi :10.4169/000298910X474989, JSTOR  10.4169/000298910x474989, MR  2599467, S2CID  5
21. Bailey, Ralph W. (1998), "El número de ordenamientos débiles de un conjunto finito", Elección y bienestar social , 15 (4): 559–562, doi :10.1007/s003550050123, MR  1647055, S2CID  120845059
22. Barthélémy, J.-P. (1980), "Un equivalente asintótico para el número total de pedidos anticipados en un conjunto finito", Matemáticas discretas , 29 (3): 311–313, doi :10.1016/0012-365X(80)90159-4, MR  0560774
23. Berndt, Bruce C. (1985), Cuadernos de Ramanujan. Parte I , Springer-Verlag, Nueva York, p. 42, doi :10.1007/978-1-4612-1088-7, ISBN 0-387-96110-0, SEÑOR  0781125
24. Kauffman, Dolores H. (1963), "Nota sobre acuerdos preferenciales", The American Mathematical Monthly , 70 (1): 62, doi :10.2307/2312790, JSTOR  2312790, MR  0144827.
25. Poonen, Bjorn (1988), "Periodicidad de una secuencia combinatoria", Fibonacci Quarterly , 26 (1): 70–76, SEÑOR  0931425
26. Diagana, Toka ; Maïga, Hamadoun (2017), "Algunas identidades y congruencias nuevas para los números de Fubini", Journal of Number Theory , 173 : 547–569, doi : 10.1016/j.jnt.2016.09.032 , MR  3581932
27. Harris, Juan; Hirst, Jeffry L.; Mossinghoff, Michael J. (2008), Combinatoria y teoría de grafos, Textos de pregrado en matemáticas (2ª ed.), Springer, pág. 132, ISBN 9780387797106
28. Ellison, T. Mark; Klein, Ewan (2001), "Reseña: Lo mejor de todas las palabras posibles (revisión de la teoría de la optimidad: una descripción general , Archangeli, Diana y Langendoen, D. Terence, eds., Blackwell, 1997)", Journal of Linguistics , 37 ( 1): 127–143, JSTOR  4176645
29. Yu, Yang; Wang, Junwei; Hacer; Sun, Wei (agosto de 2018), " Equilibrio del sistema Seru : definición, formulación y solución exacta", Computación e ingeniería industrial , 122 : 318–325, doi :10.1016/j.cie.2018.05.048
30. Zhu, Yi; Filipov, Evgueni T. (octubre de 2019), "Un enfoque numérico eficiente para simular el contacto en ensamblajes de origami", Actas de la Royal Society A: Ciencias matemáticas, físicas y de ingeniería , 475 (2230): 20190366, doi :10.1098/rspa. 2019.0366, PMC 6834023 
31. Knopfmacher, A.; Mays, ME (2005), "Un estudio de las funciones de conteo de factorización", Revista Internacional de Teoría de Números , 1 (4): 563–581, doi :10.1142/S1793042105000315, MR  2196796
32. Meyles, Lucas Chaves; Harris, Pamela E .; Jordan, Richter; Kirby, Gordon Rojas; Sehayek, Sam; Spingarn, Ethan (2023), Funciones de estacionamiento de intervalo unitario y el permutoedro , arXiv : 2305.15554; Meyles et al atribuyen la conexión entre las funciones de estacionamiento y los números de Bell ordenados a una tesis de licenciatura de 2021 realizada por Kimberly P. Hadaway de Williams College.
33. Kemeny, John G. (1956), "Dos medidas de complejidad", The Journal of Philosophy , 52 (24): 722–733, doi :10.2307/2022697, JSTOR  2022697
34. Novelli, J.-C.; Thibon, J.-Y. (Junio ​​de 2006), "Realizaciones polinómicas de algunas juiciogebras" (PDF) , Actas de la 18.ª Conferencia Internacional sobre Series de Potencias Formales y Combinatoria Algebraica (FPSAC/SFCA), San Diego, California, 2006 , págs. 243–254, arXiv : matemáticas/0605061
35. Féray, Valentin (2015), "Inclusión-exclusión cíclica", Revista SIAM de Matemáticas Discretas , 29 (4): 2284–2311, arXiv : 1410.1772 , doi :10.1137/140991364, MR  3427040
36. Chhabra, Shalendra; Yerazunis, William S.; Siefkes, Christian (2004), "Filtrado de spam utilizando un modelo de campo aleatorio de Markov con esquemas de ponderación variable" (PDF) , Actas de la 4ª Conferencia Internacional IEEE sobre Minería de Datos (ICDM 2004), 1 a 4 de noviembre de 2004, Brighton, Reino Unido , IEEE Computer Society, págs. 347–350, doi :10.1109/ICDM.2004.10031