Pongamos en una lista los elementos de S en su orden natural (de hecho, en cualquier orden). El primer elemento se puede aparear con cualquiera de los 2n-1 restantes. Tachamos ese par de la lista, y tomamos para aparear el siguiente elemento no tachado. Éste se puede aparear con cualquiera de los 2n-3 restantes. Continuando de esta manera, eventualmente (de hecho después de n-1 apareos) se llega a únicamente dos elementos no tachados, los cuales se pueden aparear de una única manera. Por el principio de multiplicación, hay (2n-1)(2n-3)…5.3.1 formas de particionar S en subconjuntos de tamaño 2.
Comentario
Vamos a resolver enseguida un ejemplo, para ilustrar el método y para que el lector se dé una idea del origen del argumento anterior. Si n=3, tenemos un conjunto de 6 elementos y, según la fórmula obtenida arriba, el número de particiones en subconjuntos de dos elementos debe ser 15. Veamos la lista:
{12 34 56} {12 35 46} {12 36 45}
{13 24 56} {13 25 46} {13 26 45}
{14 23 56} {14 25 36} {14 26 35}
{15 23 46} {15 24 36} {15 26 34}
{16 23 45} {16 24 35} {16 25 34}
Notemos que la lista se obtiene con el procedimiento de tachado. Consideremos cómo se obtiene la tercera fila:
El 1 se aparea con el 4 (una de entre las cinco posibilidades de aparear el 1); entonces se tacha el 1 y el 4 y quedan los elementos 2 3 5 6. De éstos, elegimos el primero no tachado para aparear (que es el 2), el cual se puede aparear con el 3, con el 5 o con el 6. Etc.
Notemos también que este procedimiento da lugar a una recurrencia. Si denotamos con P_n al número de particiones de un conjunto de 2n elementos en subconjuntos de tamaño 2, enotnces P_n=(2n-1)P_{n-1}. Esta recurrencia se puede explicar así. Escojo el 1 (el primer elemento) para aparear. Hay 2n-1 posibilidades de aparear el 1. Pero, alcontinuar con el apareo (en el siguiente paso del apareo), se tiene el problema de particionar un conjunto de 2(n-1), elementos. Es decir, hay P_{n-1} formas de terminarlo. Si ahora notamos que P_2=3, entonces P_3=3P_2=3(6)=15. Maravilloso ¿no es cierto?
