El problema de las cartas extraviadas es un clásico del cálculo de probabilidades. Se ha planteado con el reparto de sombreros entre varias personas o con cartas distintas escritas para introducir en sus sobres correspondientes todos ellos con direcciones de personas diferentes.
Pensemos en problemas de este tipo; Si seis personas que dejan su sombrero en una guardarropía y luego los recogen aleatoriamente, ¿De cuantas formas es posible hacer el reparto? ¿De cuántas formas es posible cada persona recoja su sombrero? ¿De cuantas formas se puede hacer el reparto para que sólo Juan se lleve su sombrero? ¿De cuántas formas se puede hacer el reparto para que ninguno se lleve su sombrero?
Las tres primeras preguntas son de fácil respuesta, serían respectivamente: 6! =720, 1 y 5! =120. Pero la cuarta tiene algo más de dificultad y despertó el interés de muchos matemáticos desde el siglo XVIII. El problema que plantea es conocido en la literatura matemática como el problema de Cartas Extraviadas y fue propuesto por primera vez, de forma general, por el matemático francés P. R. de Montmort (1678-1719) en su libro Ensayo de análisis de los juegos de azar (1708).
La formulación del problema fue la siguiente:
Una persona ha escrito n cartas a n personas diferentes y escribió sus direcciones en n sobres. Si introdujo las cartas en los sobres al azar ¿De cuántas formas es posible que ninguna de las cartas esté dentro de su sobre correspondiente?
Este problema es complicado en el caso general, ya que implica cuestiones de recursividad de o la utilización del llamado principio de inclusión-exclusión de la unión de conjuntos. De Montmort estudió el problema con su amigo el matemático suizo N. Bernoulli (1687-1759) y en la segunda edición de su libro en 1713, publicó la solución del problema de las Cartas Extraviadas realizada por Bernoulli, que él llamó problema del reencuentro. El problema fue un tópico de la Combinatoria y del cálculo de Probabilidades: L. Euler (1707-1783) le dedicó el artículo Cálculo de probabilidades en el juego del reencuentro (1743), A. de Moivre (1667-1754) lo expuso en The Doctrine of Chances (1756) y P. S. Laplace (1749-1827) lo recogió en la obra cumbre de probabilidades de toda la centuria Teoría analitica de probabilidades (1812).
Una forma habitual de plantear la cuestión en los libros de Aritmética Combinatoria es la siguiente:
Determinar todas las permutaciones (reordenaciones) de n elementos de manera que ningún elemento ocupe su posición inicial.
Comenzaremos llamando desbarajuste a una reordenación de {1, 2, 3, … , n} en la que ningún elemento ocupa su posición inicial y lo designaremos con D y con D(n) al número de desbarajustes de que se pueden hacer en {1, 2, 3, … , n}.
Ejemplo 1: Si n =3, y la posición inicial es {1, 2, 3}, entonces {2,3,1} es un desbarajuste D(3), porque el 2 está en primer lugar, el 3 en segundo lugar y el uno en tercero, mientras que {3, 2, 1}no es desbarajuste, porque el 2 permanece en segunda posición.
Ejemplo 2:
- Si n = 1 ¿Cuántos desbarajustes son posibles?: D (1) = 0,
Ya que no existen desbarajustes de {1}
- Si n = 2 ¿Cuántos desbarajustes son posibles?: D (2) = 1
Ya que de las dos permutaciones posibles de {1,2}: ({1, 2}, {2, 1}) sólo el {2, 1} es desbarajuste.
- Si n = 3 ¿Cuántos desbarajustes son posibles?: D (3) = 2
Ya que de las seis permutaciones posibles de {1,2,3} sólo {2,3,1} y {3,1,2} son desbarajustes
- Si n = 4 ¿Cuántos desbarajustes son posibles?: D(4) = 9
Ya que de las 24 permutaciones posibles de {1, 2, 3 ,4}, sólo son desbarajustes:
{2,1,4,3}, {2,3,4,1},{2,4,1,3},{3,1,4,2}, {3,4,1,2},{3,4,2,1},{4,1,3,2},{4,3,1,2}, {4,3,2,1}
Como se puede ver el número de desbarajustes crece rápidamente con el valor de n y cada vez es más difícil determinar el número de los mismos. Sería interesante disponer de una fórmula para contarlos a partir de los anteriores desbarajustes de permutaciones de menos elementos. Es decir, contar, por ejemplo, los desbarajustes D (4) en función de D (3) y D (2) o los de D (5) en función de D (4) y D (3).
PRIMERO: Determinaremos D(4) en {1,2,3,4} en función de D (3) y D (2)
En uno cualquiera de los D(4) desbarajustes de {1,2,3,4} el 1 tiene tres posibilidades de desplazarse (a la posición del 2, a la del 3 o a la del 4). Supongamos que 1 ® 2. En esta situación consideraremos dos casos.
CASO 1: 1 pase a 2 y que 2 pase a 1. En la trasformación global {1,2,3,4}pase a{2,1,3,4}.
La permutación de 1 y 2 uno por los desbarajustes de {3,4} D(2). Como el 1 puede desplazarse a las posiciones segunda tercera o cuarta, el Caso 1 aporta 3·D(2) desbarajustes a D(4)
CASO 2: 1 pase a 2 y que 2 no vaya a la posición 1. En la trasformación global (el 1 va a la posición 2): {1,2,3,4}®{2,1,3,4}, la trasformación parcial de los elementos restantes {2,3,4} tiene las exigencias que al 2 no ocupe el lugar 1, que el 3 no ocupe el lugar 3 y ni el 4 el cuatro 4. Como el 1 puede ocupar inicialmente (para poder ser desbarajuste) las posiciones segunda tercera o cuarta; el Caso 2 aporta 3· D(3) desbarajustes
Por lo tanto: D(4) = 3·D(3) + 3·D(2) = 3(D(3) + D(2)), es decir:
D(4) =3·(2+1) = 9
Determinaremos caso {1,2,3,4,5}, calculando D (5) en función de D (4) y D (3)
Con un razonamiento idéntico al anterior, en uno cualquiera de los D (5) desbarajustes de {1,2,3,4,5} el 1 tiene cuatro posibilidades de desplazarse (a la posición del 2, a la del 3, a la del 4 o a la del 5). Supongamos que 1 2. En esta situación consideraremos dos casos.
CASO 1: 1 pase a 2 y que 2 pase a 1. En la trasformación global {1,2,3,4,5}®{2,1,3,4,5}.
La permutación de 1 y 2 uno por los desbarajustes de {3,4,5}, D (3). Como el 1 puede desplazarse a las posiciones segunda tercera o cuarta o quinta el Caso 1 aporta 4·D(3) desbarajustes a D(5)
CASO 2: 1 pase a 2 y que 2 no vaya a la posición 1. En la trasformación global {1,2,3,4,5}®{2,1,3,4,5}, la trasformación parcial de los elementos restantes {2,3,4,5} tiene las exigencias que el 2 no ocupe el lugar 1, que el 3 no ocupe el lugar 3, ni el 4 no ocupe el lugar el 4, ni el 5 el lugar 5. Como el 1 puede ocupar iniciamente (para poder ser desbarajuste) las posiciones segunda, tercera , cuarta o quinta este Caso 2 aporta 4· D(4). Por lo tanto:
D(5) = 4·D(4) + 4·D(3) = 4(D(4) + D(3))
D(5) = 4·(9+2) = 44
Aunque en otro apartado del blog probaremos la fórmula de recurrencia genetal :
D(n) = (n – 1)·[D(n – 2) + D(n – 1)], la aplicaremos, y obtenemos
D(4) = 3·(2+1) = 9
D(5) = 4·(9+2) = 44
D(6) = 5·(44+9) = 265
D(7) = 6·(265+44) = 1854
D(8) = 7·(1854+ 265) = 14833
