Problema de encuentros

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.^[1]​ Para n ≥ 0 y 0 ≤ k ≤ n, el número de encuentros D_n, 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 D_7, 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 D_7, 2 = 924 posibilidades de que 2 parejas anteriores se reencuentren por casualidad.

Valores numéricos

A continuación figura el comienzo de esta matriz (sucesión A008290 en OEIS):

Fórmulas

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

${\displaystyle D_{0,0}=1,\!}$

${\displaystyle D_{1,0}=0,\!}$

${\displaystyle D_{n+2,0}=(n+1)(D_{n+1,0}+D_{n,0})\!}$

para n no negativa. Resulta que

${\displaystyle D_{n,0}=\left\lceil {\frac {n!}{e}}\right\rfloor ,}$

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 ${\displaystyle k\geq 0}$, se tiene que

${\displaystyle D_{n,k}={n \choose k}\cdot D_{n-k,0}.}$

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 D_n,0/(n!) son generados por series de potencias e^−z/(1 − z). Análogamente, se puede obtener una fórmula explícita para D_n, m de la siguiente manera:

${\displaystyle D_{n,m}={\frac {n!}{m!}}[z^{n-m}]{\frac {e^{-z}}{1-z}}={\frac {n!}{m!}}\sum _{k=0}^{n-m}{\frac {(-1)^{k}}{k!}}.}$

Esto implica inmediatamente que

${\displaystyle D_{n,m}={n \choose m}D_{n-m,0}\;\;{\mbox{y }}\;\;{\frac {D_{n,m}}{n!}}\approx {\frac {e^{-1}}{m!}}}$

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

${\displaystyle {D_{n,k} \over n!}.}$

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.^[2]​ 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

${\displaystyle \lim _{n\to \infty }{D_{n,k} \over n!}={e^{-1} \over k!}.}$

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.
• Weisstein, Eric W. «Partial Derangements». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.