números de encuentros

En matemáticas combinatorias , los números rencontres son una matriz triangular de números enteros que enumeran permutaciones del conjunto {1,...,  n  } con números específicos de puntos fijos : en otras palabras, trastornos parciales . ( Rencontre significa encuentro en francés . Según algunas versiones, el problema lleva el nombre de un juego de solitario ). Para n  ≥ 0 y 0 ≤ k  ≤  n , el número de rencontres 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 sólo dos están destinadas a recibir el regalo correcto, hay D _{7, 2}  = 924 maneras en que esto podría suceder. Otro ejemplo citado frecuentemente es el de una escuela de baile con 7 parejas, donde, después de la pausa para el té, se les dice a los participantes que busquen al azar una pareja para continuar, luego una vez más hay D _{7, 2}  = 924 posibilidades de que 2 parejas anteriores se reencuentren. por casualidad.

Valores numéricos

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

Fórmulas

Los números en la columna k  = 0 enumeran trastornos . 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 negativo . 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 hacia abajo para n impar . Para n  ≥ 1, esto da el número entero más cercano.

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

${\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 los trastornos: elegir los k puntos fijos entre n ; luego elija el trastorno 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, se puede derivar 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{ 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 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 en la n- ésima fila 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).

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 .

Limitar la distribución de probabilidad

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

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

Esta es solo 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.

Ver también

• Problema de Oberwolfach , un problema matemático diferente que implica 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 establecidas ", 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 .