Números de encuentros

En combinatoria , los números de encuentro son una matriz triangular de números enteros que enumeran permutaciones del conjunto {1, ...,  n  } con un número específico de puntos fijos : en otras palabras, desarreglos parciales . ( Rencontre es la palabra francesa para encuentro . Según algunas versiones, el problema recibe su nombre de un juego de solitario ). Para n  ≥ 0 y 0 ≤ k  ≤  n , el número de encuentro D _{n ,  k} es el número de permutaciones de {1, ...,  n  } que tienen exactamente k puntos fijos.

Por ejemplo, si se dan siete regalos a siete personas diferentes, pero solo dos están destinadas a recibir el regalo correcto, hay D _{7, 2}  = 924 posibilidades de que esto suceda. 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 pide a los participantes que encuentren al azar una pareja para continuar, luego, una vez más, hay D _{7, 2}  = 924 posibilidades de que las 2 parejas anteriores se vuelvan a encontrar por casualidad.

Valores numéricos

Aquí está el comienzo de esta matriz (secuencia A008290 en la OEIS ):

Fórmulas

Los números en la  columna k = 0 enumeran los trastornos . Por lo tanto

${\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 negativo . Resulta que

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

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

De manera más general, para cualquier , tenemos ${\displaystyle k\geq 0}$

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

La prueba es fácil una vez que uno sabe cómo enumerar los desequilibrios: elija los k puntos fijos de n ; luego elija el desequilibrio de los otros n  −  k puntos.

Los números D _{n ,0} /( n !) son generados por la serie de potencias e ^{− z} /(1 − z ) ; en consecuencia, una fórmula explícita para D _{n ,  m} se puede derivar 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{ and }}\;\;{\frac {D_{n,m}}{n!}}\approx {\frac {e^{-1}}{m!}}}$

para n grande, m fijo.

Distribución de probabilidad

La suma de las entradas en cada fila de la tabla de " 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 en 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 desprende de la linealidad de la expectativa).

De manera más general, 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. ^[1] Para i  >  n , el i ésimo momento es menor que el de esa distribución de Poisson. Específicamente, 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 limitante

A medida que aumenta el tamaño del conjunto permutado, obtenemos

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

Esta es simplemente la probabilidad de que una variable aleatoria distribuida por Poisson con valor esperado 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 que involucra la disposición de los comensales en las mesas.
• Problème des ménages , un problema similar que implica trastornos parciales

Referencias

1. Jim Pitman, "Algunos aspectos probabilísticos de las particiones de conjuntos ", American Mathematical Monthly , volumen 104, número 3, marzo de 1997, páginas 201–209.

• Riordan, John , Introducción al análisis combinatorio , Nueva York, Wiley, 1958, páginas 57, 58 y 65.
• Weisstein, Eric W. "Trastornos parciales". MundoMatemático .