En combinatoria, los números de encuentros (o también, números de reencuentros) forman una matriz triangular de números enteros que enumeran las permutaciones del conjunto { 1, ..., n } con números especificados de puntos fijos, o en otras palabras, con un número determinado de restricciones parciales.Su denominación original, rencontre, en francés significa encuentro. Según algunos relatos, el problema lleva el nombre de un juego de naipes solitario. Para n ≥ 0 y 0 ≤ k ≤ n, el número de encuentros Dn, k es el número de permutaciones de { 1, ..., n } que tienen exactamente k puntos fijos.

Por ejemplo, si se dan al azar siete regalos a siete personas diferentes, pero se considera el caso de que solo dos van a recibir el regalo correcto, hay D7, 2 = 924 formas en que esto podría suceder. Otro ejemplo que se cita a menudo es el de una escuela de baile con 7 parejas, donde, después de la pausa del té, se les dice a los participantes que encuentren "al azar" una pareja para continuar, y una vez más, hay D7, 2 = 924 posibilidades de que 2 parejas anteriores se reencuentren por casualidad.

Valores numéricos

A continuación figura el comienzo de esta matriz :

0 1 2 3 4 5 6 7 8 01 101 2101 32301 498601 54445201001 6265264135401501 718541855924315702101 81483314832742024646301122801

Ordenado por el número de elementos movidosLa forma habitual de mostrar los números de encuentros es en columnas correspondientes al número de puntos fijos . Pero también se pueden ordenar en columnas correspondientes al número de elementos movidos . Cada entrada es el producto de un coeficiente binomial y un subfactorial. En este orden cada columna corresponde a un subfactorial: 0 1 2 3 4 5 6 78 01 110 2101 31032 410689 51010204544 6101540135264265 710217031592418551854 81028112630246474201483214833 0 1 2 3 4 5 6 78 01⋅1 11⋅11⋅0 21⋅12⋅01⋅1 31⋅13⋅03⋅11⋅2 41⋅14⋅06⋅14⋅21⋅9 51⋅15⋅010⋅110⋅25⋅91⋅44 61⋅16⋅015⋅120⋅215⋅96⋅441⋅265 71⋅17⋅021⋅135⋅235⋅921⋅447⋅2651⋅1854 81⋅18⋅028⋅156⋅270⋅956⋅4428⋅2658⋅18541⋅14833

Fórmulas

Los números en la columna k = 0 enumeran subfactoriales. De este modo

para n no negativa. Resulta que

donde la relación se redondea hacia arriba para n par y se redondea hacia abajo para n impar. Para n ≥ 1, esto da el entero más cercano.

Más generalmente, para cualquier , se tiene que

La demostración es fácil una vez que se sabe cómo enumerar las restricciones: elíjanse los k puntos fijos del conjunto de n puntos; y luego elíjase el ajuste de los otros n − k puntos restantes.

Los números son generados por series de potencias . Análogamente, se puede obtener una fórmula explícita para Dn, m de la siguiente manera:

Esto implica inmediatamente que

para n grande y m fijo.

Distribución de probabilidad

La suma de las entradas en cada fila de la tabla en "valores numéricos" es el número total de permutaciones de { 1, ..., n }, y por lo tanto es n!. Si se dividen todas las entradas de la fila n por n!, se obtiene la distribución de probabilidad del número de puntos fijos de una permutación aleatoria uniformemente distribuida de { 1, ...,  n }. La probabilidad de que el número de puntos fijos sea k es

Para n ≥ 1, el número esperado de puntos fijos es 1 (un hecho que se deriva de la linealidad de la expectativa).

Más generalmente, para i ≤ n, el i-ésimo momento de esta distribución de probabilidad es el i-ésimo momento de la distribución de Poisson con valor esperado 1.Jim Pitman, "Some Probabilistic Aspects of Set Partitions", American Mathematical Monthly, volume 104, number 3, March 1997, pages 201–209. Para i > n, el momento i es menor que el de esa distribución de Poisson. En concreto, para i ≤ n, el iésimo momento es el iésimo número de Bell, es decir, el número de particiones de un conjunto de tamaño i.

Distribución de probabilidad límite

A medida que crece el tamaño del conjunto permutado, se obtiene

Esta es solo la probabilidad de que una variable aleatoria con distribución de Poisson con un valor esperado de 1 sea igual a k. En otras palabras, a medida que n crece, la distribución de probabilidad del número de puntos fijos de una permutación aleatoria de un conjunto de tamaño n se aproxima a la distribución de Poisson con valor esperado 1.

Véase también Problema de Oberwolfach, un problema matemático diferente relacionado con la disposición de los comensales en las mesas Problema del menaje, un problema similar que implica restricciones parciales

Referencias

Bibliografía Riordan, John, An Introduction to Combinatorial Analysis, Nueva York, Wiley, 1958, páginas 57, 58 y 65.

Categoría:Permutaciones Categoría:Distribuciones discretas Categoría:Teoremas de punto fijo Categoría:Triángulos de números