Archivo de la etiqueta: conteo

Probabilidad I: La Probabilidad Clásica

Por Octavio Daniel Ríos García

Introducción

En la entrada anterior concluimos nuestro estudio de los principios de conteo. Estos principios resultan muy útiles para el cálculo de cardinalidades de conjuntos. Además, la medida de probabilidad que veremos en esta entrada requiere precisamente de cardinalidades de conjuntos para ser calculada. Por ello, los principios de conteo que vimos serán cruciales para el cálculo de probabilidades bajo este enfoque.

Lo que veremos en esta entrada es el enfoque clásico de la probabilidad. A grandes rasgos, este enfoque centra su atención en la cantidad de resultados posibles de un experimento; es decir, la cardinalidad de su espacio muestral. A su vez, dado algún evento de ese espacio muestral, el enfoque clásico establecerá la probabilidad de ese evento es proporcional a su cardinalidad con respecto a la cardinalidad del espacio muestral. Esto significa que bajo el enfoque clásico, el espacio de probabilidad es equiprobable. Veamos qué queremos decir por esto.

Motivación

Ya vimos que en el enfoque frecuentista se propone que la medida de probabilidad debe de representar la «frecuencia relativa» de un evento. Por ello, en la definición de la medida de probabilidad frecuentista de un evento $A$ se toma el límite al infinito de la frecuencia relativa de $A$.

Continuando con nuestro paseo por los enfoques más importantes de la probabilidad, sigue el caso de la probabilidad clásica. En este caso partiremos de un enfoque distinto del frecuentista. Para empezar, motivaremos este enfoque con un ejemplo. Supón que nos interesa modelar el resultado de revolver una baraja inglesa y tomar $4$ cartas, sin reemplazo. Esta actividad se considera un experimento aleatorio pues se revuelve la baraja antes de tomar las $4$ cartas. Podemos representar a una baraja estándar como el conjunto

\begin{align*} \mathfrak{B} = \begin{Bmatrix} \textcolor{red}{\mathrm{A}\heartsuit}, & \textcolor{red}{1\heartsuit}, & \textcolor{red}{2\heartsuit}, & \textcolor{red}{3\heartsuit}, & \textcolor{red}{4\heartsuit}, & \textcolor{red}{5\heartsuit}, & \textcolor{red}{6\heartsuit}, & \textcolor{red}{7\heartsuit}, & \textcolor{red}{8\heartsuit}, & \textcolor{red}{9\heartsuit}, & \textcolor{red}{10\heartsuit}, & \textcolor{red}{\mathrm{J}\heartsuit}, & \textcolor{red}{\mathrm{Q}\heartsuit}, & \textcolor{red}{\mathrm{K}\heartsuit}, \\ \textcolor{red}{\mathrm{A}\blacklozenge}, & \textcolor{red}{1\blacklozenge}, & \textcolor{red}{2\blacklozenge}, & \textcolor{red}{3\blacklozenge}, & \textcolor{red}{4\blacklozenge}, & \textcolor{red}{5\blacklozenge}, & \textcolor{red}{6\blacklozenge}, & \textcolor{red}{7\blacklozenge}, & \textcolor{red}{8\blacklozenge}, & \textcolor{red}{9\blacklozenge}, & \textcolor{red}{10\blacklozenge}, & \textcolor{red}{\mathrm{J}\blacklozenge}, & \textcolor{red}{\mathrm{Q}\blacklozenge}, & \textcolor{red}{\mathrm{K}\blacklozenge}, \\ \mathrm{A}\spadesuit, & 1\spadesuit, & 2\spadesuit, & 3\spadesuit, & 4\spadesuit, & 5\spadesuit, & 6\spadesuit, & 7\spadesuit, & 8\spadesuit, & 9\spadesuit, & 10\spadesuit, & \mathrm{J}\spadesuit, & \mathrm{Q}\spadesuit, & \mathrm{K}\spadesuit, \\ \mathrm{A}\clubsuit, & 1\clubsuit, & 2\clubsuit, & 3\clubsuit, & 4\clubsuit, & 5\clubsuit, & 6\clubsuit, & 7\clubsuit, & 8\clubsuit, & 9\clubsuit, & 10\clubsuit, & \mathrm{J}\clubsuit, & \mathrm{Q}\clubsuit, & \mathrm{K}\clubsuit \end{Bmatrix} \end{align*}

donde cada elemento representa a cada uno de los elementos de la baraja. Por ejemplo, el elemento $\textcolor{red}{9\blacklozenge}$ es el $9$ de diamantes, $\mathrm{Q}\clubsuit$ es la reina de tréboles, $\mathrm{K}\spadesuit$ es el rey de espadas y $\textcolor{red}{\mathrm{J}\heartsuit}$ es la jota de corazones.

¡Atención! El conjunto $\mathfrak{B}$ no es el espacio muestral de nuestro experimento. Recuerda que el espacio muestral de un experimento aleatorio es el conjunto de todos sus posibles resultados. Así, como nuestro experimento consiste en extraer 4 cartas de una baraja revuelta, los elementos del espacio muestral debieran de ser manos de 4 cartas. Además, no importa el orden en el que tomemos las cartas, la mano resultante es la misma.

Por ello, las manos resultantes en este experimento pueden verse como subconjuntos de $\mathfrak{B}$. Por ejemplo, supón que $4$ cartas y te salen $6\clubsuit$, $\textcolor{red}{9\blacklozenge}$, $\mathrm{K}\clubsuit$ y $\textcolor{red}{8\heartsuit}$. El resultado del experimento en esta situación fue ${6\clubsuit, \textcolor{red}{9\blacklozenge}, \mathrm{K}\clubsuit, \textcolor{red}{8\heartsuit}}$, pues en un conjunto no importa el orden. Además, observa que el resultado tiene cardinalidad $4$. En consecuencia, podemos tomar al espacio muestral como

\[ \Omega = \{ M \in \mathscr{P}(\mathfrak{B}) \mid |M| = 4 \}. \]

Es decir, el espacio muestral $\Omega$ de este experimento es el conjunto de todos los subconjuntos de la baraja que tienen $4$ cartas. Como $\mathfrak{B}$ es un conjunto finito (se cumple que $|\mathfrak{B}|=52$), también $\Omega$ es un conjunto finito. De hecho, se cumple que $|\Omega| = {52 \choose 4} = 270{,}725$, pues hay ${52 \choose 4}$ combinaciones de tamaño $4$ de las $52$ cartas. Podemos tomar como σ-álgebra a $\mathscr{P}(\Omega)$, que siempre es un σ-álgebra.

Ahora, ¿qué probabilidad le asignamos a cada evento de $\Omega$? Por ejemplo, ¿cuál es la probabilidad de que en las $4$ cartas que tomamos no haya tréboles? Un posible resultado de este tipo es que las $4$ cartas que nos salgan sean $\{ \textcolor{red}{\mathrm{J}\heartsuit}, 10\spadesuit, \textcolor{red}{9\blacklozenge}, 5\spadesuit \}$. Para hacerlo, el enfoque clásico propone lo siguiente:

La probabilidad de un evento es la proporción entre el número de casos favorables a este, y el número de casos totales del experimento.

Esta hipótesis es conocida como equiprobabilidad. Así, para obtener la probabilidad de que en las $4$ cartas que tomemos no haya tréboles, debemos de obtener cuántas manos de $4$ cartas sin tréboles hay. Para ello, observa que en la baraja hay $13$ cartas que son tréboles. Por tanto, la combinación de cartas de nuestro evento está restringida a las $39$ cartas que no son tréboles. En consecuencia, hay ${39 \choose 4} = 82{,}251$ manos de $4$ cartas sin tréboles, pues hay ${39 \choose 4}$ combinaciones de tamaño $4$ de las $39$ cartas que no son tréboles. Así, desde el enfoque clásico de la probabilidad, la probabilidad de que en las $4$ cartas que tomemos no haya tréboles es

\[ \frac{\text{Número de casos favorables}}{\text{Número de casos totales}} = \frac{{39 \choose 4}}{{52 \choose 4}} = \frac{82{,}251}{270{,}725} \]

Definición de una medida equiprobable

De acuerdo con la motivación expuesta en la sección anterior, presentamos la definición formal de un espacio equiprobable. Esta definición resume las ideas del enfoque clásico de la probabilidad.

Definición. Sea $\Omega$ un conjunto finito. Definimos a $\mathbb{P}\colon \mathscr{P}(\Omega) \rightarrow \mathbb{R}$, la medida de probabilidad clásica, como sigue. Para cada $A \in \mathscr{P}(\Omega)$, se define la probabilidad de $A$ como

\[ \Prob{A} = \frac{|A|}{|\Omega|}. \]

Un espacio de probabilidad $(\Omega, \mathscr{F}, \mathbb{P})$ con esta medida de probabilidad es conocido como un espacio equiprobable.

De acuerdo con la definición anterior, el enfoque clásico de la probabilidad tiene dos hipótesis importantes sobre el fenómeno aleatorio que se intenta describir:

Primero, que $\Omega$ el espacio muestral del fenómeno es finito.
Segundo, que se trata de un espacio equiprobable. Esto es, que si el fenómeno tiene $|\Omega|$ resultados posibles, entonces cada uno tiene una probabilidad de ocurrencia igual a $\frac{1}{|\Omega|}$.

En particular, el segundo supuesto puede ser problemático. ¿Qué nos asegura que al revolver la baraja del último ejemplo obtenemos efectivamente un espacio equiprobable? Hay que tener cuidado con esto, ya que es un supuesto muy fuerte que no necesariamente se cumple.

Importante. En la literatura referente a la probabilidad, es común encontrar la expresión «al azar» en la forma de «se escoge un estudiante del grupo al azar», o «se escoge(n) una(s) carta(s) de la baraja al azar». Sin embargo, no existe una manera única de hacer una tarea «al azar», ya que hay muchísimas medidas de probabilidad, así que podría resultar ambiguo. Por ello, es común que la expresión «al azar» se refiera a asumir que el espacio es equiprobable, a menos que se indique lo contraro.

Ejemplos con el enfoque clásico

Ejemplo 1. En una encuesta a 120 comensales, un restaurante encontró que $48$ personas consumen vino con sus alimentos, $78$ consumen refresco, y $66$ consumen té helado. Además, se encontró que $36$ personas consumieron cada par de bebidas con sus alimentos. Es decir, $36$ personas consumieron vino y refresco; $36$ consumieron vino y té helado; etcétera. Finalmente, el último hallazgo fue que $24$ personas consumieron todas las bebidas.

Si se eligen $2$ comensales al azar, de manera equiprobable, de este grupo de $120$, cuál es la probabilidad de que

ambos quieran únicamente té helado con sus alimentos? (Evento $A$)
ambos consuman exactamente dos de las tres opciones de bebidas? (Evento $B$)

Utilizando la información provista por la encuesta, podemos construir el siguiente diagrama de Venn-Euler:

**Figura.** Diagrama que representa los conjuntos de personas dentro de la encuesta. $U$ es la muestra de $120$ personas, $V$ son las que consumieron **vino**, $T$ las que consumieron **té helado**, y $R$ las que consumieron **refresco**.

Sin embargo, nota que nuestro espacio muestral no es $U$, porque lo que hacemos es tomar dos personas al azar. Por ello, el espacio muestral $\Omega$ consiste de todos los pares de comensales que se pueden elegir de la muestra de $120$. Por ello, $|\Omega| = \binom{120}{2} = 7140$. Por otro lado, el diagrama nos dice que hay $18$ comensales que consumieron únicamente té helado con sus alimentos. Por ello, el número de pares de comensales que consumieron únicamente té helado es $\binom{18}{2}$. Esto quiere decir que $|A| = \binom{18}{2} = 153$. En consecuencia,

\begin{align*} \Prob{A} &= \frac{|A|}{|\Omega|} = \frac{153}{7140} \approx 0.02143. \end{align*}

Esto es, la probabilidad de que las dos personas escogidas consuman únicamente té helado es aproximadamente $2.143\%$.

Ejemplo 2. Sea $X = \{1,2,3,\ldots,99,100\}$. Imagina que seleccionamos $2$ elementos de $X$ al azar, sin reemplazo. ¿Cuál será la probabilidad de que la suma de esos dos números sea par?

Para encontrar esta probabilidad, primero hay que plantear nuestro espacio muestral y el evento cuya probabilidad queremos. Lo que hacemos es seleccionar $2$ elementos de $X$ sin reemplazo, así que nuestro espacio muestral $\Omega$ debe de tener pares de números. Sin embargo, nota que son pares en los que no importa el orden, pues elegir los números $14$ y $73$ es lo mismo que escoger los números $73$ y $14$. Por ello, $\Omega$ es el conjunto de subconjuntos de $X$ que tienen exactamente dos elementos. Esto es,

\begin{align*} \Omega &= \{ A \in \mathscr{P}(X) \mid |A| = 2 \}. \end{align*}

En consecuencia, tenemos que $|\Omega| = \binom{100}{2} = 4950$. Ahora, queremos la probabilidad del evento de que la suma de los $2$ números escogidos sea par. Es decir, buscamos la probabilidad de \mathcal{B} definido como

\begin{align*} \mathcal{B} &= \{ \{a, b\} \in \Omega \mid \text{$a + b$ es par} \}. \end{align*}

Sin embargo, no parece haber una forma inmediata de calcular $|\mathcal{B}|$, con lo que podríamos calcular $\Prob{\mathcal{B}}$. No obstante, podemos descomponer a $|\mathcal{B}|$ en dos conjuntos cuya cardinalidad sí es posible calcular. Para ello, observa que los elementos de $X$ pueden ser pares o impares, sin otra opción. En consecuencia, hay $3$ casos posibles al elegir $2$ elementos de $X$. Sea $A = \{a, b\} \in \Omega$. Entonces puede pasar que

$a$ y $b$ son ambos pares. Es decir, existen $p, q \in \mathbb{Z}$ tales que $a = 2p$ y $b = 2q$. En consecuencia, $a + b = 2p + 2q = 2(p + q)$. En conclusión, si $a$ y $b$ son pares, entonces $a + b$ es par.
$a$ es par y $b$ es impar (y viceversa). En este caso, existen $p, q \in \mathbb{Z}$ tales que $a = 2p$ y $b = 2q + 1$. Por ello, $a + b = 2p + 2q + 1 = 2(p+q) + 1$. Por lo tanto, si $a$ es par y $b$ es impar, entonces $a + b$ es impar.
$a$ y $b$ son impares. Esto implica que existen $p, q \in \mathbb{Z}$ tales que $a = 2p + 1$ y $b = 2q + 1$. Por tanto, $a + b = 2p + 1 + 2q + 1 = 2(p+q+ 1)$. Así, si $a$ y $b$ son impares, entonces $a+b$ es impar.

De este modo, tenemos que $\mathcal{B}$ se puede descomponer en la unión de dos eventos:

$\mathcal{E}_{1}$ : El evento de que los dos números escogidos sean pares:\begin{align*}\mathcal{E}_{1} = \{\{a, b\} \in \Omega \mid \text{$a, b$ son pares}\}.\end{align*}
$\mathcal{E}_{2}$ : El evento de que los dos números escogidos sean impares:\begin{align*}\mathcal{E}_{2} = \{\{a, b\} \in \Omega \mid \text{$a, b$ son impares}\}.\end{align*}

Como en $X$ hay $50$ pares y $50$ impares, se tiene que $|\mathcal{E}_{1}| = |\mathcal{E}_{2}| = \binom{50}{2} = 1225$. Además, observa que $\mathcal{E}_{1} \cup \mathcal{E}_{2} = \mathcal{B}$, y que además son eventos ajenos. En consecuencia,

\begin{align*}|\mathcal{B}| &= | \mathcal{E}_{1} \cup \mathcal{E}_{2} | = | \mathcal{E}_{1} | + | \mathcal{E}_{2} | = \binom{50}{2} + \binom{50}{2} = 2450.\end{align*}

Finalmente, con esta información podemos calcular $\Prob{\mathcal{B}}$. En efecto,

\begin{align*} \Prob{ \mathcal{B}} &= \frac{|\mathcal{B}|}{|\Omega|} = \frac{2450}{4950} = \frac{49}{99} = 0.4949494949\ldots \end{align*}

Un consejo: En los problemas donde se utiliza la probabilidad clásica (es decir, se asume equiprobabilidad en un espacio finito), es recomendable que dejes el cálculo de las probabilidades hasta el final. Realmente el meollo de estos problemas es contar la cantidad de resultados que tiene el espacio muestral $\Omega$, así como el número de resultados que tiene un evento $A$. Por ello, centra tu atención en esos cálculos antes de calcular probabilidades.

Tarea moral

Los siguientes ejercicios son opcionales. Es decir, no formarán parte de tu calificación. Sin embargo, te recomiendo resolverlos para que desarrolles tu dominio de los conceptos abordados en esta entrada.

Demuestra que la medida de probabilidad clásica es una medida de probabilidad.
En el ejemplo de la encuesta a los comensales, verifica que
1. los números en el diagrama de Venn-Euler son las cardinalidades correctas.
2. la probabilidad del evento $B$ es $3/34 \approx 0.08824$.
Usando el conjunto $X = \{1,2,\ldots,99,100\}$ del Ejemplo 2, si se eligen 3 elementos de $X$ al azar y sin reemplazo, ¿cuál es la probabilidad de que la suma de estos 3 números sea par? Sugerencia: Procede de manera similar a como hicimos aquí, y obtén los casos en los que la suma de los $3$ números resulta en un número par.

Más adelante…

Esta entrada concluye nuestro estudio de los tres enfoques que contempla el temario de la Facultad de Ciencias para Probabilidad I. Es importante entender que los enfoques (o interpretaciones) de la probabilidad que hemos visto tienen gran importancia histórica. Sin embargo, pueden ser escritos matemáticamente a través de las herramientas que construimos al principio, que conforman el enfoque más moderno de este curso: la probabilidad axiomática. Es conocida de esta manera pues se parte de ciertos objetos matemáticos que satisfacen ciertas reglas (conocidas como axiomas). Este enfoque axiomático, que rige sobre el contenido de estas notas, se atribuye al matemático ruso Andrey Nikolaevich Kolmogorov. Además, es un enfoque flexible que nos ha permitido revisar los enfoques históricos de la probabilidad como casos particulares dentro de la teoría que hemos desarrollado.

Si te interesa saber más sobre la historia de la probabilidad, el libro Introducción a la Teoría de la Probabilidad, Vol. I, del Dr. Miguel Ángel García Álvarez tiene una sección no muy larga dedicada al panorama histórico de esta rama de las matemáticas. Además, al final de esta sección incluye varias referencias de matemáticos de suma importancia en el desarrollo de la probabilidad, como Bernoulli y Laplace, o el mismo Kolmogorov.

Entradas relacionadas

Ir a Probabilidad I
Entrada anterior del curso: Principios de Conteo 3 – Combinaciones
Siguiente entrada del curso: Probabilidad Condicional

Probabilidad I: Principios de Conteo 3 – Combinaciones

Por Octavio Daniel Ríos García

Deja un comentario

Introducción

En la entrada anterior vimos lo que son las permutaciones de tamaño $r$ de una colección de $n$ objetos. Además, observamos que al momento de calcular la cantidad de permutaciones de ese tipo, se toman en cuenta los arreglos lineales que tienen los mismos objetos, pero ordenados de distinta manera. Por ejemplo, recuerda el problema de los $10$ estudiantes. Ahí, vimos que al momento de contar las permutaciones de tamaño $5$ de los $10$ estudiantes, se contabilizaban $\mathrm{BCEFI}$ y $\mathrm{CEFIB}$. Esto pues aunque tienen los mismos objetos, el orden en el que se encuentran es diferente.

Por otra parte, también puede interesarnos encontrar la cantidad de arreglos lineales en donde los elementos son distintos. Es decir, considerar a aquellos arreglos que tienen los mismos elementos como indistinguibles, incluso si se encuentran en un orden distinto. Esto es precisamente lo que haremos en esta entrada: desarrollar un concepto que nos permita contar nada más eso.

Motivación

Para comenzar, veamos un ejemplo clásico de conteo. Una baraja inglesa estándar está formada por $52$ cartas que comprenden $4$ palos: tréboles, diamantes, corazones y espadas. Cada palo tiene $13$ cartas: As, $2$, $3$, $4$, …, $9$, $10$, jota, reina y rey. Si se nos pide tomar tres cartas de una baraja inglesa, una después de otra y sin reemplazo (es decir, sin devolver las cartas que ya hemos tomado), entonces por el principio del producto hay

\[ 52 \cdot 51 \cdot 50 = \frac{52!}{49!} = P(52, 3) = 132{,}600 \]

posibles resultados. Por ejemplo, una de las posibles ternas de cartas que te pueden salir es $\color{red}{\mathrm{A}\heartsuit}$ (as de corazones), $9\clubsuit$ (nueve de tréboles), $\color{red}{\mathrm{K}\blacklozenge}$ (rey de diamantes). Pero, cuidado, recuerda que en el contexto de las permutaciones, «$\textcolor{red}{\mathrm{A}\heartsuit}\text{-}{9\clubsuit}\text{-}\textcolor{red}{\mathrm{K}\blacklozenge}$» se considera como un resultado distinto a «${9\clubsuit}\text{-}\textcolor{red}{\mathrm{A}\heartsuit}\text{-}\textcolor{red}{\mathrm{K}\blacklozenge}$» o «$\textcolor{red}{\mathrm{K}\blacklozenge}\text{-}\textcolor{red}{\mathrm{A}\heartsuit}\text{-}{9\clubsuit}$».

Sin embargo, observa que las cartas con las que terminas son las mismas sin importar el orden en el que las sacaste. Es decir, en tu mano estarán el as de corazones, el nueve de tréboles y el rey de diamantes sin importar el orden en el que se extraen. Por ello, podríamos considerar a todas las cadenas de cartas que tienen los mismos elementos como indistinguibles. Esto es, «$\textcolor{red}{\mathrm{A}\heartsuit} \text{-} {9\clubsuit} \text{-} \textcolor{red}{\mathrm{K}\blacklozenge}$», «$\textcolor{red}{\mathrm{A}\heartsuit} \text{-} \textcolor{red}{\mathrm{K}\blacklozenge} \text{-} {9\clubsuit}$», «${9\clubsuit} \text{-} \textcolor{red}{\mathrm{K}\blacklozenge} \text{-} \textcolor{red}{\mathrm{A}\heartsuit}$», «${9\clubsuit} \text{-} \textcolor{red}{\mathrm{A}\heartsuit} \text{-} \textcolor{red}{\mathrm{K}\blacklozenge}$», «$\textcolor{red}{\mathrm{K}\blacklozenge} \text{-} {9\clubsuit} \text{-} \textcolor{red}{\mathrm{A}\heartsuit}$» y «$\textcolor{red}{\mathrm{K}\blacklozenge} \text{-} \textcolor{red}{\mathrm{A}\heartsuit} \text{-} {9\clubsuit}$», las $6$ permutaciones posibles de las $3$ cartas, corresponden a una sola selección (sin orden) de cartas. En consecuencia, cada selección, o combinación, de $3$ cartas, sin tomar en cuenta el orden, corresponde a $3!$ permutaciones de $3$ cartas. En forma de ecuación, esto es:

\begin{align*} (3!)\cdot (\text{No. de combinaciones} \; &\text{de} \; \text{tamaño $3$ de una baraja de $52$}) \\ &= \text{No. de permutaciones de tamaño $3$ de una baraja de $52$} \\ &= P(52, 3) \\ &= \frac{52!}{49!}. \end{align*}

En conclusión, se pueden extraer, sin reemplazo, $3$ cartas sin reemplazo de una baraja inglesa estándar de $\frac{132{,}600}{3!} = 22{,}000$ maneras distintas.

Fórmula para el número de combinaciones sin repetición

Con la idea desarrollada en el ejemplo anterior, podemos presentar una fórmula para el cálculo del número de combinaciones de tamaño $r$ de una colección de $n$ objetos objetos.

Número de Combinaciones. Si tenemos $n$ objetos distintos, una combinación de $r$ de esos objetos, sin tomar en cuenta el orden, corresponde a $r!$ permutaciones de tamaño $r$ de los $n$ objetos. Por ello, el número de combinaciones de tamaño $r$ de una colección de $n$ objetos es

\[ C(n,r) = \frac{P(n,r)}{r!} = \frac{n!}{r!(n − r)!}, \]

para $n, r \in \mathbb{N}$ tales que $0 \leq r \leq n$.

Para denotar al número de combinaciones de tamaño $r$ de una colección de $n$ objetos también se utiliza el símbolo ${n \choose r}$, y en algunas ocasiones el símbolo $\mathrm{C}_{r}^{n}$.

Algunas observaciones importantes:

${n \choose k}$ es también conocido como coeficiente binomial.
Para cualquier $n \geq 0$ se cumple que $C(n,0) = C(n,n) = 1$. Por un lado, el número de combinaciones de tamaño $0$ es $1$ porque sólo hay una combinación vacía. Por otro lado, el número de combinaciones de tamaño $n$ es $1$ porque la única combinación de tamaño $n$ es la colección misma.
Para cualquier $n \geq 1$, $C(n,1) = C(n,n−1) = n$.
En general, para cualesquiera $n, r \in \mathbb{N}$ tales que $0 \leq r \leq n$ se cumple que \[ C(n,r) = C(n, n−r). \]
Cuando $n < r$, se tiene que $C(n,r) = 0$.

¡Observación importante! – Cuando te enfrentes a cualquier problema de conteo, la primera pregunta que debes de hacerte es: «¿importa el orden?» Cuando el orden sí es relevante, deberás pensar en términos de permutaciones y el principio del producto. Por otro lado, cuando el orden no es relevante, las combinaciones serán una parte importante para resolver el problema.

Ejemplos de problemas con combinaciones sin repetición

Ejemplo. Una primera aplicación interesante es la siguiente. Sean $n \in \mathbb{N}$ y $A$ un conjunto finito tal que $|A| = n$. En consecuencia, podemos escribir a $A$ como sigue:

\[ A = \{ a_{1}, a_{2}, \ldots, a_{n} \}. \]

Es decir, $A$ es una colección de $n$ objetos distintos. Para $r \leq n$, podemos preguntarnos: «¿cuántos subconjuntos de $A$ hay cuya cardinalidad es $r$?» Los conjuntos (en la teoría matemática) son colecciones de objetos en donde el orden en el que se escriben sus elementos no importa. Por ejemplo, se cumple que

\[ \{ a_{1}, a_{2} \} = \{ a_{2}, a_{1} \}. \]

Esto obedece al principio intuitivo que dice que «un conjunto está determinado por sus elementos». Por ello, un subconjunto de cardinalidad $r$ de $A$ es un ejemplo de una combinación de tamaño $r$ de los objetos en la colección $A$. Así, la cantidad de subconjuntos de cardinalidad $r$ de $A$ es simplemente $C(n,r) = {n \choose r}$.

Por ejemplo, para el conjunto $A = \{ 1, 2, 3, 4, 5 \}$, se cumple que $|A| = 5$. En consecuencia, hay $C(5,2) = {5 \choose 2} = \frac{5!}{(2!)(3!)} = 10$ subconjuntos de cardinalidad $2$ de $A$. Estos son:

\begin{align*} \{1,2\} &\qquad \{2,4\} \\ \{1,3\} &\qquad \{2,5\} \\ \{1,4\} &\qquad \{3,4\} \\ \{1,5\} &\qquad \{3,5\} \\ \{2,3\} &\qquad \{4,5\} \end{align*}

Ejemplo. En un curso de cálculo, la profesora se encuentra redactando el examen final que constará de $10$ preguntas a escoger.

Primero, la profesora decide que las instrucciones digan que escojas cualesquiera $7$ de las $10$ preguntas. Como no importa el orden en el que las respondas, puedes responder el examen de \[ {10 \choose 7} = \frac{10!}{(7!)(3!)} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120 \]maneras distintas.
Sin embargo, la profesora se da cuenta de que quizás sus alumnos tendrán un sesgo por las primeras $5$ preguntas, que son más sencillas. Por ello, decide dividir el examen en dos secciones, cada una con $5$ preguntas. Además, el alumno deberá de escoger $3$ preguntas de la primera sección y $4$ preguntas de la segunda sección. Las $3$ preguntas de la primera sección se pueden escoger de ${5 \choose 3} = 10$ maneras, y las $4$ preguntas de la segunda sección pueden escogerse de ${5 \choose 4} = 5$ maneras. Así, por el principio del producto, el examen puede completarse de ${5 \choose 3}{5 \choose 4} = 10 \cdot 5 = 50$ maneras.
Finalmente, la profesora decide restringir un poco menos las cosas para su grupo, y opta por lo siguiente: para resolver el examen, el alumno debe escoger $7$ preguntas tales que al menos $3$ de ellas vienen de la segunda sección. De esta manera, hay tres casos a considerar:
1. Si el alumno escoge $3$ preguntas de la segunda sección y $4$ preguntas de la primera sección, por el principio del producto hay ${5 \choose 3}{5 \choose 4} = 10 \cdot 5 = 50$ maneras de hacerlo.
2. Por otro lado, si el alumno decide escoger $4$ preguntas de la segunda sección y $3$ preguntas de la primera sección, puede hacerlo de ${5 \choose 4}{5 \choose 3} = 5 \cdot 10 = 50$ maneras.
3. Si decide responder las $5$ preguntas de la segunda sección y $2$ de la primera sección, entonces por el principio del producto, hay ${5 \choose 5}{5 \choose 2} = 1 \dot 10 = 10$ maneras posibles de hacerlo.
  
  Así, combinando los resultados de los tres casos, por el principio de la suma encontramos que el examen puede formar \[ {5 \choose 3}{5 \choose 4} + {5 \choose 4}{5 \choose 3} + {5 \choose 5}{5 \choose 2} = 50 + 50 + 10 = 110 \] combinaciones de $7$ preguntas donde cada combinación incluye al menos $3$ preguntas de la segunda sección.

¡Otra observación importante! – Hay problemas que requieren los conceptos de permutaciones y combinaciones para su resolución. Esto puede observarse en el siguiente ejemplo.

Ejemplo. El número de permutaciones de las letras en la palabra $\mathrm{CHACHALACA}$ es

\begin{align*} \frac{10!}{(4!)(3!)(2!)(1!)} = 12{,}600. \end{align*}

Ahora, ¿cuántas de estas permutaciones no tienen $\mathrm{C}$’s consecutivas? Sin considerar a las $\mathrm{C}$’s, el número de permutaciones de las letras que quedan ($\mathrm{HAHALAA}$) es

\begin{align*} \frac{7!}{(4!)(2!)(1!)} = 105. \end{align*}

Por ejemplo, una de estas $105$ permutaciones es la cadena de letras $\mathrm{LAHAAHA}$. Ahora, podemos acomodar esta permutación como sigue:

\begin{align*} \square \; \mathrm{L} \; \square \; \mathrm{A} \; \square \; \mathrm{H} \; \square \; \mathrm{A} \; \square \; \mathrm{A} \; \square \; \mathrm{H} \; \square \; \mathrm{A} \; \square \end{align*}

Observa que podemos poner las $3$ $\mathrm{C}$’s en cualesquiera de los $8$ espacios en blanco y se cumplirá que no hay $\mathrm{C}$’s consecutivas. Además, $3$ de esos $8$ espacios pueden escogerse de ${8 \choose 3} = 56$ maneras distintas. Esto se puede hacer para cada una de las $105$ permutaciones de las letras $\mathrm{HAHALAA}$, así que por el principio del producto se tienen $105 \cdot 56 = 5{,}880$ permutaciones de las letras en la palabra $\mathrm{CHACHALACA}$ que no tienen $\mathrm{C}$’s consecutivas.

Tarea moral

Sea $X = \{2, 4, 6, 8 \}$. ¿Cuántos subconjuntos de cardinalidad $2$ de $X$ hay?
¿Cómo se relaciona el coeficiente multinomial (visto en la entrada pasada) con el coeficiente binomial? Para verlo, ¿qué pasa cuando sólo se tiene $2$ tipos de objetos en el coeficiente multinomial?
Existen algunos ejercicios geométricos que pueden resolverse con las herramientas de esta entrada. Por ejemplo, considera los puntos $(2,1)$ y $(7,4)$ sobre una cuadrícula y conéctalos con un camino sobre esta, utilizando únicamente movimientos hacia la derecha y hacia arriba. Visualmente:

El anterior es un ejemplo de los muchos caminos posibles. ¿Cuántos caminos posibles existen entre estos dos puntos? Sugerencia: Considera a cada camino como una secuencia (o cadena) de pasos hacia la derecha ($\mathrm{D}$) y hacia arriba ($\mathrm{A}$). Así, el camino mostrado en la gráfica corresponde a la cadena $\mathrm{ADDDAADD}$.

Más adelante…

Con esto damos por terminada la parte del curso que corresponde a los principios de conteo. Sin embargo, hay otros resultados de conteo que no revisamos aquí, como las combinaciones con reemplazo. Por otro lado, es posible que los ejemplos aquí expuestos no sean suficientes para representar todas las complejidades de los problemas de conteo. Por ello, te recomendamos buscar la mayor cantidad de ejemplos de conteo y combinatoria posibles. En particular, puedes revisar el libro que utilizamos como base para esta parte del curso: Discrete And Combinatorial Mathematics: An Applied Introduction (5ta Edición) de Ralph P. Grimaldi, tiene una gran cantidad de ejemplos de todos los temas de conteo vistos (algunos de esos ejemplos los incluímos aquí).

En la siguiente entrada veremos otro de los enfoques más importantes en la historia de la probabilidad: la probabilidad clásica, que está basada en el cálculo de cardinalidades. Como con los enfoques pasados, este enfoque puede representarse de manera formal como una medida de probabilidad.

Entradas relacionadas

Ir a Probabilidad I
Entrada anterior del curso: Principios de Conteo 2 – Permutaciones
Siguiente entrada del curso: La Probabilidad Clásica

Probabilidad I: Principios de Conteo 2 – Permutaciones

Por Octavio Daniel Ríos García

Deja un comentario

Introducción

En la entrada pasada vimos dos principios básicos de conteo: el de la suma y el del producto. En particular, el principio del producto tiene aplicaciones más especializadas. Tal es el caso de las permutaciones y las combinaciones. Dada una colección de objetos, es posible extraer una cantidad fija $k$ de ellos y formar arreglos de tamaño $k$. De estos arreglos puede o no importarnos el orden de los objetos que los forman. Esto da lugar al concepto que veremos en esta entrada: las permutaciones.

Motivación

Comenzaremos con el concepto de permutación. Dada una colección de $n$ objetos, es posible extraer $k$ (con $k \leq n$) de ellos para formar un arreglo lineal. Es decir, se acomodan los elementos en una línea. Lo que nos interesa es ver la cantidad de arreglos lineales de tamaño $k$ que pueden obtenerse de una colección de $n$ objetos. Sin embargo, en un arreglo nos importa el orden en el que se acomodan los objetos. Así, dos arreglos lineales con los mismos elementos pero ordenados de diferente manera se consideran como distintos. Por ello, si queremos la cantidad de arreglos lineales ordenados posibles, estas diferencias se toman en cuenta. Comencemos con un ejemplo.

Ejemplo. En un grupo de $10$ estudiantes, se escoge a $5$ de ellos y se sientan en una fila para una fotografía. ¿Cuántos arreglos lineales pueden formarse?

Como mencionamos anteriormente, la palabra arreglo designa una importancia al orden de los elementos. Si $\mathrm{A}$, $\mathrm{B}$, $\mathrm{C}$, …, $\mathrm{I}$, $\mathrm{J}$ denotan a los $10$ estudiantes, entonces $\mathrm{BCEFI}$, $\mathrm{CEFIB}$ y $\mathrm{ABCFG}$ son tres arreglos lineales distintos. Además, observa que los dos primeros arreglos constan de los mismos $5$ estudiantes, lo que los hace distintos es el orden en el que están acomodados sus elementos.

Ahora, para responder a la pregunta que hicimos, vamos a valernos del principio del producto. Tenemos que considerar las $5$ posiciones (porque estamos tomando $5$ de los $10$ estudiantes que tiene el grupo) y debemos de considerar además cuántos estudiantes hay disponibles para ocupar cada posición.

\[ \underset{\substack{ \phantom{x} \\ \text{1a} \\ \text{Posicion}}}{10} \cdot \underset{\substack{ \phantom{x} \\ \text{2a} \\ \text{Posicion}}}{9} \cdot \underset{\substack{ \phantom{x} \\ \text{3a} \\ \text{Posicion}}}{8} \cdot \underset{\substack{ \phantom{x} \\ \text{4a} \\ \text{Posicion}}}{7} \cdot \underset{\substack{ \phantom{x} \\ \text{5a} \\ \text{Posicion}}}{6} \]

En la 1ᵃ posición puede ir cualquiera de los $10$ estudiantes. No es posible duplicar a los estudiantes, por lo que las repeticiones no son posibles aquí. Por ello, podemos seleccionar únicamente a alguno de los $9$ estudiantes restantes para ocupar la 2ᵃ posición. Similarmente, ahora nos quedan $8$ estudiantes para ocupar la 3ᵃ posición. Continuamos así hasta llegar a que sólo $6$ estudiantes pueden ocupar la 5ᵃ posición. Así, tenemos un total de $30{,}240$ arreglos posibles de $5$ estudiantes tomados del grupo de $10$.

Permutaciones de objetos distintos

Seguramente ya notaste que en este tipo de problemas surgen productos de enteros consecutivos (observa el ejemplo que acabamos de ver, y el ejemplo de las placas de la entrada anterior). En Álgebra Superior I puede que hayas visto el concepto de factorial. Este concepto permite una escritura más sencilla de las operaciones que aparecen en los problemas de conteo. Por ello, lo incluimos como recordatorio:

Recordatorio. Sea $n \in \mathbb{N}$. Se define el número $n$ factorial (denotado por $n!$) como sigue:

\begin{align*} 0! &= 1, \\ n! &= (n)(n − 1)(n − 2) \cdots (3)(2)(1), & \text{para $n \geq 1$}. \end{align*}

Así, se puede observar que

\begin{align*} 1! &= 1, \\ 2! &= 2 \cdot 1 = 2, \\ 3! &= 3 \cdot 2 \cdot 1 = 6, \\ 4! &= 4 \cdot 3 \cdot 2 \cdot 1 = 24, \\ 5! &= 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120. \\ \end{align*}

Además, para cualquier $n \in \mathbb{N}$ se cumple que $(n + 1)! = (n+1)(n!)$.

Utilizando la notación del factorial podemos simplificar el resultado obtenido en el último ejemplo.

\begin{align*} 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 = 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot \frac{5 \cdot 4 \cdot 3 \cdot 2\cdot 1}{5 \cdot 4 \cdot 3 \cdot 2\cdot 1} = \frac{10!}{5!}. \end{align*}

Esto es, al dividir $10!$ entre $5!$ se cancelan los últimos términos de $10!$. Efectivamente, la expresión resultante coincide con lo que obtuvimos en el ejemplo.

Definición 1.18. Dada una colección de $n$ objetos distintos, cualquer arreglo lineal formado con estos objetos es llamado una permutación de la colección.

Por ejemplo, si tenemos las letras $\mathrm{a}$, $\mathrm{b}$ y $\mathrm{c}$, hay $6$ maneras de acomodar (o permutar) estas letras: $\mathrm{abc}$, $\mathrm{acb}$, $\mathrm{bac}$, $\mathrm{bca}$, $\mathrm{cab}$ y $\mathrm{cba}$. Por otro lado, si nos interesa tomar arreglos de $2$ letras, entonces hay $6$ permutaciones de tamaño $2$ de la colección: $\mathrm{ab}$, $\mathrm{ac}$, $\mathrm{ba}$, $\mathrm{bc}$, $\mathrm{ca}$ y $\mathrm{cb}$.

Principio de las permutaciones. Sean $n, r \in \mathbb{N}$ tales que $1 \leq r \leq n$. Si tenemos $n$ objetos distintos, entonces por la regla del producto, el número de permutaciones de tamaño $r$ de los $n$ objetos es

\begin{align*} P(n,r) &= \underset{\substack{ \phantom{x} \\ \text{1a} \\ \text{Posicion}}}{(n)} \cdot \underset{\substack{ \phantom{x} \\ \text{2a} \\ \text{Posicion}}}{(n − 1)} \cdot \underset{\substack{ \phantom{x} \\ \text{3a} \\ \text{Posicion}}}{(n − 2)} \cdots \underset{\substack{ \phantom{x} \\ \text{$r$-esima} \\ \text{Posicion}}}{(n − r + 1)} \\ &= (n)(n−1)(n−2) \cdots (n−r+1) \cdot \frac{(n−r)(n−r−1) \cdots (3)(2)(1)}{(n−r)(n−r−1) \cdots (3)(2)(1)} \\ &= \frac{n!}{(n−r)!}. \end{align*}

Como mencionamos previamente, aplicamos el principio del producto para determinar el número de permutaciones que pueden hacerse a partir de una colección dada.

Algunas propiedades importantes que observar.

Cuando $r = 0$, $P(n, 0) = 1 = \frac{n!}{(n−0)!}$, por lo que $P(n, r)$ está bien definido incluso para $r = 0$.
Al permutar todos los $n$ objetos de la colección, se tiene $r = n$. Por ello, $P(n,n) = \frac{n!}{0!} = n!$ es el número de permutaciones posibles de todos los objetos de la colección.
Es importante notar que el número de permutaciones de tamaño $r$ de una colección de $n$ objetos es un resultado del principio del producto cuando no permitimos repetición. En consecuencia, $P(n,r)$ es el número de arreglos lineales de tamaño $r$ en los que no se permiten repeticiones. Sin embargo, cuando sí permitimos las repeticiones, por el principio del producto hay $n^{r}$ arreglos lineales posibles.

Ejemplo. El número de permutaciones de las letras en la palabra $\mathrm{CARMESI}$ es $7!$, pues todas las letras son distintas entre sí. Si queremos formar permutaciones de tamaño $4$, entonces el número de permutaciones de tamaño $4$ es $P(7,4) = \frac{7!}{(7 − 4)!} = \frac{7!}{3!} = 840$. Por otro lado, si permitimos repeticiones de letras, entonces el número de cadenas de $11$ letras que podemos formar es $7^{11} = 1{,}977{,}326{,}743$.

Permutaciones con objetos repetidos

Ejemplo. ¿Qué pasa cuando nuestra colección tiene objetos repetidos o indistinguibles? Por ejemplo, ¿cuál es el número de permutaciones de las $4$ letras en la palabra $\mathrm{PALA}$? En este caso, la letra $\mathrm{A}$ se repite. Veamos cómo se ven todas las permutaciones de estas letras.

Tabla de Arreglos
$\mathrm{A \, A \, L \, P}$	$\mathrm{A_{1} \, A_{2} \, L \, P}$	$\mathrm{A_{2} \, A_{1} \, L \, P}$
$\mathrm{A \, A \, P \, L}$	$\mathrm{A_{1} \, A_{2} \, P \, L}$	$\mathrm{A_{2} \, A_{1} \, P \, L}$
$\mathrm{A \, L \, A \, P}$	$\mathrm{A_{1} \, L \, A_{2} \, P}$	$\mathrm{A_{2} \, L \, A_{1} \, P}$
$\mathrm{A L \, P \, A}$	$\mathrm{A_{1} \, L \, P \, A_{2}}$	$\mathrm{A_{2} \, L \, P \, A_{1}}$
$\mathrm{A \, P \, A \, L}$	$\mathrm{A_{1} \, P \, A_{2} \, L}$	$\mathrm{A_{2} \, P \, A_{1} \, L}$
$\mathrm{A \, P \, L \, A}$	$\mathrm{A_{1} \, P \, L \, A_{2}}$	$\mathrm{A_{2} \, P \, L \, A_{1}}$
$\mathrm{L \, A \, A \, P}$	$\mathrm{L \, A_{1} \, A_{2} \, P}$	$\mathrm{L \, A_{2} \, A_{1} \, P}$
$\mathrm{L \, A \, P \, A}$	$\mathrm{L \, A_{1} \, P \, A_{2}}$	$\mathrm{L \, A_{2} \, P \, A_{1}}$
$\mathrm{L \, P \, A \, A}$	$\mathrm{L \, P \, A_{1} \, A_{2}}$	$\mathrm{L \, P \, A_{2} \, A_{1}}$
$\mathrm{P \, A \, A \, L}$	$\mathrm{P \, A_{1} \, A _{2}\, L}$	$\mathrm{P \, A_{2} \, A _{1}\, L}$
$\mathrm{P \, A \, L \, A}$	$\mathrm{P \, A_{1} \, L \, A_{2}}$	$\mathrm{P \, A_{2} \, L \, A_{1}}$
$\mathrm{P \, L \, A \, A}$	$\mathrm{P \, L \, A_{1} \, A_{2}}$	$\mathrm{P \, L \, A_{2} \, A_{1}}$
(a)	(b)

En la tabla de la izquierda (a) pusimos todos los arreglos distintos que se pueden formar con las letras que tenemos. Por otro lado, si distinguimos a las dos letras $\mathrm{A}$ como $\mathrm{A_{1}}$ y $\mathrm{A_{2}}$, nuestra colección se vuelve una colección de objetos distintos. Así, en la tabla de la derecha (b) pusimos todos los arreglos con las letras de la palabra $\mathrm{PA_{1}LA_{2}}$. En este caso sí sabemos calcular el número de permutaciones posibles, es $P(4,4) = 4! = 24$. La tabla revela que para cada arreglo en el que las $\mathrm{A}$’s son indistinguibles le corresponden dos permutaciones con $\mathrm{A}$’s distintas. En consecuencia,

\begin{align*} 2 \cdot (\text{Arreglos distintos con las letras $\mathrm{P}$, $\mathrm{A}$, $\mathrm{L}$, $\mathrm{A}$}) = (\text{Permutaciones de los simbolos $\mathrm{P}$, $\mathrm{A_{1}}$, $\mathrm{L}$, $\mathrm{A_{2}}$}), \end{align*}

por lo que la respuesta a nuestra pregunta original de encontrar todas las permutaciones de las $4$ letras en la palabra $\mathrm{PALA}$ es $\frac{4!}{2} = 12$.

Ejemplo. Usando la misma idea que desarrollamos en el ejemplo anterior, considera ahora las permutaciones de las $9$ letras de la palabra $\mathrm{COCODRILO}$.

Primero, observa que hay $3! = 6$ maneras de acomodar a las $\mathrm{O}$’s distinguidas por cada arreglo en el que las $\mathrm{O}$’s no están distinguidas. Por ejemplo, observa la siguiente tabla:

Tabla de arreglos
$\mathrm{C \, O \, C \, O \, D \, R \, I \, L \, O}$	$\mathrm{C \, O_{1} \, C \, O_{2} \, D \, R \, I \, L \, O_{3}}$
	$\mathrm{C \, O_{1} \, C \, O_{3} \, D \, R \, I \, L \, O_{2}}$
	$\mathrm{C \, O_{2} \, C \, O_{1} \, D \, R \, I \, L \, O_{3}}$
	$\mathrm{C \, O_{2} \, C \, O_{3} \, D \, R \, I \, L \, O_{1}}$
	$\mathrm{C \, O_{3} \, C \, O_{1} \, D \, R \, I \, L \, O_{2}}$
	$\mathrm{C \, O_{3} \, C \, O_{2} \, D \, R \, I \, L \, O_{1}}$
(a) Arreglo sin distinguir las $\mathrm{O}$’s.	(b) Arreglos distinguendo a las tres letras $\mathrm{O}$.

Por cada permutación de las letras en la palabra $\mathrm{COCODRILO}$ sin distinguir a las $\mathrm{O}$’s, hay $3$ espacios ocupados por letras $\mathrm{O}$. Por ello, al distinguir a cada una, estamos permutando esas $3$ $\mathrm{O}$’s, que pueden acomodarse de $P(3,3) = 3! = 6$ maneras. Por otro lado, lo mismo pasa con las $\mathrm{C}$’s. En este caso, hay $2!$ maneras de acomodar las $\mathrm{C}$’s distinguidas por cada arreglo sin distinguir las $\mathrm{C}$’s. Por lo tanto, se tiene que

\begin{align*} (3!)(2!)(\text{Arreglos distintos con las letras en $\mathrm{COCODRILO}$}) = (\text{Permutaciones de los simbolos $\mathrm{C}_{2}$, $\mathrm{O_{1}}$, $\mathrm{C}_{2}$, $\mathrm{O_{2}}$, $\mathrm{D}$, $\mathrm{R}$, $\mathrm{I}$, $\mathrm{L}$, $\mathrm{O_{3}}$}), \end{align*}

así que el número de arreglos distintos de las $9$ letras en $\mathrm{COCODRILO}$ es $\frac{9!}{(3!)(2!)} = 30{,}240$.

Podemos enunciar un principio general para arreglos con objetos que se repiten siguiendo la idea desarrollada en los últimos ejemplos.

Permutaciones con objetos repetidos. Si tenemos una colección de $n$ objetos y dentro de esta colección tenemos $n_{1}$ objetos indistinguibles de un $1$er tipo, $n_{2}$ objetos indistinguibles de un $2$do tipo, …, y $n_{r}$ objetos indistinguibles de un $r$-ésimo tipo, de tal manera que

\[ n_{1} + n_{2} + \cdots + n_{r} = n, \]

entonces la cantidad de permutaciones de los $n$ objetos dados es

\[\frac{n!}{(n_{1}!)(n_{2}!) \cdots (n_{r}!)}. \]

Este valor es conocido como el coeficiente multinomial de $n_{1}$, $n_{2}$, …, $n_{r}$.

Ejemplo. La ciudad de $\mathrm{CONSTANTINOPLA}$ fue la ciudad capital del imperio bizantino entre los años 395 y 1204. Podemos aplicar el último principio de conteo que desarrollamos para encontrar la cantidad de permutaciones de las letras en la palabra $\mathrm{CONSTANTINOPLA}$.

Para ello, primero hay que encontrar cuántas letras distintas tiene. Observa que en total tiene $9$ letras distintas. En consecuencia, podemos pensar de cada letra distinta como un tipo de objeto. Así, tenemos $9$ tipos de objetos en la colección, y hay que contar cuántos objetos de cada tipo hay. Esto lo podemos ver en la siguiente tabla.

Tipo	Letra	Número de letras de ese tipo
$1$	$\mathrm{A}$	$n_{1} = 2$
$2$	$\mathrm{C}$	$n_{2} = 1$
$3$	$\mathrm{I}$	$n_{3} = 1$
$4$	$\mathrm{L}$	$n_{4} = 1$
$5$	$\mathrm{N}$	$n_{5} = 3$
$6$	$\mathrm{O}$	$n_{6} = 2$
$7$	$\mathrm{P}$	$n_{7} = 1$
$8$	$\mathrm{S}$	$n_{8} = 1$
$9$	$\mathrm{T}$	$n_{9} = 2$

Además, el número de letras en $\mathrm{CONSTANTINOPLA}$ es $14$, precisamente el resultado de sumar todos los $n_{i}$. Así, obtenemos que la cantidad de premutaciones posibles de las letras en $\mathrm{CONSTANTINOPLA}$ es

\[ \frac{14!}{(2!)(1!)(1!)(1!)(3!)(2!)(1!)(1!)(2!)} = \frac{14!}{(2!)(3!)(2!)(2!)} = 1{,}816{,}214{,}400. \]

Otra pregunta que podemos resolver es, ¿cuántas permutaciones tienen a las $3$ $\mathrm{N}$’s juntas? Para verlo, podemos pensar en que la cadena de letras $\mathrm{NNN}$ es un solo símbolo, y partir de la colección de símbolos $\mathrm{A}$, $\mathrm{A}$, $\mathrm{C}$, $\mathrm{I}$, $\mathrm{L}$, $\mathrm{NNN}$ (como un solo símbolo), $\mathrm{O}$, $\mathrm{O}$, $\mathrm{P}$, $\mathrm{S}$, $\mathrm{T}$, $\mathrm{T}$, y hacer lo mismo. Así, el número de permutaciones que tiene a las $3$ $\mathrm{N}$’s juntas es

\[ \frac{12!}{(2!)(1!)(1!)(1!)(1!)(2!)(1!)(1!)(2!)} = \frac{12!}{(2!)(2!)(2!)} = 59{,}875{,}200. \]

Tarea moral

¿Cuántas permutaciones de los dígitos $0$, $1$, $2$, …, $9$ hay cuyo primer dígito es $3$ o cuyo último dígito es $7$?
Encuentra el número de permutaciones de la palabra $\mathrm{MISSISSIPPI}$.
¿Cuántas cadenas de $13$ símbolos pueden hacerse con $6$ estrellas $*$ y $7$ barras $|$? Por ejemplo:\[ |*|*|***|*|||, \qquad ******|||||||, \qquad |*|*|*|*|*|*|. \]

Más adelante…

En la siguiente entrada continuaremos con nuestro estudio de los principios de conteo. El siguiente concepto será el de combinación, que se deriva del concepto de permutación, siendo la combinación un concepto un poco más especializado.

Por otro lado, el concepto de permutación con objetos repetidos te será de utilidad en el curso de Probabilidad II para algo que se conoce como la distribución multinomial. Cuando veamos lo que son las variables aleatorias y las funciones de distribución te quedará claro a qué nos referimos por «distribución multinomial».

Entradas relacionadas

Ir a Probabilidad I
Entrada anterior del curso: Principios de Conteo 1 – Suma y Producto
Siguiente entrada del curso: Principios de Conteo 3 – Combinaciones

Probabilidad I: Principios de Conteo 1 – Suma y Producto

Por Octavio Daniel Ríos García

Deja un comentario

Introducción

En la entrada anterior abordamos el enfoque frecuentista de la probabilidad. El siguiente enfoque que veremos requiere de algunas herramientas adicionales. Por ello, el propósito de esta sección es hacer todos los preparativos para estudiar la siguiente medida de probabilidad importante: la probabilidad clásica. Este último enfoque se utiliza para el caso en el que $\Omega$, el espacio muestral, es finito, y se basa en la cardinalidad de $\Omega$ y la de sus subconjuntos. En consecuencia, es necesario que sepas contar la cantidad de elementos que tiene cualquier subconjunto de $\Omega$ que se te pida.

No demostraremos la validez de las propiedades para conjuntos en esta entrada, pues se trata de propiedades de conjuntos finitos. Por ello, puedes consultar nuestras notas de Álgebra Superior I en caso de que las necesites. Esta parte del curso está basada principalmente en el primer capítulo del libro Discrete and Combinatorial Mathematics: An Applied Introduction (5ᵃ edición) de Ralph P. Grimaldi.

El principio de conteo de la suma

Comenzaremos enunciando algunos principios de conteo asociados a la realización de tareas. Estos principios pueden expresarse en términos de cardinalidades de conjuntos.

Principio de la suma. Si una tarea puede realizarse de $m$ formas distintas, y otra tarea puede realizarse de $n$ formas distintas, y las dos tareas no se pueden hacer simultáneamente, entonces se puede realizar alguna de las dos tareas de $m + n$ maneras distintas.

En términos de conjuntos. Si $A$, $B$ son conjuntos finitos tales que $A \cap B = \emptyset$, entonces

\[ | A \cup B | = |A| + |B|. \]

Donde $|A|$ es la cardinalidad (número de elementos) del conjunto $A$.

Ejemplo. En la biblioteca de la Facultad de Ciencias hay $25$ libros sobre probabilidad y $15$ libros sobre álgebra moderna. Así, por el principio de la suma, un alumno de la Facultad de Ciencias puede elegir de entre $25 + 15 = 40$ libros para aprender sobre cualquiera de estos dos temas.

El principio de la suma puede extenderse a más de dos tareas, siempre y cuando se cumpla que ningún par de tareas pueda ocurrir simultáneamente. En términos de conjuntos, se tiene que para cualesquiera $A_{1}$, $A_{2}$, …, $A_{k}$ conjuntos que son ajenos dos a dos. Entonces se cumple que

\[ {\left| \bigcup_{i=1}^{k} A_{i} \right|} = \sum_{i=1}^{k} |A_{i}| \]

Precisamente, que los conjuntos sean ajenos dos a dos se interpreta como que ningún par de tareas puede realizarse simultáneamente.

Ejemplo. En la sección de ciencias de la computación de la biblioteca de la Facultad de Ciencias de la UNAM hay $7$ libros sobre C++, $6$ libros sobre Java, y $5$ libros sobre Python. En consecuencia, por el principio de la suma, una alumna de la facultad de ciencias tiene $7+6+5=18$ libros a elegir para comenzar a aprender algún lenguaje de programación.

También podemos precisar qué ocurre cuando $A$ y $B$ son finitos y no son ajenos. Primero, veamos cuando $B \subseteq A$. Como $B \subseteq A$, se cumple que $A = B \cup (A \smallsetminus B)$. Observa que $B$ y $A \smallsetminus B$ son conjuntos ajenos, por lo que

\[ |A| = |B \cup (A \smallsetminus B)| = |B| + |A \smallsetminus B|. \]

Y como la cardinalidad de un conjunto finito es un número natural, se tiene que $|B| \leq |A|$. En conclusión, si $A \subseteq B$, entonces $|B| \leq |A|$. Ahora, sabemos que para cualesquiera conjuntos finitos $A$ y $B$, los conjuntos $A$ y $B \smallsetminus A$ son ajenos, y que $A \cup B = A \cup (B \smallsetminus A)$, por lo que

\[ |A \cup B| = |A \cup (B \smallsetminus A)| = |A| + |B \smallsetminus A|, \]

y como $B \smallsetminus A \subseteq B$, se tiene que $|B\smallsetminus A| \leq |B|$, y así

\[ |A \cup B| = |A| + |B \smallsetminus A| \leq |A| + |B|. \]

En conclusión, la cardinalidad es subaditiva. De hecho, esta última propiedad se cumple para cualquier $n \in \mathbb{N}^{+}$ y cualesquiera $A_{1}$, $A_{2}$, …, $A_{n}$ conjuntos finitos:

\[ {\left| \bigcup_{i=1}^{n} A_{i} \right|} \leq \sum_{i=1}^{n} |A_{i}|. \]

Ejemplo. Una profesora de la facultad de ciencias tiene $8$ libros sobre Probabilidad en su colección, mientras que uno de sus colegas tiene $5$. Si denotamos por $m$ al número de libros diferentes sobre Probabilidad que tienen en su posesión, se cumple que

\[ 8 \leq m \leq 13, \]

pues $m$ será $8$ si el colega de la profesora tiene los mismos libros que ella (y así, el número de libros distintos que tienen en su posesión es $8$). Por otro lado, por el principio de la suma, $m$ puede tomar un valor máximo de $8 + 5 = 13$ en el caso de que los libros de la profesora y de su colega son todos distintos.

En la entrada de propiedades de una medida de probabilidad vimos un resultado conocido como el principio de inclusión-exclusión. Resulta que este principio es cierto también para la cardinalidad de conjuntos finitos. Es decir, que para cualesquiera $A$ y $B$ conjuntos finitos se cumple que

\[ |A \cup B| = |A| + |B|− |A \cap B|. \]

Más aún, para cualquier $n \in \mathbb{N}^{+}$ y cualesquiera $A_{1}$, $A_{2}$, …, $A_{n}$ conjuntos finitos se cumple que

\[ {\left| \bigcup_{i=1}^{n} A_{i} \right|} = \sum_{i=1}^{n}|A_{i}| − \sum_{i<j}|A_{i} \cap A_{j}| + \sum_{i<j<k} |A_{i} \cap A_{j} \cap A_{k}| − \cdots + (-1)^{n+1}{\left|\bigcap_{i=1}^{n} A_{i} \right|}. \]

Por ejemplo, para $n=3$ y para cualesquiera $A_{1}$, $A_{2}$, $A_{3}$ conjuntos finitos, se tiene que

\[ |A_{1} \cup A_{2} \cup A_{3}| = |A_{1}| + |A_{2}| + |A_{3}| − |A_{1} \cap A_{2}| − |A_{1} \cap A_{3}| − |A_{2} \cap A_{3}| + |A_{1} \cap A_{2} \cap A_{3}|. \]

Ejemplo. Le pedimos a tres aficionados al rock progresivo que nos dijeran sus $5$ bandas favoritas de este género musical. Sus listas son las siguientes:

Aficionado 1 ($A_{1}$)

Pink Floyd.
Genesis.
Marillion.
Rush.
Riverside.

Aficionado 2 ($A_{2}$)

King Crimson.
Yes.
Genesis.
Rush.
Pink Floyd.

Aficionado 3 ($A_{3}$)

Jethro Tull.
King Crimson.
Änglagård.
Anekdoten.
Yes.

Si decides escoger una banda de las que mencionaron estas tres personas, ¿cuántas opciones distintas existen? En otras palabras, ¿cuál es la cardinalidad de $A_{1} \cup A_{2} \cup A_{3}$? Para verlo, podemos valernos del principio de inclusión-exclusión. Primero, veamos los elementos que tienen en común las listas al compararlas dos a dos:

$A_{1} \cap A_{2}$

Pink Floyd.
Genesis.
Rush.

$A_{1} \cap A_{3}$

No tienen elementos en común.

$A_{2} \cap A_{3}$

King Crimson.
Yes.

En consecuencia, $|A_{1} \cap A_{2}| = 3$, $|A_{1} \cap A_{3}| = 0$ y $|A_{2} \cap A_{3}| = 2$. Luego, observa que no hay elementos en común entre las tres listas, por lo que $|A_{1} \cap A_{2} \cap A_{3}| = 0$. Entonces tenemos que

\begin{align*} |A_{1} \cup A_{2} \cup A_{3}| &= |A_{1}| + |A_{2}| + |A_{3}| − |A_{1} \cap A_{2}| − |A_{1} \cap A_{3}| − |A_{2} \cap A_{3}| + |A_{1} \cap A_{2} \cap A_{3}| \\ &= 5 + 5 + 5 − 3 − 0 − 2 + 0 \\ &= 15 − 5 \\ &= 10. \end{align*}

Por lo tanto, existen $10$ opciones distintas a elegir entre las bandas que mencionaron las tres personas.

El principio de conteo del producto

Ahora, ¿qué pasa cuando tenemos dos tareas y queremos hacerlas de forma consecutiva, en orden? Por ejemplo, imagina que tienes $3$ camisas distintas y $4$ pantalones distintos. ¿De cuántas maneras posibles puedes ponerte primero una camisa y luego un pantalón? Por cada una de las $3$ de camisas habrá $4$ pantalones distintos a escoger.

**Figura.** Figura que ilustra las maneras posibles de ponerte primero una de las $3$ camisas y luego uno de los $4$ pantalones.

En consecuencia, a la primera camisa le corresponden $4$ pantalones, a la segunda también, y a la tercera lo mismo. Por ello, el número de maneras posibles de ponerte primero una camisa y luego un pantalón serían $4 + 4 + 4 = 3 \cdot 4 = 12$.

Podemos verlo en términos de conjuntos. Sean $C = \{ c_{1}, c_{2}, c_{3} \}$ el conjunto de las camisas y $P = \{ p_{1}, p_{2}, p_{3}, p_{4} \}$ el conjunto de los pantalones. Podemos representar la idea de tomar primero una camisa y luego un pantalón a través del producto cartesiano de estos dos conjuntos:

\begin{align} C \times D = \begin{Bmatrix} (c_1,p_1), & (c_1, p_2), & (c_1, p_3), & (c_1, p_4) \\ (c_2,p_1), & (c_2, p_2), & (c_2, p_3), & (c_2, p_4) \\ (c_3,p_1), & (c_3, p_2), & (c_3, p_3), & (c_3, p_4) \end{Bmatrix}, \end{align}

observa que cada par ordenado representa cada una de las combinaciones de camisa y pantalón que puedes escoger. Por ello, $|C \times D|$ es el número total de combinaciones de camisa y pantalón posibles, que resulta ser $|C \times D| = |C||D| = 3 \cdot 4 = 12$. Además, observa que $C \times D$ representa precisamente la idea de que primero se escoge una camisa, y en segundo lugar se escoge el pantalón. Por otro lado, el conjunto $D \times C$ representa la idea de escoger primero el pantalón y después la camisa. Observa que esto no afecta el número total de combinaciones posibles.

La discusión anterior da lugar a nuestro segundo principio básico de conteo.

Principio del producto. Si una tarea puede dividirse en dos etapas y hay $m$ resultados posibles para la primera etapa y para cada una de estas etapas hay $n$ resultados posibles para la segunda etapa, entonces la tarea puede ser realizada, en el orden acordado, de $m n$ maneras distintas.

En términos de conjuntos. Para cualesquiera $A$ y $B$ conjuntos finitos se cumple que

\[ |A \times B| = |A||B|. \]

Ejemplo. Se lanzan dos dados distintos sobre una mesa. El primero tiene $6$ caras, y el segundo tiene $8$ caras. En consecuencia, esta actividad tiene $6 \cdot 8 = 48$ resultados posibles.

Ejemplo. El principio del producto puede extenderse a más de dos etapas en una misma tarea. Por ejemplo, considera la manufactura de placas para automóviles que consisten de $2$ letras seguidas de $4$ dígitos.

**Figura.** Ejemplo de placa de acuerdo con lo anterior. Esta placa consiste de la cadena de letras y dígitos $\textrm{A}\textrm{A}0000$.

Si no ponemos restricciones a la combinación de caracteres que lleva cada placa, entonces hay $26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 \cdot 10 = 6{,}760{,}000$ placas posibles, pues hay $26$ letras en el alfabeto (sin considerar a la ‘ñ’) y $10$ dígitos del $0$ al $9$.
Podemos restringir las combinaciones que admitimos en una placa. Si no permitimos que tenga letras repetidas, entonces la parte que corresponde a las letras tiene $26 \cdot 25$ combinaciones posibles. ¿Por qué $26 \cdot 25$ y no $26 \cdot 26$ como en el caso anterior? Precisamente porque al escoger la primera letra, la segunda no puede ser la misma, por lo que sólamente se puede escoger alguna de las $25$ restantes, que son distintas de la que ya se escogió. En consecuencia, hay $26 \cdot 25 \cdot 10 \cdot 10 \cdot 10 \cdot 10 = 6{,}500{,}000$ combinaciones de letras y dígitos en los que no se repiten las letras.
Por otro lado, ¿cuántas placas hay sin dígitos repetidos? En este caso, sí permitimos que las letras se repitan, así que la parte correspondiente a las letras es $26 \cdot 26$. Por otro lado, en los dígitos, queremos que no haya dígitos repetidos, así que el número de cadenas de dígitos admisibles es $10 \cdot 9 \cdot 8 \cdot 7$. Esto se debe a que para el primer dígito se tienen $10$ opciones para escoger. Luego, al haber fijado el primero, el segundo está limitado a no ser el mismo que el primero, por lo que se puede escoger alguno de $9$ dígitos restantes. Después, el tercer dígito debe de ser distinto de los dos primeros, por lo que se escoge alguno de $8$ dígitos restantes. Finalmente, el cuarto dígito debe de ser distinto de los otros tres, por lo que se debe de escoger alguno de $7$ dígitos que quedan. En conclusión, hay $26 \cdot 26 \cdot 10 \cdot 9 \cdot 8 \cdot 7 = 3{,}407{,}040$ placas en las que los dígitos son todos distintos.
Por último, ¿cuántas placas hay sin repeticiones? Es decir, que ninguno de los símbolos (letras o dígitos) se repite. En este caso, se tienen $26 \cdot 25 \cdot 10 \cdot 9 \cdot 8 \cdot 7 = 3{,}276{,}000$ placas posibles en las que no hay repeticiones de ningún tipo.

Ejemplo. Para guardar información, la memoria principal de una computadora contiene una colección grande de circuitos, cada uno de los cuales es capaz de almacenar un bit. Esto es, alguno de los dígitos binarios (binary digits) $0$ o $1$. Toda la información que se almacena en una computadora consiste de colecciones muy grandes de bits. Por ejemplo, los colores y las imágenes son comúnmente almacenados en forma de arreglos de bits. En el caso de las imágenes, formatos como el PNG (Portable Network Graphics) y el BMP (bitmap, «mapa de bits») son ejemplos de formatos de imagen que consisten de matrices de pequeños cuadraditos de colores llamados pixeles.

**Figura.** Ejemplo de una imagen digital, que consiste de una matriz de **pixeles**. Al hacer zoom se aprecian claramente los pixeles que constituyen a la imagen.

Aunado a esto, cada uno de los pixeles tiene un color, el cual es representado a través de un arreglo de bits. Uno de los modelos de color más utilizados en los dispositivos digitales es el modelo RGB (Red Green Blue), que combina los colores primarios rojo, verde y azul para obtener otros colores.

Sin embargo, una computadora tiene acceso a una cantidad limitada de espacios de memoria, por lo que no podemos representar todos los colores visibles. Por ello, hacemos lo posible por representar la mayor cantidad posible de colores con los recursos disponibles para la computadora. Antiguamente, las computadoras y las consolas de videojuegos tenían una cantidad muy limitada de recursos. En consecuencia, dedican una cantidad fija de bits al color. Esta cantidad es conocida como la profundidad de color. Por ejemplo, en la siguiente imagen se muestran todos los colores posibles en una profundidad de color de $6$-bits.

**Figura.** Todos los colores posibles que se obtienen con una profundidad de color de $6$ bits. A cada color primario se le dedican $2$ bits.

A cada color primario se le dedican $2$ bits, es decir, dos «casillas» en las que puede ir un $0$ o un $1$. Así, en cada «casilla» hay $2$ opciones a escoger, por lo que una cadena de $2$ bits tiene $2 \cdot 2 = 4$ combinaciones posibles de $0$’s o $1$’s.

Bit 1	Bit 2
$0$	$0$
$0$	$1$
$1$	$0$
$1$	$1$

En la tabla anterior se ilustran todos los valores que puede tomar la lista de $2$ bits que se asigna a cada color: $00$, $01$, $10$ y $11$. Estos valores pueden pensarse como cifras en sistema binario. Así, $00_{2}$ es $0$, $01_{2}$ es $1$, $10_{2}$ es $2$ y $11_{2}$ es $3$. A cada color primario le corresponde un par de bits que representa la intensidad de rojo, verde y azul que contiene un color compuesto dado. Estos valores se combinan entre sí de manera aditiva. Por ejemplo, tener los valores $01$ en rojo, $00$ en verde y $10$ en azul resulta en un color morado como se muestra en la siguiente figura.

**Figura.** La cadena de dígitos $\textcolor{red}{01}\textcolor{green}{00}\textcolor{blue}{10}$ resulta en este color **morado**.

En conclusión, cuando la profundidad de color es de $6$ bits se tiene un total de $(2^2) \cdot (2^2) \cdot (2^2) = 64$ colores disponibles. Para ilustrar lo limitada que resulta esa cantidad, observa la siguiente imagen.

**Figura.** Una fotografía del castillo de Lichtenstein. A la derecha se muestra una rendición de la misma fotografía utilizando nuestros $64$ colores disponibles.

Es por esto que las computadoras y consolas de videojuegos más antiguas tienen ese característico estilo de gráficos pixelados, pues sus capacidades de procesamiento eran tan limitadas que debían de limitar la cantidad de colores que podían presentar en la pantalla o televisión.

Para que te des una idea de cuánto ha avanzado la tecnología, prácticamente cualquier computadora y celular en la actualidad tiene una profunidad de color de $24$ bits, con $8$ bits dedicados a cada color primario. Esto es, se tienen disponibles $(2^8) \cdot (2^8) \cdot (2^8) = 16{,}777{,}216$ colores distintos para escoger.

Tarea moral

En una heladería se venden $7$ sabores de helado distintos. A unas cuadras de distancia, hay otra heladería más grande que vende $12$ sabores de helado.
1. Asumiendo que los sabores de helado que ofrecen ambas heladerías son todos distintos, ¿cuántos sabores distintos tienes para escoger?
2. Si no sabes los sabores que ofrecen ambas heladerías, sea $h$ el número de sabores distintos que se ofrecen en ambas heladerías. ¿Entre qué valores se encuentra $h$?
Retoma el ejemplo de las placas con $2$ letras y $4$ dígitos.
1. Si permitimos repeticiones, ¿cuántas placas tienen únicamente vocales (A, E, I, O, U) y dígitos pares?
2. Y si no permitimos repeticiones, ¿cuántas placas tienen únicamente vocales (A, E, I, O, U) y dígitos pares?
El SNES (Super Nintendo Entertainment System) es una consola muy antigua que posee una profundidad de color de $15$-bits ($5$ bits para cada color primario). ¿Cuántos colores disponibles tiene esta consola?

Más adelante…

En la siguiente entrada abordaremos otras herramientas de conteo, las permutaciones y las combinaciones. Estos nuevos conceptos son resultados que se derivan a partir del principio del producto. Por ello, es recomendable que te quede bien claro este último principio.

Los dos principios vistos en esta entrada son fundamentales para el estudio de la probabilidad clásica. En particular, el principio del producto será de gran utilidad para calcular la cardinalidad de los espacios muestrales de los experimentos aleatorios que veremos en esta parte.

Entradas relacionadas

Ir a Probabilidad I
Entrada anterior del curso: El Enfoque Frecuentista
Siguiente entrada del curso: Principios de Conteo 2 – Permutaciones

Seminario de Resolución de Problemas: Sucesiones recursivas y recursiones lineales

Por Leonardo Ignacio Martínez Sandoval

Deja un comentario

Introducción

En esta entrada estudiaremos aquellas sucesiones en las que un término está definido mediante términos anteriores. Estas son las sucesiones recursivas. Dentro de ellas hay unas muy especiales, que son las que satisfacen una recursión lineal. También hablaremos de eso.

En entradas anteriores ya hemos visto ejemplos de sucesiones recursivas. Por un lado, las sucesiones aritméticas y geométricas cumplen una recursión sencilla. Las sucesiones periódicas también se pueden poner en términos de una recursión.

Vimos otros ejemplos en la entrada de sucesiones monótonas y acotadas, en donde la recursion nos ayuda a demostrar algunas de estas propiedades.

Sucesiones recursivas

Una sucesión recursiva es una sucesión $\{x_n\}$ en la que, intuitivamente, cada término depende de los anteriores. La regla que dice cómo está relacionado cada término con los de antes le llamamos la regla o fórmula recursiva. Usualmente los primeros términos de la sucesión están dados, y se les conoce como los términos iniciales.

Las sucesiones aritméticas son recursivas. Si $\{x_n\}$ es aritmética de término inicial $a$ y diferencia $d$, se comienza con $x_0=a$ y para $n\geq 0$ se satisface la recursión $x_{n+1}=x_n+d$. Similarmente, una sucesión geométrica $\{y_n\}$ de término inicial $s$ y razón $r$ se puede poner en términos recursivos: $y_0=s$ y para $n\geq 0$, se tiene $y_{n+1}=ry_n$.

Una sucesión periódica $\{z_n\}$ de periodo $p$ también satisface una recursión. Los términos iniciales $z_0,\ldots,z_{p-1}$ están dados y para $n\geq 0$ se tiene que $z_{n+p}=z_n$.

Las sucesiones recursivas pueden aparecer como parte del enunciado de un problema, o bien pueden aparecer de manera natural como parte de la solución de un problema.

Problema. Para un triángulo $T$ del plano se define otro triángulo $f(T)$ como sigue:

Se nombran los vértices $A,B,C$ de modo que $|BC|\leq |AC|\leq |AB|$.
Al punto medio de $BC$ se le nombra $M$.
Se rota el punto $A$ alrededor de $M$ en $180^\circ$ para obtener un punto $A’$.
Se define $f(T)$ como el triángulo $ACA’$.

Definimos una sucesión de triángulos como sigue. Se toma $T_0=T$. Luego, para $n\geq 0$ se define $T_{n+1}=f(T_n)$. ¿Es posible que esta sucesión tenga dos triángulos congruentes?

Sugerencia pre-solución. Es difícil estudiar las ternas de lados bajo la operación. Modifica el problema a entender otro parámetro que puedas estudiar fácilmente bajo las reglas dadas.

Solución. La respuesta es que en la sucesión no hay dos triángulos congruentes. De hecho, la observación clave es mostrar algo más fuerte: en la sucesión no hay dos triángulos con el mismo perímetro.

Tomemos un triángulo $T$. En el primer paso se nombran los vértices $ABC$ de modo que $BC$ el lado más chico del triángulo, y por lo tanto el ángulo en $A$ es menor estrictamente a $90^\circ$. Por esta razón, $A$ está fuera del círculo con diámetro $BC$, y por lo tanto la mediana $AM$ tiene longitud mayor a $\frac{|BC|}{2}$. El nuevo triángulo tiene lados de longitudes $|AB|$, $|AC|$ y $2|AM|>|BC|$.

Así, la sucesión de perímetros de los triángulos es estrictamente creciente. Por lo tanto, en la sucesión no puede haber dos triángulos con el mismo perímetro, y entonces no hay dos congruentes.

$\square$

Sucesiones recursivas y conteo

Las sucesiones recursivas aparecen también en problemas de combinatoria o de algoritmos, en donde ciertos casos o cierta cantidad de pasos se puede poner en términos de versiones más pequeñas del problema. Además, es posible que en un problema interactúen dos o más sucesiones de manera recursiva. Veamos un ejemplo.

Problema. Se tienen palabras de $10$ letras que usan los símbolos $a$, $b$ y $c$. ¿Cuántas de ellas no tienen dos $a$ consecutivas, ni dos $b$ consecutivas?

Sugerencia pre-solución. En vez de resolver el problema directamente, generalízalo a cuando se tienen palabras de $n$ letras. Para contar cuántas son, divide en casos de acuerdo a en qué símbolo terminan y plantea una recursión en términos de valores anteriores. Hay cierta simetría en $a$ y $b$. Aprovéchala.

Solución. Vamos a resolver un problema más general. Contemos las sucesiones sin dos $a$ ni dos $b$ consecutivas. Dividamos en los siguientes casos:

$\{x_n\}$ será la sucesión que cuenta cuántas de $n$ letras hay que terminen en $a$.
$\{y_n\}$ será la sucesión que cuenta cuántas de $n$ letras hay que terminen en $b$.
$\{z_n\}$ será la sucesión que cuenta cuántas de $n$ letras hay que terminen en $c$.

Por ejemplo, $x_1=y_1=z_1=1$, pues con una letra y con la letra final definida sólo hay una opción. Tenemos que $x_2=2$, que son $$ba,ca,$$ que $y_2=2$, que son $$ab,cb,$$ y que $z_3=3$, que son $$ac,bc,cc.$$ El problema nos pregunta por $x_{10}+y_{10}+z_{10}$.

La razón para partir en estos casos es que si sabemos en qué letra termina una sucesión, entonces sabemos exactamente cómo encontrar las que tienen una letra más de manera recursiva. Por ejemplo, para $n\geq 1$ tenemos que $x_{n+1}=y_n+z_n$, pues una palabra buena de $n+1$ letras que termina en $a$ se forma por una palabra buena de $n$ letras que no termina en $a$, y luego al final se le pone una $a$. Las tres recursiones que obtenemos son
\begin{align*}
x_{n+1}&=y_n+z_n\\
y_{n+1}&=x_n+z_n\\
z_{n+1}&=x_n+y_n+z_n.
\end{align*}

Ahora sí podemos hacer las cuentas únicamente haciendo operaciones, sin la dificultad que implica llevar el conteo de casos en el problema original. La siguiente tabla se puede llenar fácilmente, llenando renglón a renglón de arriba a abajo. Además, la simetría del problema en $a$ y $b$ hace que las sucesiones $x_n$ y $y_n$ sean iguales, así que también podemos aprovechar esto al momento de hacer las cuentas:

$n$	$x_n$	$y_n$	$z_n$
$1$	$1$	$1$	$1$
$2$	$2$	$2$	$3$
$3$	$5$	$5$	$9$
$4$	$14$	$14$	$19$
$5$	$33$	$33$	$47$
$6$	$80$	$80$	$113$
$7$	$193$	$193$	$273$
$8$	$466$	$466$	$659$
$9$	$1125$	$1125$	$1591$
$10$	$2716$	$2716$	$3841$

Tabla de valores de las sucesiones

De esta manera, la cantidad total de palabras que pide el problema es $$2716+2716+3841=9273.$$

$\square$

Recursiones lineales

Hay un tipo de sucesiones recursivas especiales, que cumplen que cada término depende de pocos términos anteriores y de manera lineal.

Por ejemplo, la sucesión de Fibonacci satisface $F_0=0$, $F_1=1$ y para $k\geq 0$ se tiene que $$F_{k+2}=F_k+F_{k+1}.$$ Aquí la recursión depende de los dos términos inmediatos anteriores, y cada uno de ellos aparece linealmente. Por ello, decimos que es una recursión lineal de orden 2.

La definición general es la siguiente.

Definición. Una sucesión $\{x_n\}$ de reales satisface una recursión lineal de orden $m$ si los primeros $m$ términos $x_0,\ldots,x_{m-1}$ están dados, y además existen reales $a_0,\ldots,a_{m-1}$ tales que para $k\geq 0$ se satisface la recursión lineal $$x_{m+k}=a_0x_k+a_1x_{k+1}+\ldots+a_{m-1}x_{m+k-1}.$$

El siguiente método nos ayuda en varios casos a pasar una sucesión que satisface una recursión lineal a una fórmula cerrada.

Primero, tomamos una sucesión $\{x_n\}$ como la de la definición. Luego, consideramos el siguiente polinomio de grado $m$: $$P(x)=x^m-a_{m-1}x^{m-1}-\ldots-a_0.$$

Supongamos que $r$ es una raíz de $P$. Afirmamos que la sucesión $\{r^n\}$ satisface la recursión. En efecto, como $r$ es raíz de $P$, tenemos que $$r^m=a_{m-1}r^{m-1}+\ldots+a_0,$$ y multiplicando ambos lados por $r^k$ tenemos que $$r^{m+k}=a_{m-1}r^{m+k-1}+\ldots+a_0r^k,$$ que es justo la recursión lineal (con los sumandos de derecha a izquierda).

Ahora, nota que si $\{x_n\}$ y $\{y_n\}$ satisfacen la recursión lineal, entonces para cualesquiera reales $c$ y $d$ tenemos que $\{cx_n+dy_n\}$ también. Entonces si hacemos combinaciones lineales de potencias de raíces de $P$ también tendremos sucesiones que satisfacen la recursión lineal. Resulta que en varios casos «todas las soluciones se ven así».

La discusión hasta aquí es un poco abstracta, así que hagamos un ejemplo concreto.

Problema. Determina una fórmula cerrada para la sucesión $\{A_n\}$ tal que $A_0=1$, $A_1=5$ y que satisface la recursión lineal de orden 2 $$A_{n+2}=-6A_n+5A_{n+1}.$$

Sugerencia pre-solución. Encuentra el polinomio asociado a la recursión. Si tiene raíces $\alpha$ y $\beta$, muestra que para cualesquiera reales $c$ y $d$ se tiene que $B(c,d)=\{c\alpha^n+d\beta^n\}$ satisface la recursión. Ya que nos dan los dos primeros términos, se puede encontrar los únicos $c$ y $d$ que funcionan para $\{A_n\}$.

Solución. El polinomio asociado a la recursión es $x^2-5x+6$, que tiene raíces $2\,\text{ y }\, 3$. Entonces, para cualesquiera reales $c$ y $d$ se tiene que la sucesión $B(c,d)=\{c2^n+d3^n\}$ satisface la recursión.

Además, necesitamos que los primeros términos sean $1\,\text{ y }\,5$ respectivamente, de donde obtenemos el sistema de ecuaciones para $c$ y $d$ siguiente:

\begin{align*}
1&=c2^0+d3^0=c+d\\
5&=c2^1+d3^1=2c+3d.
\end{align*}

La solución a este sistema es $c=-2$, $d=3$. De esta forma, la fórmula cerrada para $\{A_n\}$ es $$A_n=-2\cdot 2^n+3\cdot 3^n=3^{n+1}-2^{n+1}.$$

$\square$

Todos los pasos que hicimos en el problema anterior son reversibles, pero si quieres asegurarte de que todo va marchando bien, puedes mostrar por inducción que la fórmula dada es correcta.

Teorema para recursiones lineales de orden $m$

Resulta que cuando el polinomio asociado tiene $m$ raíces distintas, entonces el método anterior siempre funciona.

Teorema. Supongamos que la sucesión $\{x_n\}$ satisface la recursión lineal de orden $m$ $$x_{m+k}=a_0x_k+a_1x_{k+1}+\ldots+a_{m-1}x_{m+k-1}$$ para ciertos reales $a_0,\ldots,a_{m-1}$, y que las raíces del polinomio $$P(x)=x^m-a_{m-1}x^{m-1}-\ldots-a_0$$ son todas distintas y son $r_0,\ldots,r_{m-1}$. Entonces, existen únicos números $c_0,\ldots,c_{m-1}$ tales que para todo $n\geq 0$ se tiene $$x_n=c_0r_0^n+\ldots+c_{m-1}r_{m-1}^n,$$ y ellos se pueden encontrar mediante el sistema de $m$ ecuaciones lineales que queda al tomar $n=0,1,\ldots,m-1$.

No veremos la demostración de este teorema, pero aquí abajo lo usaremos para resolver algunos problemas.

Problema. La sucesión $\{B_n\}$ satisface que para toda $n\geq 0$ se tiene que $$B_{n+5}+B_n=-2(B_{n+4}+B_{n+1})-3(B_{n+3}+B_{n+2}).$$ Demuestra que esta sucesión es acotada.

Sugerencia pre-solución. Calcula el polinomio asociado. Factorízalo y muestra que todas sus raíces son diferentes.

Solución. Reacomodando los términos en la hipótesis, obtenemos que $\{B_n\}$ satisface una recursión lineal con polinomio asociado $$P(x)=x^5+2x^4+3x^3+3x^2+2x+1,$$ que se puede factorizar como $$(x^2+x+1)(x^3+x^2+x+1).$$

Las raíces del primer factor son las dos raíces cúbicas de la unidad que no sean uno digamos $w$ y $z$. Las del segundo factor son las $3$ raíces cuartas de la unidad que no sean uno, es decir $i$, $-1$ y $-i$.

Todos estos complejos tienen norma uno y además son distintos. De esta forma, por el teorema de recursiones lineales, existen únicos complejos $a,b,c,d,e$ tales que para toda $n$ se cumple $$B_n=aw^n+bz^n+ci^n+d(-1)^n+e(-i)^n.$$

De aquí podemos proceder de dos formas distintas. Una es simplemente tomando norma de ambos lados y usando la desigualdad del triángulo:

\begin{align*}
|B_n|&=\norm{aw^n+bz^n+ci^n+d(-1)^n+e(-i)^n}\\
&\leq \norm{aw^n}+\norm{bz^n}+\norm{ci^n}+\norm{d(-1)^n}+\norm{e(-i)^n}\\
&= \norm{a}+\norm{b}+\norm{c}+\norm{d}+\norm{e},
\end{align*}

lo cual muestra que $B_n$ está acotada.

La otra es usar que para cada raíz $m$-ésima de la unidad $\alpha$ y cualquier constante $r$ se tiene que $\{r\alpha^n\}$ es periódica de periodo $m$. De esta forma, $\{B_n\}$ es suma de sucesiones periódicas, y por lo tanto es periódica. Como es periódica, entonces es acotada.

$\square$

Existe una forma sistemática para lidiar con recursiones lineales cuando las raíces del polinomio anterior no son diferentes. Sin embargo, ella requiere de un buen entendimiento de matrices y diagonalización, que es un tema no trivial en álgebra lineal. De cualquier forma, el método anterior funciona en una gran variedad de situaciones.

Recursiones lineales y sumas de potencias

Quizás lo más importante del método anterior es que da la siguiente intuición:

«Las sucesiones $\{x_n\}$ que satisfacen una recursión lineal de orden $m$ y las expresiones del estilo $$S_n=c_0r_0^n+\ldots+c_{m-1}r_{m-1}^n$$ están fuertemente relacionadas.»

Así, cuando se tiene una combinación lineal de potencias $n$-ésimas, una de las primeras cosas que hay que hacer es ver si la recursión lineal que satisface nos ayuda para el problema. El siguiente problema es el Problema 1 de la primer Competencia Iberoamericana Interuniversitaria de Matemáticas

Problema. Muestra que para todo entero positivo $n$ se tiene que la expresión $\left(\frac{3+\sqrt{17}}{2}\right)^n+\left(\frac{3-\sqrt{17}}{2}\right)^n $ es un entero impar.

Sugerencia pre-solución. Ya discutimos cómo pasar de una recursión lineal a una suma de potencias. Ahora tienes que trabajar al revés para encontrar una recursión lineal que satisfaga la expresión del problema.

Solución. Sean $\alpha=\frac{3+\sqrt{17}}{2}$ y $\beta=\frac{3-\sqrt{17}}{2}$. El problema pide mostrar que para $n$ entero positivo se tiene que $x_n:=\alpha^n+\beta^n$ es un entero impar.

Como $\alpha$ y $\beta$ son raíces del polinomio
\begin{align*}
P(x)&=(x-\alpha)(x-\beta)\\
&=x^2-(\alpha+\beta)x+\alpha\beta\\
&=x^2-3x-2,
\end{align*}

se tiene que $x_n$ satisface la recursión lineal de orden dos siguiente: $$x_{n+2}=3x_{n+1}+2x_n.$$

Con esto, estamos listos para mostrar inductivamente que $x_n$ es impar para todo entero positivo $n$. Se tiene que $x_0=2$ y $x_1=\alpha+\beta=3$, de modo que por la recursión, $x_2=13$, así que la afirmación es cierta para $n=1,2$.

Si la afirmación es cierta hasta un entero positivo $n-1$, usamos la recursión para mostrar que $x_n=3x_{n-1}+2x_{n-2}$ es la suma de un entero impar y un entero par, de modo que $x_n$ es impar. Esto termina la demostración.

$\square$

Más problemas

Esta entrada es una extensión de la sección 7 del curso de sucesiones que impartí para los entrenadores de la Olimpiada Mexicana de Matemáticas. Puedes consultar las notas de este curso en el siguiente PDF, en donde hay más problemas de práctica:

Curso de Sucesiones Descarga