Problema de encuentros
# 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):

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

| in | 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 |
| in | 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.

