Intro
Continuamos en este post las instancias de uso de las combinaciones de $ n $ objetos tomadas de $ r $ en $ r $. De nuevo, el lector debería focalizar el argumento combinatorio como una forma de adquirir esa lógica argumentativa de la combinatoria que se basa en experimentos imaginarios.
r-Sucesiones crecientes con elementos distintos de $\{1,2,\ldots,n\}$
¿Cuántas sucesiones crecientes se pueden formar con r elementos distintos de $\{1,2,\ldots,n\}$?
Solución (argumento biyectivo)
Cada sucesión creciente de $ r $ elementos distintos de $\{1,2,\ldots,n\}$ tiene asociado exactamente un r-subconjunto de $\{1,2,\ldots,n\}$. Por otro lado, en cada uno de estos subconjuntos, sus elementos se pueden ordenar en orden creciente; con lo cual el subconjunto se puede ver como una sucesión creciente de $ r $ elementos distintos tomados de $\{1,2,\ldots,n\}$.
De esta manera, los r-subconjuntos y las r-sucesiones crecientes con elementos distintos de $\{1,2,\ldots,n\}$, están en correspondencia uno a uno. Por tanto, vistos como clases de objetos o conjuntos de objetos, tienen la misma cardinalidad. Es decir, el número de sucesiones crecientes que se pueden formar con $ r $ elementos distintos de $\{1,2,\ldots,n\}$ es $C(n,r).$
Argumento alternativo (elección de posiciones)
Si vemos el conjunto $\{1,2,\ldots,n\}$ ya ordenado en orden creciente como una sucesión (en el sentido de que hay un primer elemento, un segundo elemento, etc.), entonces, elegir un r-subconjunto equivale a elegir $ r $ posiciones de entre las $ n $ disponibles; y el mismo procedimiento resulta en una r-sucesión creciente con elementos distintos de $\{1,2,\ldots,n\}$. Luego, la respuesta es $C(n.r).$
Comentario a los argumentos
En el primer argumento se aplica el método biyectivo de demostración, el cual consiste en establecer una correspondencia uno a uno entre los elementos del conjunto que queremos contar y los de otro, del cual es más fácil de establecer su cardinalidad, o bien ya la conocemos. El segundo argumento ya lo habíamos mencionado en el post 3 y es el método de elegir $ r $ posiciones de entre $ n $ dadas. Otra cosa: en este último argumento se ordenan los elementos del conjunto, la aclaración es que en un conjunto el orden no importa pero no está prohibido ordenar sus elementos para los propósitos que a uno convengan.
Relación con expansión de productos
Instancia 1 (número de divisores de un n)
¿Cuántos divisores tiene un número?
Solución: Consideremos la descomposición canónica del número: $n=p^xq^y\ldots$. Entonces los divisores de n (contando el 1 y n mismo) son los términos de la expansión del producto $(1+p+p^2+\ldots+p^x)(1+q+q^2+\ldots+q^y)\ldots$. Pero no nos interesan realmente los divisores sino solamente su número. Y su número se obtiene haciendo (para propósitos de obtenerlo) $1=p=q=\ldots$. ¿Y en qué se convierte el producto después de esto? Bueno, se convierte en $(1+x)(1+y)\ldots$ La respuesta es entonces: los divisores de $n=p^xq^y\ldots$ está dado por el producto $(1+x)(1+y)\ldots$
Comentario (sobre el truco de la solución)
El lector debe hacer el esfuerzo por apropiarse de este truco genial; y lo digo porque podría serle indiferente al no comprender su esencia (al no intentar comprenderlo); para ello, sugiero imaginar la expansión de $(1+p+p^2+\ldots+p^x)(1+q+q^2+\ldots+q^y)\ldots$ y convencerse de que los términos de esa expansión son realmente los divisores de n. Luego, debe ver que si hace cada primo igual a 1 lo que se obtiene es el número de términos de la expansión... Finalmente, debe convertir el resultado en una regla de uso para calcular el número de divisores de un $ n $ (Ver esta instancia de uso [1].)
Instancia 2 (coeficientes binomiales)
¿Cuál es el coeficiente de $x^r$ en la expansión del binomio $(1+x)^n$?
Solución: Para ver este resultado conviene ver el binomio de Newton explícitamente como $(1+x)^n=(1+x)(1+x)(1+x)\ldots(1+x)$ (n paréntesis) antes de expandirlo por la regla distributiva. Luego hay que pensar en que cada uno de los términos de la expansión se forma mediante un proceso de elección: de cada paréntesis se elige el 1 o se elige la $x$ para multiplicar, según la regla distributiva. De esta manera, el coeficiente de $x^r$ se forma con todas las elecciones en que se elige la $x$ de $r$ paréntesis. Es decir, el experimento imaginario que hace el truco aquí es el de elegir $ r $ posiciones de entre $ n $ disponiobles. ¿Y de cuántas formas puedo elegir $ r $ posiciones de entre $ n $ disponibles? De $C(n,r)$ formas ¿no es cierto? Así que la respuesta es: el coeficiente de $x^r$ en la expansión del binomio $(1+x)^n$ es $C(n,r)$.
Los saluda
jmd
PD: estos posts sobre argumentos básicos de conteo son el inicio de unos apuntes de combinatoria con énfasis en razonamiento combinatorio; así que, como un inicio, pueden tener errores tanto en estructura como en redacción; por esta razón les pediría a los usuarios de MaTeTaM que me hicieran saber los posibles errores cometidos y también preguntaran sobre argumentos oscuros y/o de plano incomprensibles (todas las retroalimentaciones son bienvenidas --y se agradecerán).