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 Dn, 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 D7, 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 D7, 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 .
Pero también se pueden ordenar en columnas correspondientes al número de elementos movidos (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:
|
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
![{\displaystyle D_{0,0}=1,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/343e742166b4f1dd2e235e9e50e39028e9bb22c3)
![{\displaystyle D_{1,0}=0,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7db901649cab97ac6c8a7f2ed7d213a44222e8b3)
![{\displaystyle D_{n+2,0}=(n+1)(D_{n+1,0}+D_{n,0})\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be750cf20b826aaa09b3ed23ec4dd1b324632fb4)
para n no negativa. Resulta que
![{\displaystyle D_{n,0}=\left\lceil {\frac {n!}{e}}\right\rfloor ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52746acd9deee4689782eb956e6dee518807100e)
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
, se tiene que
![{\displaystyle D_{n,k}={n \choose k}\cdot D_{n-k,0}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fa660a757a67bd37bcc14764f7349ed58ec2e1b)
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 Dn,0/(n!) son generados por series de potencias e−z/(1 − z). Análogamente,
se puede obtener una fórmula explícita para Dn, 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!}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf129f782941abf712ba9ee9cd8d8407fb37b28b)
Esto implica inmediatamente que
![{\displaystyle D_{n,m}={n \choose m}D_{n-m,0}\;\;{\mbox{y }}\;\;{\frac {D_{n,m}}{n!}}\approx {\frac {e^{-1}}{m!}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d43cd85dec2be28634a16952a5b0dcd73cc3fa16)
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
![{\displaystyle {D_{n,k} \over n!}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7519344ecd9c1d6145fc8e4e6cd59901820f243c)
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
![{\displaystyle \lim _{n\to \infty }{D_{n,k} \over n!}={e^{-1} \over k!}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1222847a75a81f98fdc1edaada66d25154af57f0)
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
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.