Hagamos una pequeña fila

Contar cosas puede ser muy entretenido, y muchas veces es necesario. En las competencias de matemáticas se dedica un tiempo de entrenamiento en ocuparnos de como contar bien y en algunos cursos de probabilidad y estadística lo estudiamos también, pero estos últimos no siempre me agradan porque se vuelven en cursos de fórmulas solamente, como si las deducciones de estas estuvieran fuera del alcance de los alumnos. En honor a esas personas que me han preguntando sobre el origen de algunas fórmulas, escribo este pequeño post sobre conteo.

Existen muchas técnicas de conteo, unas muy simples, como usar tablas o diagramas de arbol y otras más elaboradas como utilizar funciones generatrices o encontrar biyecciones. Aquí en particular me concentraré en reducir algunas situaciones simples de conteo a un problema de poner cosas en fila, ya que en ocasiones termina siendo mucho más simple o al menos las idea es más sencilla de manipular en la cabeza. También haré un peque\~no abuso respecto a algunos conceptos y definiciones, una disculpa por adelantando para quien se de cuenta y le moleste. Comienzo.

Primero lo tedioso, sumas y multiplicaciones. Supongamos que tenemo dos tareas {A} y {B}, cada una puede llevarse a cabo de {a} y {b} maneras respectivamente. Por ejemplo, una tarea puede ser elegir un libro y tener {6} opciones libro o lavarse los dientes y las opciones serían empezar por los dientes de arriba o los de abajo.

Si tenemos dos tareas {A} y {B} y tenemos que realizar una o la otra, las maneras de proceder con la decisión son {a+b} formas de hacer alguna de las dos tareas.

Por ejemplo, si tenemos un menú con {4} diferentes tipos de licuados y {2} tipos de café y tenemos que elegir sólo una bebida para tomar, tenemos {2+4=6} formas diferentes de elegir lo que tomaremos porque solamente podemos tomar café o licuado; por su puesto que la unica decisión correcta sería elegir el café. Dejaré esta regla como consecuencia del sentido común o de hacer arbolitos, tablitas o contar con dedos (con varias manos quizás) y continuaremos.

Si tenemos dos tareas {A} y {B} y tenemos que realizar una y la otra, las maneras de proceder con la decisión son {a\mathop{.}b} formas de hacer ambas tareas.

Aquí por ejemplo, pudieramos estar en un restaurante donde nos ofrecen {3} tipos diferentes de entradas y {6} platos fuertes diferentes. Como en este lugar tenemos que elegir una entrada y un plato fuerte, tenemos un total de {3\mathop{.}6=18} formas diferentes de comer. Pueden llegar a este resultado con la regla de la suma, pensando en que pueden elegir entre {6} maneras de comer (una por plato fuerte) con la primera entrada o {6} maneras de comer con la segunda entrada u otras {6} maneras con la tercera comida. Con la regla de la suma tendríamos el resultado: {6+6+6=3\mathop{.}6}.

La otra manera que me gusta pensar es como si tuvieramos una tabla, en un eje ponemos los nombres de las tres entradas y en el otro los nombres de las 6 comidas. Para elegir lo que comemos seleccionamos el cuadrito donde se cruza a fila y comida que indican lo que queremos. Claramente hay {3\mathop{.}6} cuadritos en esta tabla y cada cuadrito es una opción.

Miles de ejemplos se pueden sacar con estas dos reglas sencillas y miles de ellos se pueden encontrar en internet, por lo que no invertiré tiempo en ejemplos de estas reglas, ni de las otras cosas que desarrollé a menos que lo vea necesario. Mejor procedemos a desarrollar cosas más divertidas.

Pensemos ahora en filas. Supongamos que para entrar a ver The Theory of Everything se tiene que hacer fila en el cine a lo largo de un pasillo largo y delgado de manera que no pueden hacer fila dos personas una al lado de la otra (mala idea en caso de incendio). Digamos que un físico va a ir a verla. Este tendría sólo una manera de hacer fila; llegar y pararse hasta adelante.

Simple. Ahora supongamos que hay dos físicos que llegaron a ver la película. Habrá dos posibles filas, una donde el primer físico este adelante y el segundo justo atrás y donde el primer físico que llego estuviera en segundo lugar y el seguno físico estuviera justo adelante (aunque quizás sería algo injusto). Supongamos ahora que hay tres físicos. Estos tendrían {6} maneras de hacer fila, pues podemos poner a cualquiera de los tres en primer lugar y luego luego ordenar a los siguientes dos.

En adelante consideramos dos tareas al momento de hacer la fila. Supongamos que tenemos {4} físicos. La primer tarea es elegir al físico que va a estar primero en la fila, para ello tenemos {4} opciones y justo después hacemos una fila con los tres restantes justo detrás de el, para esto ya sabemos que tenemos {6} opciones, por lo que obtenemos {4\mathop{.}6=24} opciones. Continuamos con una definición conveniente.

Sea {n!} el número de maneras de poner {n} objetos diferentes en fila

Con esta definición podemos extender lo que haciamos con nuestra fila de físicos. Supongamos que tengo {n} físicos que van a ver la película. Para poner a estos físicos en fila tenemos por definición {n!} maneras de proceder, pero vamos a pensar esto en dos tareas; haremos una y luego la otra. La primera tarea es elegir al físico que va primero, para lo cual tenemos {n} maneras de proceder. La segunda tarea es poner a los otros {n-1} físicos a hacer fila atrás del primero, lo cual también por definición tiene {(n-1)!} maneras de hacerse, de lo anterior, por regla de la multiplicación tenemos que:

\displaystyle n!=n\mathop{.}(n-1)!

Si a la ecuación anterior agregamos que, en particular, {1!=1}, obtenemos la definición recursiva del factorial. Utilizamos la palabra recursividad cuando escribimos los terminos de una sucesión en función de alguno o algunos términos anteriores. Si sustituyeramos {n=1} y realizamos un despeje, podríamos definir convenientemente {0!=1}. Recuerdo que una vez supe de un profesor que decía que explicar porque {0!=1} era muy difícil y que los alumnos no lo entenderían y que por eso no lo explicaba… Bueno este es un porque. Además, si utilizamos la propiedad recursiva varias veces:

\displaystyle n!=n\mathop{.}(n-1)!

\displaystyle n!=n\mathop{.}(n-1)\mathop{.}(n-2)!

\displaystyle n!=n\mathop{.}(n-1)\mathop{.}(n-2)\mathop{.}(n-3)!

\displaystyle \vdots

\displaystyle n!=n\mathop{.}(n-1)\mathop{.}(n-2)\mathop{.}(n-3)!\mathop{...}2\mathop{.}1

Esta última es la formulación con que la mayoría debe estar familiarizado, aunque personalemnte prefiero la versión recursiva y me parece que es más útil.

Utilizaremos esto para probar otras dos formulitas que de vez en cuando encontramos por ahí sin corroborar. Vamos a hacer elecciones. Unicamente elegir, no ordenar. Cosas como elegir que libros vas a comprar en tu visita a la librería; luego te puede preocupar por que leer primero y que despues, pero antes hay que elegir cuales. Para seguir, usaremos otra definición conveniente:

Sea {\binom{n}{k}} el número de maneras de elegir k objetos diferentes (sin repetir) de entre n opciones diferentes.

El número {\binom{n}{k}}, también puede escribirse como {C\binom{n}{k},\; C_k^{n},\; _nC_k}, y puede leerse como “combinaciones de n en k” o sencillamente “n en k, además a estos elementos se les llama coeficientes binomiales. Teniendo esta definición ya podemos empezar a dar respuestas a algunas preguntas. Por ejemplo, si queremos saber de cuantas formas podemos elegir a {6} estudiantes para una delegación de la Olimpida de Matemáticas y tenemos a {30} participantes, las maneras de elegirlos serían simplemente {\binom{30}{6}}. Si tuvieramos un café y tuvieramos que elegir dos bebidas diferentes para llevar teniendo {19} opciones, habría {\binom{19}{2}} formas de realizar la compra, aunque lo más seguro sería elegir alguna bebida con café.

De cualquier manera estas respuestas son un poco tramposas y parecido a contestar con la misma pregunta, muchos prefieren tener un número preciso para trabajar, así que ahora utilizaremos la definición conveniente para dar un valor a {\binom{n}{k}}; en pocas palabras, deduciremos la formulita que la mayoria de nosotros conocemos bajo el mismo proceso, dividir en tareas y poner cosas en fila.

Volvemos a la idea de poner {n} cosas en fila, las maneras de hacer esto, como ya sabemos, son {n!}, pero vamos a realizar este conteo de una manera alternativa. Primero vamos a elegir {k} objetos privilegiados que estarán primero en la fila, los vamos a ordenar y en seguida pondremos a los restantes. Para elegir a las {k} privilegiadas entre las {n} cosas tenemos, por la segunda definición conveniente, un total de {\binom{n}{k}}. Estos {k} objetos pueden ponerse en fila de {k!} maneras diferentes debido a nuestra primera definición conveniente. Nos quedan {(n-k)} objetos no-privilegiados, los cuales pueden poners en fila de {(n-k)!} maneras diferentes, de nuevo por nuestra primera definición conveniente.

Tenemos entonces tres tareas: Vamos a elegir y ordenar a los primeros {k} y ordenar a los restantes {n-k}, por regla de la multiplicación tenemos un total de {\binom{n}{k}\mathop{.}n!\mathop{.}(n-k)!} de construir nuestra fila, pero esto, por la definición que teniamos de los factoriales, debe ser igual a {n!} de donde tenemos que:

\displaystyle n!=\binom{n}{k}\mathop{.}k!\mathop{.}(n-k)!

O bien, podemos despejar esto para obtener lo que buscamos:

\displaystyle \binom{n}{k}=\frac{n!}{k!\mathop{.}(n-k)!}

Listo. A partir de aquí ya podemos atacar muchos problemas de conteo con algo de creatividad. Agregando a esto, a veces nos dan una formula para permutaciones sin repetición, en la que elegimos k objetos y luego los ordenamos, nos dicen que esta es como la de combinaciones pero cuando si nos importa el orden. Personalmente no me agrada mucho esa formula ni la forma en que es presentada porque creo que permite confundirse muy facilemnte y porque simplemente es elegir k objetos mediante combinaciones y luego ordenarlos en fila mediante un factorial:

\displaystyle P_k^{n}=\binom{n}{k}\mathop{.}k!=\frac{n!}{k!\mathop{.}(n-k)!}\mathop{.}k!=\frac{n!}{(n-k)!}

Sin embargo, hay cosas más interesantes que podemos hacer con filas, factoriales y coeficientes binomiales, por ejemplo el teorema del binomio de Newton o algunos resultados interesante que encontramos al pensar un poco en contar de dos maneras la misma cosa. Por lo pronto es todo por este post algo largo. En otra ocasión les quiero contar como obtener algunas formulas para sumar cuadrados, cubos y demás a partir de ideas de conteo; si alguien tiene alguna otra idea o sugerencia que me de, digame en comentarios. Saludos

Advertisements

One thought on “Hagamos una pequeña fila

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s