7.1: Conteo
- Page ID
- 113967
Muchos resultados en matemáticas son respuestas a preguntas de “Cuantos.”.
“¿Cuántos subconjuntos tiene un conjunto finito?”
“¿Cuántos apretones de manos ocurrirán cuando la\(n\) gente se encuentre por primera vez?”
“¿Cuántas funciones hay de un conjunto de tamaño\(n\) a un conjunto de tamaños\(m\)?”
El título de esta sección, “Contando”, no pretende evocar el proceso habitual de contar ovejas, o cambio de conteo. Lo que queremos es poder contar alguna colección en principio para que podamos descubrir una fórmula para su tamaño.
Hay dos principios que serán indispensables para contar las cosas. Estos principios son simples, pero poderosos, y han sido nombrados de la manera más poco imaginativa posible. La “regla de multiplicación” que nos dice cuándo debemos multiplicar, y la “regla de suma” que nos dice cuándo debemos agregar.
Antes de describir estos principios en detalle, vamos a echar un vistazo a un problema más simple que se describe más fácilmente con un ejemplo: ¿Cuántos enteros hay en la lista\((7, 8, 9, . . . 44)\)? Ciertamente podríamos anotar todos los enteros desde\(7\) hasta\(44\) (inclusive) y luego contarlos —aunque este no sería el mejor plan si los números\(7\) y\(44\) fueran reemplazados por (digamos)\(7,045,356\) y\(22,355,201\). Un método que sí conduce a una capacidad generalizada de contar los elementos de una secuencia finita surge si pensamos detenidamente qué es exactamente una secuencia finita.
Una secuencia de un conjunto\(S\) es una función de\(\mathbb{N}\) a\(S\).
Una secuencia finita de un conjunto\(S\) es una función de\(\{0, 1, 2, . . . , n\}\) a\(S\), donde\(n\) hay algún entero particular (finito).
Ahora es fácil ver que hay\(n+1\) elementos en el conjunto\(\{0, 1, 2, . . . , n\}\) por lo que contar los elementos de una secuencia finita será fácil si podemos determinar la función involucrada y averiguar qué\(n\) es invirtiéndola (\(n\)es una imagen inversa para el último elemento en un listado de la secuencia).
En el ejemplo con el que empezamos, la función es\(f(x) = x + 7\). Podemos resumir el proceso que nos permite contar la secuencia diciendo “hay una correspondencia uno a uno entre las listas
\((7, 8, 9, . . . , 44)\)
y
\((0, 1, 2, . . . , 37)\)
y el posterior tiene\(38\) entradas”.
De manera más general, si hay una lista de números consecutivos comenzando con\(k\) y terminando con\(n\), habrá\(n−k +1\) entradas en la lista. Las listas de números enteros consecutivos representan un tipo relativamente simple de secuencia finita. Por lo general, tendríamos alguna función un poco más interesante que necesitaríamos invertir.
El siguiente ejercicio implica invertir la función\((x + 5)^2\).
¿Cuántos enteros hay en la lista\((25, 36, 49, . . . , 10000)\)?
Tendremos mucha más práctica con contar los elementos de secuencias en los ejercicios al final de esta sección, continuemos en nuestro recorrido de contar echando un vistazo a la regla de la suma.
La regla de adición dice que es apropiado agregar si podemos dividir una colección en piezas disjuntas. En otras palabras, si un conjunto\(S\) es la unión de dos o más subconjuntos y estos subconjuntos son mutuamente disjuntos, podemos encontrar el tamaño de\(S\) sumando los tamaños de los subconjuntos.
En el juego Yahtzee, uno\(5\) tira dados y (opcionalmente) realiza una segunda tirada de algunos o todos los dados. El objetivo es lograr varias configuraciones finales que se modelen a partir de las manos en Poker. En particular, una configuración, conocida como “casa llena”, se logra al tener dos de un número y tres de otro. (Coloquialmente, decimos “tres de un tipo más un par es una casa llena”.)
Ahora, podríamos usar las “manos” de Yahtzee para proporcionarnos una colección completa de problemas de conteo una vez que tengamos nuestros principios básicos de conteo, pero por el momento solo queremos hacer un punto simple (y obvio) sobre las “casas llenas”: el par es más pequeño o más grande que el de tres de un tipo. Esto significa que podemos dividir el conjunto de todas las casas completas posibles en dos conjuntos disgregados: las casas completas que consisten en un par pequeño y un trío más grande y aquellos en los que el par es más grande que el tres de una especie. Si podemos encontrar alguna manera de contar estos dos casos por separado, entonces el número total de casas llenas será la suma de estos números.
La regla de multiplicación nos da una manera de contar las cosas pensando en cómo podríamos construirlas. Los números que se multiplican son el número de opciones que tenemos en el proceso de construcción. Sorprendentemente a menudo, el número de elecciones que podemos tomar en una etapa determinada de construcción de alguna configuración es independiente de las elecciones que han ido antes; si este no es el caso, la regla de multiplicación puede no aplicarse.
Si algún objeto se puede construir por\(k\) etapas, y si en la primera etapa tenemos\(n_1\) opciones en cuanto a cómo proceder, en la segunda etapa tenemos\(n_2\) opciones, etcétera. Entonces el número total de tales objetos es el producto\(n_1n_2 · · · n_k\).
Una permutación de un\(n\) -set (w.l.o.g.\(\{1, 2, . . . , n\}\)) es una\(n\) -tupla ordenada donde cada entrada es un elemento distinto del\(n\) -set. Generalmente, una permutación puede considerarse como una biyección de un\(n\) -set a sí mismo. Nuestro primer uso de la regla de multiplicación será contar el número total de permutaciones de\(\{1, 2, 3, . . . , n\}\).
Empecemos por contar las permutaciones de\(\{1, 2, 3\}\). Una permutación será una\(3\) -tupla que contiene los números\(1\),\(2\) y\(3\) en algún orden. Pensaremos en construir tal cosa en tres etapas. Primero, debemos seleccionar un número para ir en la primera posición — hay\(3\) opciones. Habiendo hecho esa elección, sólo habrá dos posibilidades para el número en la segunda posición. Por último, sólo queda un número para poner en la tercera posición 1. Así, hay\(3 · 2 · 1 = 6\) permutaciones de un conjunto\(3\) -elemento.
La regla general es que hay\(n!\) permutaciones de\(\{1, 2, . . . , n\}\).
Hay momentos en que las configuraciones que son como permutaciones (en que están ordenadas y no tienen duplicados) pero que no constan de todos los\(n\) números son útiles.
Una\(k\) permutación de un\(n\) -set es una selección ordenada de\(k\) distintos elementos de un conjunto de tamaños\(n\).
Hay ciertas limitaciones naturales sobre el valor de\(k\), por ejemplo, no\(k\) puede ser negativo —aunque (posiblemente)\(k\) puede serlo\(0\), tiene más sentido pensar en\(k\) ser al menos\(1\). Además, si\(k\) excede no\(n\) podremos encontrar ninguna\(k\) -permutación, ya que será imposible cumplir con el requisito “distinto”. Si\(k\) y\(n\) son iguales, no hay diferencia entre una\(k\) -permutación y una permutación ordinaria. Por lo tanto, ordinariamente restringimos\(k\) a estar en el rango\(0 < k < n\).
La notación\(P(n, k)\) se utiliza para el número total de\(k\) -permutaciones de un conjunto de tamaños\(n\). Por ejemplo,\(P(4, 2)\) es\(12\), ya que hay doce pares ordenados diferentes que tienen entradas distintas de donde provienen las entradas\(\{1, 2, 3, 4\}\).
Anote las doce\(2\) permutaciones del\(4\) -set\(\{1, 2, 3, 4\}\).
Contar\(k\) -permutaciones usando la regla de multiplicación es fácil. Construimos una\(k\) permutación por\(k\) etapas. En etapa\(1\), elegimos el primer elemento en la permutación — hay n opciones posibles. En etapa\(2\), elegimos el segundo elemento —ahora solo hay\(n − 1\) opciones ya que es posible que no repita la primera entrada. Seguimos así hasta que hayamos escogido\(k\) entradas. El número\(P(n, k)\) es el producto de\(k\) números que comienzan con\(n\) y descienden hasta\(n − k + 1\). Para verificar que ese\(n − k + 1\) es realmente el límite inferior correcto, verifique que efectivamente haya\(k\) entradas en la secuencia
\((n, n − 1, n − 2, . . . n − k + 1).\)
Esta verificación puede ser más fácil si reescribimos la secuencia como
\((n − 0, n − 1, n − 2, . . . n − (k − 1)).\)
Echemos un vistazo a otro pequeño ejemplo —\(P(8, 4)\). Habrá\(8\) opciones para la primera entrada en una\(4\) -tupla,\(7\) opciones para la segunda entrada,\(6\) opciones para la tercera entrada y\(5\) opciones para la última entrada. (Tenga en cuenta que\(5 = 8 −4 + 1\).) Así\(P(8, 4) = 8 · 7 · 6 · 5 = 1680\).
Por último, debemos tomar nota de que es relativamente fácil de expresar\(P(n, k)\) usando factoriales. Si dividimos un número factorializado por algún número menor factorializado, obtendremos un producto descendente igual que los anteriores.
¿Por qué factorial\(8!\) dividiríamos para conseguir\(P(8, 4)\)?
La regla general es esa\(P(n, k) = \dfrac{n!}{(n−k)!}\).
Si estuviéramos jugando un juego de cartas en el que nos repartían\(5\) cartas de una baraja de\(52\), recibiríamos nuestras cartas en forma de\(5\) -tuplas\(P(52, 5) = 52·51·50·49·48 = 311875200\) ordenadas. Normalmente, realmente no nos importa en qué orden nos llegaron las tarjetas. En un juego de cartas uno normalmente comienza a clasificar las cartas para ver qué mano tiene uno; esto es una señal segura de que el orden en que se repartieron las cartas es realmente inmaterial. ¿Cuántos pedidos diferentes se pueden poner cinco tarjetas? La respuesta a esta pregunta es\(5! = 120\) ya que lo que estamos discutiendo no es más que una permutación de un conjunto de tamaños\(5\). Así, si decimos que hay\(311,875,200\) diferentes manos posibles en\(5\) -card poker, ¡estamos sobrecontando las cosas por bastante! Cualquier mano dada aparecerá\(120\) veces en esa tabulación, lo que significa que el valor correcto es\(\dfrac{311875200}{120} = 2598960\).
Bien, entonces hay alrededor\(2.6\) de millones de manos diferentes en\(5\) -card poker. A menos que planeas convertirte en jugador, esto no es realmente tan útil de una pieza de información, pero si generalizas lo que hemos hecho en el párrafo anterior, habrás encontrado una manera de contar colecciones desordenadas de un tamaño dado tomadas de un conjunto.
Una\(k\) -combinación de un\(n\) -set es una selección desordenada, sin repeticiones, de\(k\) cosas fuera de\(n\). Esto es exactamente lo mismo que un subconjunto de tamaño\(k\) de un conjunto de tamaños\(n\), y el número de tales cosas se denota por varias notaciones diferentes\(C(n, k)\) —,\(nCk\) y\(\binom{n}{k}\) entre ellas 2. Podemos llegar a una fórmula para\(C(n, k)\) por un argumento ligeramente rotundo. Supongamos que pensamos en contar las\(k\) -permutaciones de\(n\) las cosas usando la regla de multiplicación de una manera diferente a la que tenemos anteriormente. Construiremos una\(k\) permutación en dos etapas. Primero, elegiremos\(k\) símbolos para poner en nuestra permutación, lo que se puede hacer de\(C(n, k)\) maneras. Y segundo, pondremos esos\(k\) símbolos en un orden particular —que se puede lograr de\(k!\) maneras—. Así\(P(n, k) = C(n, k) · k!\). Como ya sabemos eso\(P(n, k) = \dfrac{n!}{(n−k)!}\), podemos sustituir y resolver para obtener
\[C(n, k) = \dfrac{n!}{k! · (n − k)!}.\]
Es posible dividir muchos problemas de conteo en\(4\) “tipos” en función de las respuestas a dos preguntas:
¿Es importante el orden en las configuraciones que se están contando?
¿Se nos permite tener elementos repetidos en una configuración?
Supongamos que estamos en la situación general de seleccionar\(k\) cosas fuera de un conjunto de tamaños\(n\). Debería ser posible escribir fórmulas que involucren\(n\) y\(k\) en las cuatro celdas de la siguiente tabla.
| ¿Importa el Orden? | |||
|
¿Las repeticiones están bien? |
Sí | No | |
| Sí | |||
| No | |||
Ordenado con repetición
Seleccionar un número PIN 3 para tu cuenta bancaria es un buen ejemplo del tipo de problema que se trata en la parte inferior izquierda de la tabla. Obviamente, el orden en el que ingresas los dígitos de tu PIN es importante. Si el número de uno es\(1356\), ¡no va a hacer para poner en\(6531\)! Tampoco hay razón por la que no pudiéramos tener dígitos repetidos en un PIN. (¡Aunque alguien que elige un PIN como\(3333\) está tomando un poco de riesgo para la seguridad! Un tipo malo mirando por encima de tu hombro puede discernir fácilmente cuál es tu PIN.) Un PIN es una selección ordenada de\(4\) cosas fuera de\(10\), donde se permite la repetición. Hay\(104\) posibles PIN. Podemos determinar esto pensando en el principio de multiplicación — hay\(10\) opciones para el primer dígito de nuestro PIN, ya que la repetición está bien todavía hay\(10\) opciones para nuestro segundo dígito, luego (todavía)\(10\) elecciones para el tercer dígito así como para el cuarto dígito.
En general, al seleccionar\(k\) cosas fuera de\(n\) posibilidades, donde se permiten los recuentos de pedidos y la repetición, hay selecciones\(n^k\) posibles.
Ordenado sin repetición
Supongamos que uno desea llegar a una contraseña para una cuenta de computadora. Hay\(52\) letras (tanto mayúsculas como minúsculas),\(10\) números y\(32\) símbolos y signos de puntuación, para un total de caracteres\(94\) diferentes que pueden usarse. Algunos administradores de sistemas pueden ser muy paranoicos acerca de las contraseñas que podrían ser adivinables; por ejemplo, ninguna contraseña que aparece en un diccionario debería usarse nunca en un sistema donde la seguridad es una preocupación. Supongamos que el administrador de su sistema rechazará cualquier contraseña que tenga símbolos repetidos, y que las contraseñas deben tener\(8\) caracteres. ¿Cuántas contraseñas son posibles?
Esta es una instancia de un problema de conteo donde estamos seleccionando\(8\) cosas de un conjunto de tamaños\(94\); claramente el orden es importante y la restricción del administrador del sistema significa que es posible que no tengamos repeticiones. La regla de multiplicación nos dice que existen\(94 · 93 · 92 · 91 · 90 · 89 · 88 · 87 = 4488223369069440\) diferentes contraseñas. Y en el caso general (seleccionar\(k\) cosas fuera de un conjunto de tamaños\(n\), sin repetición, y con conteo de órdenes) habrá\(\dfrac{n!}{(n − k)!}\) posibilidades. Este es el número por el que hemos denotado anteriormente\(P(n, k)\).
Desordenado sin repetición
Este es también un caso que hemos considerado anteriormente. Si estamos eligiendo\(k\) las cosas fuera de lugar\(n\) y el orden no es importante y no puede haber repeticiones, entonces lo que estamos describiendo es un\(k\) -subconjunto del\(n\) -set. Hay\(C(n, k) = \dfrac{n!}{k!(n−k)!}\) distintos subconjuntos. Aquí, vamos a dar un ejemplo que no suena como si estuviéramos hablando de contar subconjuntos de un tamaño determinado. (¡Aunque realmente lo estamos!)
¿Cuántas secuencias diferentes de números\(6\) estrictamente crecientes podemos elegir\(\{1, 2, 3, . . . 20\}\)?
Obviamente, enumerar todas esas secuencias sería una tarea ardua. Podríamos empezar\((1, 2, 3, 4, 5, 6)\) y tratar de proceder de alguna manera ordenada a\((15, 16, 17, 18, 19, 20)\), pero desafortunadamente existen\(38,760\) tales secuencias así que a menos que enlistemos la ayuda de una computadora es poco probable que terminemos este trabajo en un tiempo razonable. El número que acabamos de dar\((38,760)\) es\(C(20, 6)\) y así parecería que estamos alegando que este problema es realmente una selección desordenada sin repetición de\(6\) cosas fuera de\(20\). Bueno, en realidad, algunas partes de esto son claramente correctas —estamos seleccionando\(6\) cosas de un conjunto de tamaños\(20\), y debido a que se supone que nuestras secuencias están aumentando estrictamente no habrá repeticiones— pero, una secuencia estrictamente creciente está claramente ordenada y la fórmula que estamos usando es para colecciones desordenadas.
Al especificar un orden particular (estrictamente creciente) en las secuencias que estamos contando anteriormente, en realidad estamos eliminando la importancia del orden. Dicho de otra manera: si el orden realmente importaba, los símbolos\(1\) a través\(6\) podrían ser puestos en\(720\) diferentes órdenes —pero solo queremos contar una de esas posibilidades—. Dicho de otra manera: hay una correspondencia uno a uno entre un\(6\) subconjunto de\(\{1, 2, 3, . . . 20\}\) y una secuencia estrictamente creciente. ¡Solo asegúrate de que el subconjunto esté escrito en orden creciente!
Bien, en este punto hemos llenado tres de las cuatro celdas de nuestra mesa.
| ¿Importa el Orden? | |||
|
¿Las repeticiones están bien? |
Sí | No | |
| Sí | \(P(n, k) = \dfrac{n!}{(n−k)!}\) | \(C(n, k) = \dfrac{n!}{k!(n−k)!}\) | |
| No | \(n^k\) | ||
¿Qué tipo de cosas estamos contando en la parte inferior derecha de la mesa? Selecciones desordenadas de\(k\) cosas fuera de\(n\) posibilidades donde puede (o no!) ser repeticiones. El juego Yahtzee proporciona un buen ejemplo de este tipo de configuración. Cuando tiramos\(5\) dados, no lo hacemos uno a la vez, más bien, los tiramos como grupo; los dados son indistinguibles por lo que no hay forma de ordenar nuestro conjunto de\(5\) resultados. De hecho, sería bastante razonable, después del rollo de uno, organizar el dado en (digamos) orden creciente. Repetiremos un poco de consejo que se dio anteriormente: si uno es libre de reorganizar una configuración para adaptarse a las necesidades de uno, esa es una pista de que el orden no es importante en las configuraciones bajo consideración. Por último, ¿se permiten las repeticiones? Los resultados en Yahtzee son\(5\) números del set\(\{1, 2, 3, 4, 5, 6\}\), y si bien es posible no tener repeticiones, ¡ese es un resultado bastante especial! En general, el mismo número puede aparecer en dos, o varios, o incluso en todos\(5\) los dados 4.
Entonces, ¿cuántos resultados diferentes hay cuando uno tira cinco dados? Para responder a esta pregunta será útil pensar en cómo podríamos expresar tal resultado. Dado que el orden no es importante, podemos optar por poner los números que aparecen en el dado individual en el orden que queramos. También podemos colocarlos en orden creciente. Habrá\(5\) números y cada número está entre\(1\) y\(6\). Podemos enumerar los resultados sistemáticamente comenzando con un Yahtzee para todos:
\((1,1,1,1,1) \;\;\;\; (1,1,1,1,2) \;\;\;\; (1,1,1,1,3) \;\;\;\; (1,1,1,1,4) \;\;\;\; (1,1,1,1,5) \;\;\;\; (1,1,1,1,6) \\ (1,1,1,2,2) \;\;\;\; (1,1,1,2,3) \;\;\;\; (1,1,1,2,4) \;\;\;\;(1,1,1,2,5) \;\;\;\; (1,1,1,2,6) \;\;\;\; (1,1,1,3,3) \\ (1,1,1,3,4) \;\;\;\; (1,1,1,3,5) \;\;\;\; (1,1,1,3,6) \;\;\;\;(1,1,1,4,4) \;\;\;\;(1,1,1,4,5) \;\;\;\;(1,1,1,4,6) \\ (1,1,1,5,5) \;\;\;\;(1,1,1,5,6)\;\;\;\; (1,1,1,6,6) \;\;\;\;(1,1,2,2,2) \;\;\;\;(1,1,2,2,3)\;\;\;\; (1,1,2,2,4) \\ (1,1,2,2,5) \;\;\;\;(1,1,2,2,6)\;\;\;\; (1,1,2,3,3)\;\;\;\; (1,1,2,3,4)\;\;\;\; (1,1,2,3,5) \;\;\;\;(1,1,2,3,6) \\ (1,1,2,4,4) \;\;\;\;(1,1,2,4,5) \;\;\;\;(1,1,2,4,6) \;\;\;\;(1,1,2,5,5) \;\;\;\;(1,1,2,5,6) \;\;\;\;(1,1,2,6,6) \\ (1,1,3,3,3) \;\;\;\;(1,1,3,3,4) \;\;\;\;(1,1,3,3,5) \;\;\;\;(1,1,3,3,6)\;\;\;\; (1,1,3,4,4) \;\;\;\;(1,1,3,4,5) \\ (1,1,3,4,6) \;\;\;\;(1,1,3,5,5) \;\;\;\;(1,1,3,5,6) \;\;\;\;(1,1,3,6,6) \;\;\;\;(1,1,4,4,4) \;\;\;\;(1,1,4,4,5) \\ (1,1,4,4,6) \;\;\;\;(1,1,4,5,5)\;\;\;\; (1,1,4,5,6) \;\;\;\;(1,1,4,6,6)\;\;\;\; (1,1,5,5,5) \;\;\;\;(1,1,5,5,6) \\ (1,1,5,6,6)\;\;\;\; (1,1,6,6,6) \;\;\;\;(1,2,2,2,2) \;\;\;\;(1,2,2,2,3) \;\;\;\;(1,2,2,2,4) \;\;\;\;(1,2,2,2,5) \\ (1,2,2,2,6)\;\;\;\; (1,2,2,3,3)\;\;\;\; (1,2,2,3,4) \;\;\;\;(1,2,2,3,5) \;\;\;\;(1,2,2,3,6) \;\;\;\;(1,2,2,4,4) \\ (1,2,2,4,5)\;\;\;\; (1,2,2,4,6) \;\;\;\;(1,2,2,5,5) \;\;\;\;(1,2,2,5,6)\;\;\;\; (1,2,2,6,6) \;\;\;\;(1,2,3,3,3) \\ (1,2,3,3,4)\;\;\;\; (1,2,3,3,5) \;\;\;\;(1,2,3,3,6) \;\;\;\;(1,2,3,4,4) \;\;\;\;(1,2,3,4,5) \;\;\;\;(1,2,3,4,6) \\ (1,2,3,5,5) \;\;\;\;(1,2,3,5,6) \;\;\;\;(1,2,3,6,6) \;\;\;\;(1,2,4,4,4)\;\;\;\; (1,2,4,4,5) \;\;\;\;(1,2,4,4,6) \\ (1,2,4,5,5) \;\;\;\;(1,2,4,5,6) \;\;\;\;(1,2,4,6,6)\;\;\;\; (1,2,5,5,5) \;\;\;\;(1,2,5,5,6) \;\;\;\;(1,2,5,6,6) \\ (1,2,6,6,6) \;\;\;\;(1,3,3,3,3)\;\;\;\; (1,3,3,3,4) \;\;\;\;(1,3,3,3,5)\;\;\;\; (1,3,3,3,6) \;\;\;\;(1,3,3,4,4) \\ (1,3,3,4,5)\;\;\;\; (1,3,3,4,6) \;\;\;\;(1,3,3,5,5) \;\;\;\;(1,3,3,5,6) \;\;\;\;(1,3,3,6,6) \;\;\;\;(1,3,4,4,4) \\ (1,3,4,4,5)\;\;\;\; (1,3,4,4,6) \;\;\;\;(1,3,4,5,5) \;\;\;\;(1,3,4,5,6)\;\;\;\; (1,3,4,6,6) \;\;\;\;(1,3,5,5,5) \\ (1,3,5,5,6)\;\;\;\; (1,3,5,6,6)\;\;\;\; (1,3,6,6,6)\;\;\;\; (1,4,4,4,4) \;\;\;\;(1,4,4,4,5)\;\;\;\; (1,4,4,4,6) \\ (1,4,4,5,5) \;\;\;\;(1,4,4,5,6) \;\;\;\;(1,4,4,6,6)\;\;\;\; (1,4,5,5,5)\;\;\;\; (1,4,5,5,6)\;\;\;\; (1,4,5,6,6) \\ (1,4,6,6,6)\;\;\;\; (1,5,5,5,5)\;\;\;\; (1,5,5,5,6) \;\;\;\;(1,5,5,6,6) \;\;\;\;(1,5,6,6,6) \;\;\;\;(1,6,6,6,6) \\ (2,2,2,2,2)\;\;\;\; (2,2,2,2,3)\;\;\;\; (2,2,2,2,4) \;\;\;\;(2,2,2,2,5) \;\;\;\;(2,2,2,2,6) \;\;\;\;(2,2,2,3,3) \\ (2,2,2,3,4)\;\;\;\; (2,2,2,3,5)\;\;\;\; (2,2,2,3,6) \;\;\;\;(2,2,2,4,4) \;\;\;\;(2,2,2,4,5) \;\;\;\;(2,2,2,4,6) \\ (2,2,2,5,5)\;\;\;\; (2,2,2,5,6)\;\;\;\; (2,2,2,6,6) \;\;\;\;(2,2,3,3,3) \;\;\;\;(2,2,3,3,4) \;\;\;\;(2,2,3,3,5) \\ (2,2,3,3,6)\;\;\;\; (2,2,3,4,4)\;\;\;\; (2,2,3,4,5) \;\;\;\;(2,2,3,4,6) \;\;\;\;(2,2,3,5,5) \;\;\;\;(2,2,3,5,6) \\ (2,2,3,6,6)\;\;\;\; (2,2,4,4,4)\;\;\;\; (2,2,4,4,5) \;\;\;\;(2,2,4,4,6) \;\;\;\;(2,2,4,5,5) \;\;\;\;(2,2,4,5,6) \\ (2,2,4,6,6)\;\;\;\; (2,2,5,5,5)\;\;\;\; (2,2,5,5,6) \;\;\;\;(2,2,5,6,6) \;\;\;\;(2,2,6,6,6) \;\;\;\;(2,3,3,3,3) \\ (2,3,3,3,4)\;\;\;\; (2,3,3,3,5)\;\;\;\; (2,3,3,3,6) \;\;\;\;(2,3,3,4,4) \;\;\;\;(2,3,3,4,5) \;\;\;\;(2,3,3,4,6) \\ (2,3,3,5,5) \;\;\;\;(2,3,3,5,6) \;\;\;\;(2,3,3,6,6) \;\;\;\;(2,3,4,4,4)\;\;\;\; (2,3,4,4,5) \;\;\;\;(2,3,4,4,6) \\ (2,3,4,5,5) \;\;\;\;(2,3,4,5,6) \;\;\;\;(2,3,4,6,6) \;\;\;\;(2,3,5,5,5)\;\;\;\; (2,3,5,5,6) \;\;\;\;(2,3,5,6,6) \\ (2,3,6,6,6) \;\;\;\;(2,4,4,4,4) \;\;\;\;(2,4,4,4,5) \;\;\;\;(2,4,4,4,6) \;\;\;\;(2,4,4,5,5) \;\;\;\;(2,4,4,5,6) \\ (2,4,4,6,6) \;\;\;\;(2,4,5,5,5) \;\;\;\;(2,4,5,5,6) \;\;\;\;(2,4,5,6,6)\;\;\;\; (2,4,6,6,6) \;\;\;\;(2,5,5,5,5) \\ (2,5,5,5,6) \;\;\;\;(2,5,5,6,6) \;\;\;\;(2,5,6,6,6) \;\;\;\;(2,6,6,6,6) \;\;\;\;(3,3,3,3,3) \;\;\;\;(3,3,3,3,4) \\ (3,3,3,3,5) \;\;\;\;(3,3,3,3,6) \;\;\;\;(3,3,3,4,4) \;\;\;\;(3,3,3,4,5)\;\;\;\; (3,3,3,4,6) \;\;\;\;(3,3,3,5,5) \\ (3,3,3,5,6)\;\;\;\; (3,3,3,6,6) \;\;\;\;(3,3,4,4,4) \;\;\;\;(3,3,4,4,5)\;\;\;\; (3,3,4,4,6) \;\;\;\;(3,3,4,5,5) \\ (3,3,4,5,6) \;\;\;\;(3,3,4,6,6) \;\;\;\;(3,3,5,5,5) \;\;\;\;(3,3,5,5,6)\;\;\;\; (3,3,5,6,6)\;\;\;\; (3,3,6,6,6) \\ (3,4,4,4,4)\;\;\;\; (3,4,4,4,5)\;\;\;\; (3,4,4,4,6) \;\;\;\;(3,4,4,5,5) \;\;\;\;(3,4,4,5,6) \;\;\;\;(3,4,4,6,6) \\ (3,4,5,5,5)\;\;\;\; (3,4,5,5,6) \;\;\;\;(3,4,5,6,6) \;\;\;\;(3,4,6,6,6) \;\;\;\;(3,5,5,5,5) \;\;\;\;(3,5,5,5,6) \\ (3,5,5,6,6) \;\;\;\;(3,5,6,6,6)\;\;\;\; (3,6,6,6,6) \;\;\;\;(4,4,4,4,4)\;\;\;\; (4,4,4,4,5) \;\;\;\;(4,4,4,4,6) \\ (4,4,4,5,5)\;\;\;\; (4,4,4,5,6)\;\;\;\; (4,4,4,6,6)\;\;\;\; (4,4,5,5,5) \;\;\;\;(4,4,5,5,6) \;\;\;\;(4,4,5,6,6) \\ (4,4,6,6,6)\;\;\;\; (4,5,5,5,5) \;\;\;\;(4,5,5,5,6) \;\;\;\;(4,5,5,6,6)\;\;\;\; (4,5,6,6,6) \;\;\;\;(4,6,6,6,6) \\ (5,5,5,5,5)\;\;\;\; (5,5,5,5,6)\;\;\;\; (5,5,5,6,6) \;\;\;\;(5,5,6,6,6) \;\;\;\;(5,6,6,6,6) \;\;\;\;(6,6,6,6,6) \)
Uf.. ¡errar, quiero decir, Yahtzee!
Puedes describir un elemento genérico del listado anterior diciendo “Comienza con algún número de\(1\)'s (que puede ser cero), luego hay algunos\(2\) (de nuevo, podría ser que haya cero\(2\)), luego algunos (posiblemente ninguno), luego algunos (o tal vez no)\(3\), luego algunos\(4\) (o tal vez no), luego algunos \(5\)'s (creo que probablemente te hagas la idea) y finalmente algunos\(6\) (perdón por todos los comentarios entre paréntesis)”.
Por supuesto, podríamos realmente contar los resultados como se enumeran anteriormente (los hay\(252\)) pero eso sería bastante aburrido —y no nos acercaría más a resolver tales problemas en general. Para contar cosas como rollos de Yahtzee resultará que podemos contar algo relacionado pero mucho más simple: arreglos de coma en blanco. Para el problema de Yahtzee contamos arreglos de\(5\) espacios en blanco y\(5\) comas. Es decir, cosas como\(\underline{\;\;\;}\)\(\underline{\;\;\;}\),,\(\underline{\;\;\;}\),\(\underline{\;\;\;}\), y\(\underline{\;\;\;}\),\(\underline{\;\;\;}\)\(\underline{\;\;\;}\)\(\underline{\;\;\;}\)\(\underline{\;\;\;}\)\(\underline{\;\;\;}\),,,, y,,\(\underline{\;\;\;}\)\(\underline{\;\;\;}\)\(\underline{\;\;\;}\),,,,\(\underline{\;\;\;}\)\(\underline{\;\;\;}\),,. Estos arreglos de espacios en blanco y comas corresponden únicamente a los rollos de Yahtzee: las comas sirven para separar diferentes valores numéricos y los espacios en blanco son donde escribiríamos los\(5\) resultados en el dado.
Convénzase de que realmente hay una correspondencia uno a uno entre los resultados de Yahtzee y los arreglos de\(5\) espacios en blanco y\(5\) comas haciendo lo siguiente
¿Qué rollos Yahtzee corresponden a los siguientes arreglos de coma en blanco?
\(\underline{\;\;\;},\underline{\;\;\;} ,\underline{\;\;\;} ,\underline{\;\;\;} ,\underline{\;\;\;} , \;\;\;\;\;\;\;\;\;\;\; \underline{\;\;\;}\;\underline{\;\;\;},\underline{\;\;\;}\;\underline{\;\;\;}\;\underline{\;\;\;},,,, \;\;\;\;\;\;\;\;\;\;\; ,,,,,\underline{\;\;\;}\;\underline{\;\;\;}\;\underline{\;\;\;}\;\underline{\;\;\;}\;\underline{\;\;\;}\)
¿Qué arreglos de coma en blanco corresponden a los siguientes resultados de Yahtzee?
\(\{2, 3, 4, 5, 6\} \;\;\;\;\;\;\;\;\;\;\; \{3, 3, 3, 3, 4\} \;\;\;\;\;\;\;\;\;\;\; \{5, 5, 6, 6, 6\}\)
Puede parecer al principio que esta cosa de las comas en blanco está bien, pero que todavía no estamos más cerca de responder a la pregunta con la que empezamos. ¡Puede parecer así hasta que te das cuenta de lo fácil que es contar estos arreglos de coma en blanco! Verá, hay\(10\) símbolos en uno de estos arreglos de coma en blanco y si elegimos posiciones para (digamos) las comas, los espacios en blanco tendrán que ir a las otras posiciones —así cada\(5\) subconjunto de nos\(\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}\) da un arreglo de coma en blanco y cada uno de ellos nos da un resultado Yahtzee. Es por ello que hay\(C(10, 5) = 252\) resultados listados en la tabulación gigante anterior.
En general, cuando estamos seleccionando\(k\) cosas de un conjunto de tamaños\(n\) (con repetición y sin orden) tendremos que considerar arreglos de coma en\(k\) blanco que tengan espacios en blanco y\(n−1\) comas. Como ayuda para la memoria, considera que cuando realmente escribes los elementos de un conjunto se necesitan unas comas menos que elementos —por ejemplo\(\{1, 2, 3, 4\}\) tiene\(4\) elementos pero solo necesitamos\(3\) comas para separarlos. La respuesta general a nuestro problema es\(C(k + n − 1, k)\) o\(C(k + n − 1, n − 1)\), dependiendo de si quieres pensar en seleccionar posiciones para los\(k\) espacios en blanco o para las\(n − 1\) comas. Resulta que estos coeficientes binomiales son iguales por lo que no hay problema con la aparente ambigüedad.
Entonces, finalmente, nuestra tabla de fórmulas de conteo está completa. Lo produciremos aquí una vez más y, mientras estamos en ello, abandonaremos la\(C(n, k)\) notación a favor de la notación más habitual de “coeficiente binomial”\(\binom{n}{k}\)
| ¿Importa el Orden? | |||
|
¿Las repeticiones están bien? |
Sí | No | |
| Sí | \(P(n, k) = \dfrac{n!}{(n−k)!}\) | \(C(n, k) = \dfrac{n!}{k!(n−k)!}\) | |
| No | \(n^k\) | \(\binom{n+k−1}{k}\) | |
Ejercicios:
Determinar el número de entradas en las siguientes secuencias.
- \((999, 1000, 1001, . . . 2006)\)
- \((13, 15, 17, . . . 199)\)
- \((13, 19, 25, . . . 601)\)
- \((5, 10, 17, 26, 37, . . . 122)\)
- \((27, 64, 125, 216, . . . 8000)\)
- \((7, 11, 19, 35, 67, . . . 131075)\)
¿Cuántas “casas llenas” hay en Yahtzee? (Una casa llena es un par junto con un tres de una especie.)
¿De cuántas maneras puedes conseguir “dos pares” en Yahtzee?
Demostrar que los coeficientes binomiales\(\binom{n + k − 1}{k}\) y\(\binom{n + k − 1}{n − 1}\) son iguales.
El “alfabeto del criptógrafo” se utiliza para suministrar pequeños ejemplos en codificación y criptografía. Consiste en las primeras\(6\) letras,\(\{a, b, c, d, e, f\}\). ¿Cuántas “palabras” de longitud hasta se\(6\) pueden hacer con este alfabeto? (Una palabra no necesita ser en realidad una palabra en inglés, por ejemplo tanto “fed” como “dfe” serían palabras en el sentido que estamos usando el término.)
¿Cuántas “palabras” hay de longitud\(4\), con letras distintas del alfabeto del Criptógrafo, en las que las letras aparecen alfabéticamente en orden creciente? (“Acef” sería una de esas palabras, pero “café” no lo haría.)
¿Cuántas “palabras” hay de longitud del alfabeto\(4\) del Criptógrafo, con letras repetidas permitidas, en las que las letras aparecen alfabéticamente en orden no decreciente?
¿Cuántos subconjuntos tiene un conjunto finito?
¿Cuántos apretones de manos ocurrirán cuando la\(n\) gente se conozca por primera vez?
¿Cuántas funciones hay de un conjunto de tamaño\(n\) a un conjunto de tamaños\(m\)?
¿Cuántas relaciones hay de un conjunto de tamaño\(n\) a un conjunto de tamaño\(m\)?