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.​ 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):

k n	0	1	2	3	4	5	6	7	8
0	1
1	0	1
2	1	0	1
3	2	3	0	1
4	9	8	6	0	1
5	44	45	20	10	0	1
6	265	264	135	40	15	0	1
7	1854	1855	924	315	70	21	0	1
8	14833	14832	7420	2464	630	112	28	0	1

Ordenado por el número de elementos movidos
La forma habitual de mostrar los números de encuentros es en columnas correspondientes al número de puntos fijos $k$. Pero también se pueden ordenar en columnas correspondientes al número de elementos movidos $i=n-k$ (sucesión A098825 en OEIS). Cada entrada es el producto de un coeficiente binomial y un subfactorial. En este orden cada columna corresponde a un subfactorial: $~~~T(n,i)={\binom {n}{i}}~\cdot ~!i$
i n  0 1 2 3 4 5 6 7 8 0 1 1 1 0 2 1 0 1 3 1 0 3 2 4 1 0 6 8 9 5 1 0 10 20 45 44 6 1 0 15 40 135 264 265 7 1 0 21 70 315 924 1855 1854 8 1 0 28 112 630 2464 7420 14832 14833	i n  0 1 2 3 4 5 6 7 8 0 1⋅1 1 1⋅1 1⋅0 2 1⋅1 2⋅0 1⋅1 3 1⋅1 3⋅0 3⋅1 1⋅2 4 1⋅1 4⋅0 6⋅1 4⋅2 1⋅9 5 1⋅1 5⋅0 10⋅1 10⋅2 5⋅9 1⋅44 6 1⋅1 6⋅0 15⋅1 20⋅2 15⋅9 6⋅44 1⋅265 7 1⋅1 7⋅0 21⋅1 35⋅2 35⋅9 21⋅44 7⋅265 1⋅1854 8 1⋅1 8⋅0 28⋅1 56⋅2 70⋅9 56⋅44 28⋅265 8⋅1854 1⋅14833

Fórmulas

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

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

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

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

para n no negativa. Resulta que

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

$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:

$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

$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

${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.​ 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

$\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

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. 

• Datos: Q1293666