Número de campana ordenado

Número de ordenamientos 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 números de Fubini cuentan los ordenamientos débiles en un conjunto de elementos. Los ordenamientos débiles organizan sus elementos en una secuencia que permite empates , como los que podrían surgir como resultado de una carrera de caballos . ^{[1] [2]} ${\displaystyle n}$

Los números de Bell ordenados fueron estudiados en el siglo XIX por Arthur Cayley y William Allen Whitworth . Su nombre se debe a 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 dotadas de un orden total . Su nombre alternativo, los 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 llamarse por esos nombres, por ejemplo, como los números de arreglos preferenciales ^[3] o los números de órdenes débiles generalizados asimétricos. ^[4]

Estos números pueden calcularse mediante una fórmula de suma que involucra coeficientes binomiales o mediante el uso de una relación de recurrencia . También cuentan los objetos combinatorios que tienen una correspondencia biyectiva con los ordenamientos débiles, como las particiones multiplicativas ordenadas de un número sin 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 empates . Esta posibilidad describe varios escenarios del mundo real, incluyendo ciertas competiciones 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 empatados, y estas clases de equivalencia pueden entonces ordenarse linealmente mediante el ordenamiento débil. Por lo tanto, un ordenamiento débil puede describirse como una partición ordenada , una partición de sus elementos y un orden total en 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 la 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 , que están todos empatados entre sí.

El número de Bell ordenado enésimo, denotado aquí , da el número de ordenamientos débiles distintos en los elementos. ^[8] Por ejemplo, hay tres ordenamientos débiles en los dos elementos a y b : pueden ordenarse con a antes de b , con b antes de a o con ambos empatados. La figura muestra los 13 ordenamientos débiles en 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 la OEIS ).

Cuando los elementos a ordenar no están etiquetados (sólo importa el número de elementos en cada conjunto empatado, no sus identidades) lo que queda es una composición o partición ordenada de enteros, una representación de como una suma ordenada de 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 enteros de 1 a . ^[4] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 2^{n-1}}$ ${\displaystyle n-1}$

Historia

13 plátanos con hojas ordenadas y recorridos de raíz a hoja 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 demuestra que los árboles de este tipo se cuentan por los números de Bell ordenados.

Los números de Bell ordenados 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 un árbol de este tipo, 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 & Fraenkel (1984) llaman a los árboles de este tipo "árboles de Cayley", y a las secuencias que pueden usarse para etiquetar sus huecos (secuencias de números enteros positivos que incluyen al menos una copia de cada número entero positivo entre uno y el valor máximo en la secuencia) llaman "permutaciones de Cayley". ^[10] ${\displaystyle n+1}$ ${\displaystyle i}$ ${\displaystyle i+1}$ ${\displaystyle n}$ ${\displaystyle n}$

Pippenger (2010) rastrea el problema de contar ordenamientos débiles, que tienen la misma secuencia como su 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 reorganizar el orden de 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 , llamados así por Eric Temple Bell , cuentan las particiones de un conjunto , y los ordenamientos débiles que se cuentan por los números de Bell ordenados pueden interpretarse como una partición junto con un orden total en 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 forma temprana de la Enciclopedia en línea de secuencias enteras (OEIS). Este se convirtió en uno de los primeros usos exitosos de la 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, uno puede contar los ordenamientos débiles contando los ordenamientos y particiones totales, y combinando los resultados apropiadamente. Los números de Stirling del segundo tipo , denotados , cuentan las particiones de un conjunto de elementos en subconjuntos no vacíos. Un ordenamiento débil puede obtenerse de tal partición eligiendo uno de los ordenamientos totales de sus subconjuntos. Por lo tanto, los números de Bell ordenados pueden contarse sumando los posibles números 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 una fórmula de suma : ^{[14] [15]} Por resultados generales sobre sumas que involucran números de Stirling, se deduce que los números de Bell ordenados son log-convexos , lo que significa que obedecen la desigualdad para todos los . ^[16] ${\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 de cuatro dimensiones 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 th contando las características de dimensión . Un permutoedro es un politopo convexo , la envoltura convexa de puntos cuyos vectores de coordenadas son las permutaciones de los números de 1 a . Estos vectores están definidos en un espacio de dimensión , pero ellos y su envoltura convexa se encuentran en un subespacio afín -dimensional . Por ejemplo, el permutoedro tridimensional es el octaedro truncado , la envoltura 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 en una suma de coeficientes binomiales , la fórmula para los números de Bell ordenados puede expandirse en una suma doble. Los números de Bell ordenados también pueden darse mediante 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 los pares de elementos consecutivos están en orden creciente: ^[18] donde es el polinomio euleriano . Una forma de explicar esta fórmula de suma implica una aplicación de ordenaciones débiles en los números de 1 a a permutaciones , obtenidas al ordenar cada conjunto empatado en orden numérico. Bajo esta aplicación, cada permutación con pares crecientes consecutivos proviene de ordenaciones débiles, que se distinguen entre sí por el subconjunto de los pares crecientes consecutivos que están empatados en la ordenación 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

Al igual que 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 al hecho de que los números de Bell ordenados son los números en la primera columna de la matriz infinita . Aquí está la matriz identidad y es una forma de matriz infinita del triángulo de Pascal . Cada fila de comienza con los números en la misma fila del triángulo de Pascal y luego continúa con una secuencia infinita de ceros que se repite. ^[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}$

Con base 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 para los números de Bell ordenados, obtenida al usar solo el término para en esta suma y descartar los términos restantes: ^{[21] [3] [5] [15] [22]} donde . Por lo tanto, los números de Bell ordenados son mayores que los factoriales por un factor exponencial. Aquí, como en la aproximación de Stirling al factorial, el 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 grande. 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, tomando da 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 ordenamiento 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 ordenamiento, junto con un ordenamiento débil más pequeño en los elementos restantes. Hay elecciones del primer conjunto y elecciones del ordenamiento débil en el resto de los elementos. Al multiplicar estos dos factores y luego sumar las elecciones 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 ordenamiento débil en cero elementos). Con base en esta recurrencia, se puede demostrar que estos números obedecen a ciertos patrones periódicos en aritmética modular : para , suficientemente grande , ${\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 prima . ^{[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 módulo que son primos relativos a . ^[4] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

Aplicaciones

Enumeración combinatoria

Como ya se ha mencionado, los números de Bell ordenados cuentan ordenaciones débiles, caras de permutoedros , árboles de Cayley, permutaciones de Cayley y fórmulas equivalentes en el teorema de Fubini. Las ordenaciones débiles a su vez tienen muchas otras aplicaciones. Por ejemplo, en las carreras de caballos , los finales de carrera han eliminado la mayoría, pero no todos, de los empates, llamados en este contexto empates , y el resultado de una carrera que puede contener empates (incluidos todos los caballos, no solo los tres primeros en llegar a la meta) puede describirse utilizando una ordenación débil. Por esta razón, los números de Bell ordenados 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 ordenaciones 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 pueden formularse utilizando ordenamientos débiles, con soluciones contadas utilizando números de Bell ordenados. Velleman y Call (1995) consideran cerraduras de combinación con un teclado numérico, en el 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 un sistema de este tipo está dado por los números de Bell ordenados. ^[18] En seru , una técnica japonesa para equilibrar líneas de montaje , los trabajadores con formació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 dado de trabajadores, teniendo en cuenta las opciones de cuántas etapas utilizar y cómo asignar trabajadores a cada etapa, es un número de Bell ordenado. ^[29] Como otro ejemplo, en la simulación por ordenador del origami , los números de Bell ordenados dan el número de ordenamientos en los que se pueden doblar los pliegues de un patrón de pliegues , lo que permite doblar conjuntos de pliegues simultáneamente. ^[30]

En teoría de números , una partición multiplicativa ordenada de un 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 entero es libre de cuadrados cuando es un producto de números primos distintos ; 30 es libre de 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é término de la partición. Por lo tanto, el número de particiones multiplicativas ordenadas está dado por . Por otra parte, 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 . Por lo tanto, en este caso, hay particiones multiplicativas ordenadas. Los números que no son ni potencias libres de cuadrados ni primos tienen un número de particiones multiplicativas ordenadas que (en función del número de factores primos) está 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 hasta la 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 automóviles llega a una calle con lugares para estacionar. Cada automóvil tiene un lugar de estacionamiento preferido, dado por su valor en la secuencia. Cuando un automóvil llega a la calle, estaciona 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 solo si cada automóvil puede encontrar un lugar para estacionar en o después de su lugar preferido. El número de funciones de estacionamiento de longitud es exactamente . Para una clase restringida de funciones de estacionamiento, en la que cada automóvil estaciona en su lugar preferido o en el siguiente lugar, el número de funciones de estacionamiento está dado por los números de Bell 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á empatado con el automóvil en su lugar preferido. Las permutaciones , contadas por los factoriales, son funciones de estacionamiento para las cuales cada automóvil estaciona en su lugar preferido. ^[32] Esta aplicación también proporciona una prueba combinatoria para límites superiores e inferiores en los números de Bell ordenados de una 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, que se muestran aquí por sus intersecciones con una esfera unitaria . Los planos de reflexión de cortan la esfera en círculos máximos . 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 asociado con un grupo de Coxeter de tipo . Aquí, un grupo de Coxeter puede considerarse 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 líneas que se encuentran en el origen en á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 las relaciones n -arias , enunciados matemáticos que pueden ser verdaderos para algunas opciones 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 se pueden 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 intercambiando los argumentos y la relación unaria obtenida repitiendo un argumento. (Repetir el 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 optimalidad en lingüística . En esta teoría, las gramáticas para lenguas 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 está limitado 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 los vínculos entre restricciones, de modo que la clasificación de las restricciones se convierte 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 mucho más rico de gramáticas. ^[28]

Otro

Si se lanza una moneda justa (con la misma probabilidad de que salga cara o cruz) repetidamente 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 de dimensión . Truncando esta serie a un número acotado de términos y luego aplicando el resultado para valores ilimitados de se 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 utilizando peso para una secuencia de palabras, donde se obtiene de la ecuación de recurrencia con caso 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 solo se consideran secuencias no vacías) y agregar uno por separado de la suma (para hacer 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, American Mathematical Society, pág. 4, ISBN 9780821886311Debido a esta aplicación, De Koninck llama a estos números "números de caballo", pero este nombre no parece tener un uso muy extendido.
2. Mendelson, Elliott (1982), "Carreras con empates", Mathematics Magazine , 55 (3): 170–175, doi :10.2307/2690085, JSTOR  2690085, MR  0653432
3. Gross, OA (1962), "Arreglos preferenciales", The American Mathematical Monthly , 69 (1): 4–8, doi :10.2307/2312725, JSTOR  2312725, MR  0130837
4. Sloane, N. J. A. (ed.), "Secuencia A000670", La enciclopedia en línea de secuencias de números enteros , OEIS Foundation
5. Sklar, Abe (1952), "Sobre la factorización de números enteros sin cuadrados", Actas de la American Mathematical Society , 3 (5): 701–705, doi : 10.1090/S0002-9939-1952-0050620-1 , JSTOR  2032169, MR  0050620
6. Ziegler, Günter M. (1995), Lecciones 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 discriminación de utilidad", Econometrica , 24 (2): 178–191, doi :10.2307/1905751, JSTOR  1905751, MR  0078632
8. Pippenger, Nicholas (2010), "El hipercubo de resistencias, expansiones asintóticas y disposiciones preferenciales", Mathematics Magazine , 83 (5): 331–346, arXiv : 0904.1757 , doi :10.4169/002557010x529752, JSTOR  10.4169/002557010X529752, MR  2762645, S2CID  17260512
9. Cayley, A. (1859), "Sobre las formas analíticas llamadas árboles, segunda parte", Philosophical Magazine , Serie IV, 18 (121): 374–378, doi :10.1017/CBO9780511703706.026, ISBN 9781108004961, en Obras completas de Arthur Cayley, pág. 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, MR  0732206
11. Whitworth, WA (1886), Elección y azar , Deighton: Bell and Co., Proposición XXII, pág. 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ág. 228, archivado desde el original (PDF) el 4 de julio de 2014 , consultado el 12 de marzo de 2013
13. Knopfmacher, A.; Mays, ME (2005), "Un estudio de las funciones de conteo de factorización", International Journal of Number Theory , 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 los empates" (PDF) , Fibonacci Quarterly , 13 : 11–18, doi :10.1080/00150517.1975.12430678, MR  0376367
15. Sprugnoli, Renzo (1994), "Matrices de Riordan y sumas combinatorias", Discrete Mathematics , 132 (1–3): 267–290, doi : 10.1016/0012-365X(92)00570-H , MR  1297386
16. Liu, Lily L.; Wang, Yi (2007), "Sobre la convexidad logarítmica de secuencias combinatorias", Advances in Applied Mathematics , 39 (4): 453–476, arXiv : math/0602672 , doi :10.1016/j.aam.2006.11.002, MR  2356431
17. Para la interpretación de como el número de caras -dimensionales de un asociaedro -dimensional, véase Sloane, N. J. A. (ed.), "Sequence A019538", The On-Line Encyclopedia of Integer Sequences , OEIS Foundation ${\displaystyle k!\{{\scriptstyle {n \atop k}}\}}$ ${\displaystyle k}$ ${\displaystyle n}$, que da el ordenamiento fila por fila de un triángulo infinito de números con como el número n en la fila n 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, Louis W .; Woan, Wen Jin; Woodson, Leon C. (1992), "Cómo adivinar una función generadora", SIAM Journal on Discrete Mathematics , 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  207520945
21. Bailey, Ralph W. (1998), "El número de ordenamientos débiles de un conjunto finito", Social Choice and Welfare , 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 de preórdenes totales en un conjunto finito", Discrete Mathematics , 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ág. 42, doi :10.1007/978-1-4612-1088-7, ISBN 0-387-96110-0, Sr.  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, doi :10.1080/00150517.1988.12429663, MR  0931425
26. Diagana, Toka ; Maïga, Hamadoun (2017), "Algunas nuevas identidades y congruencias 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, John; 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), "Revisión: La mejor de todas las palabras posibles (revisión de Optimality Theory: An Overview , 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 e ingeniería , 475 (2230): 20190366, Bibcode :2019RSPSA.47590366Z, doi :10.1098/rspa.2019.0366, PMC 6834023 , PMID  31736647 
31. Knopfmacher, A.; Mays, ME (2005), "Un estudio de las funciones de conteo de factorización", International Journal of Number Theory , 1 (4): 563–581, doi :10.1142/S1793042105000315, MR  2196796
32. Meyles, Lucas Chaves; Harris, Pamela E .; Jordaan, Richter; Kirby, Gordon Rojas; Sehayek, Sam; Spingarn, Ethan (2023), Funciones de estacionamiento de intervalo unitario y el permutoedro , arXiv : 2305.15554Meyles 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 de 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 polinomiales de algunas trialgebras" (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 : math/0605061
35. Féray, Valentin (2015), "Inclusión-exclusión cíclica", SIAM Journal on Discrete Mathematics , 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-4 de noviembre de 2004, Brighton, Reino Unido , IEEE Computer Society, págs. 347-350, doi :10.1109/ICDM.2004.10031, ISBN 0-7695-2142-8