¿De cuántas formas se puede formar una r-lista (lista de r elementos) con n objetos etiquetados $1,2,\ldots,n$?
(Nota: se entiende que $ r $ no es mayor que $ n $, pues de otra manera ninguna lista se podría formar)
Solución
Encabezando la lista se puede poner cualquiera de los n objetos y, para cada una de esas n elecciones, en segundo lugar se puede poner cualquiera de los n-1 objetos restantes, etc, hasta llegar a la elección r donde se puede colocar en último lugar a cualquiera de los n-(r-1) objetos que aún quedan sin poner en la lista. Es decir, la respuesta es: hay $n(n-1)\ldots(n-r+1)$ r-listas con objetos etiquetados $1,2,\ldots,n$.
Solución alternativa (con argumento de clasificación)
Todas la r-listas las clasifico en n clases: la clase de las que empiezan con el 1, la de las que empiezan con el 2, etc. La clase 1 se puede ver como la clase de (r-1)-listas formadas con los objetos etiquetados $2,3,\ldots,n$, y esto sucede con cada una de las clases: a los objetos $1,2,\ldots,n$ les quitamos el objeto etiquetado i y con los restantes formamos las (r-1)-listas. Si llamamos V(n,r) al número de r-listas formadas con n objetos, entonces cada una de las n clases así formadas tiene V(n-1,r-1) listas. Pero de acuerdo a lo que ya sabemos --o bien por un argumento de inducción-- V(n,r)=n!/(n-r)!. Entonces, el argumento clasificatorio produce $nV(n-1,r-1)=n(n-1)!/(n-1-r+1)!=n!/(n-r)!$ para el número de r-listas formadas con n objetos.
Comentarios
El argumento es el mismo que en las permutaciones (las n-listas con objetos etiquetados $1,2,\ldots,n$). Es el principio multiplicativo aplicado directamente. Y de nuevo aquí podría ser útil pensar en el modelo de urna: en la urna hay n bolas numeradas del q al n, y se hacen extracciones consecutivas sin reemplazo (se saca una bola, se registra y se deja fuera).
Es común que este número (el de $n(n-1)\ldots(n-r+1)$ de r-listas con objetos etiquetados $1,2,\ldots,n$) se exprese mediante factoriales. El lector debería convencerse de que $n(n-1)\ldots(n-r+1)=n!/(n-r)!.$ (Al número de r-listas formadas con n objetos, se le llama también --en una terminología ya en desuso-- Variaciones de n objetos tomados de r en r.)
El lector haría bien en generar las V(n,r) para valores pequeños de n y r, como un medio para que empiece a tomar confianza en los argumentos combinatorios. Por ejemplo, para n=4 y r=2, V(4,2)=4!/2=12. En vista de este resultado, debería generar todas las 12 2-listas una por una. Y quizá podría desear clasificarlas, como se hace en el argumento clasificatorio.
Los saluda
jmd
Creo que en la parte en la
Creo que en la parte en la que dice:
"Entonces, el argumento clasificatorio produce $ nV(n-1,r-1)=n(n-1)!/(n-1-r+1)=n!/(n-r)! $ para el número de r-listas formadas con n objetos."
debería decir:
"Entonces, el argumento clasificatorio produce $ nV(n-1,r-1)=n(n-1)!/(n-1-r+1)!=n!/(n-r)! $ para el número de r-listas formadas con n objetos."
pues en la expresión el denominador primero no tiene factorial y después sí.
En otra cuestión: estuve pensando en otra forma de interpretar la siguiente expresión:
Lo que queremos demostrar es que el número de r-listas es igual a la división de n! entre (n-r)!. Tenemos n objetos en la lista original. El total de formas de ordenar esos n objetos en una lista de n objetos sabemos por el post anterior que es
De cada una de esas n! formas distintas de ordenar la lista de n objetos, observamos la secuencia inicial de r objetos (es decir, la secuencia de los primeros r objetos de la lista). La pregunta es: ¿cuántas listas de n objetos tienen una secuencia inicial fija de r objetos? Pues bien, como son n objetos, y tenemos una secuencia inicial de r objetos fija, lo que nos interesa contar entonces es la forma de ordenar una lista de (n-r) objetos (que es la cantidad de objetos que nos quedan), pero esto ya sabemos hacerlo también por el post anterior, así que podemos afirmar que hay (n-r)! de hacer esto, es decir, el total de listas de n objetos que empiezan con una secuencia inicial fija de r objetos es:
Si estudiamos cuidadosamente el último razonamiento, nos podemos dar cuenta que cada secuencia inicial distinta de r objetos se repite exactamente (n-r)! veces en las n! distintas formas de ordenar una lista de n objetos, así que el total de listas de n objetos que tienen una secuencia inicial distinta de r objetos es
pero sólo nos interesa la secuencia inicial de r objetos, así que os podemos olvidar de los (n-r) objetos restantes y afirmamos que hay
r-listas de una lista de n objetos, y esto es lo que queríamos demostrar.
(PD. La combinatoria no es lo mío xD, pero se ve vino esa idea para contar algo de una manera distinta, quizás haya algún error o se pueda aclarar mejor xD)
Muy buena observación Zzq. Tu
Muy buena observación Zzq. Tu argumento es de doble conteo. Lo puedo resumir así:
Contar las n-permutaciones de dos formas:
Por un lado sabemos que son n!, Pero también podemos clasificarlas por sus primeros r elementos: a cada una de las V(n,r) r-listas, le añadimos los n-r objetos restantes y éstos se ordenan de todas las formas posibles (es decir, hay (n-r)! formas de añadirlos a la lista ya formada de r objetos tomados de los n). Esto produce la ecuación V(n.r)(n-r)!=n!.
Yo más bien estaba pensando en un argumento algebraico: dado que V(n,r)=n(n-1)...(n-r+1), se puede multiplicar y dividir por los factores que completan n! y ya se obtendría la fórmula. Es decir, multiplicar por (n-r)(n-r-1)...(2)(1) y dividir entre eso mismo.
Te saluda
jmd
PD: Por otro lado, gracias por la corrección; sí faltaba un signo de factorial --ya lo agregué.
Si, a veces hago argumentos
Si, a veces hago argumentos de combinatoria muy extensos xD, cuando escribo poquito siento que algo me hace falta (sean casos o argumentos o pruebas para comprobar una hipotesis). Gracias por el resumen, sabía que se podía aclarar mejor :D, gracias :D.
Saludoz :D