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

$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.[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

\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

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.
Jim Pitman, "Some Probabilistic Aspects of Set Partitions", American Mathematical Monthly, volume 104, number 3, March 1997, pages 201–209.

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

Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.

[1] 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.

[2] Jim Pitman, "Some Probabilistic Aspects of Set Partitions", American Mathematical Monthly, volume 104, number 3, March 1997, pages 201–209.