En matemática combinatoria , los números de rencontres son una matriz triangular de enteros que enumeran permutaciones del conjunto {1, ..., n } con números específicos de puntos fijos : en otras palabras, desarreglos parciales . ( Rencontre es francés para el encuentro . Según algunas versiones, el problema es el nombre de un solitario juego.) Para n ≥ 0 y 0 ≤ k ≤ n , el número Rencontres D n , kes 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 destinados a obtener el presente correcto, hay D 7, 2 = 924 formas en las que esto podría suceder. Otro ejemplo frecuentemente citado 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 un compañero 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 la OEIS ):
k norte | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
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 |
Fórmulas
Los números de la columna k = 0 enumeran los trastornos . Por lo tanto
para n no negativo . Resulta que
donde la relación se redondea hacia arriba para n pares y hacia abajo para n impares . Para n ≥ 1, esto da el número entero más cercano.
De manera más general, para cualquier , tenemos
La demostración es fácil después de saber cómo enumerar los trastornos: elija los k puntos fijos de n ; luego elija la alteración 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:
Esto implica inmediatamente que
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 de la n- ésima fila por n !, Se obtiene la distribución de probabilidad del número de puntos fijos de una permutación aleatoria distribuida uniformemente de {1, ..., n }. La probabilidad de que el número de puntos fijos sea k es
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
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 el valor esperado 1.
Referencias
- ^ 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" . MathWorld .