(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En esta nota usaremos el concepto de combinaciones visto en la nota anterior para construir el famoso triángulo de Pascal, y probar cómo elevar un binomio a la $n$-ésima potencia, mediante la conocida fórmula del binomio de Newton. Empecemos la nota con un resultado que será la clave para ambos resultados.

Teorema

Sean $n,m\in \mathbb N,m+1\leq n$. Tenemos que:

$\binom{n}{m}+ \binom{n}{m+1}= \binom{n+1}{m+1} .$

Esta fórmula se conoce como la formula del triángulo de Pascal.

Demostración

Sean $n,m\in \mathbb N,m+1\leq n$ y $A=\set{a_1,\dotsc,a_{n+1}}$, un conjunto con $n+1$ elementos. Sabemos que:

$\binom{n+1}{m+1}=\#\set{C\subseteq A\mid \#C=m+1}.$

Pero si $C$ es un subconjunto de $A$ con $m+1$ elementos hay dos opciones, que $a_{n+1}\in C$ o que $a_{n+1}\notin C$, así:

$ \set{C\subseteq A\mid \#C=m+1}= $

$= \set{C\subseteq A\mid \#C=m+1, a_{n+1}\in C }\cup \set{C\subseteq A\mid \#C=m+1, a_{n+1}\notin C }.$

Y como la unión es disjunta :

$\# \set{C\subseteq A\mid \#C=m+1}=$

$= \# \set{C\subseteq A\mid \#C=m+1, a_{n+1}\in C }+ \# \set{C\subseteq A\mid \#C=m+1, a_{n+1}\notin C }$.

Pero todo subconjunto de $A$ con $m+1$ elementos tal que $a_{n+1}\in C$, es de la forma $B\cup \set{a_{n+1}}$, donde $B$ es un subconjunto de $\set{a_1,\dotsc,a_n}$ con $m$ elementos, por lo tanto:

$ \# \set{C\subseteq A\mid \#C=m+1, a_{n+1}\in C }=\binom{n}{m}.$

Por otro lado, todo subconjunto de $A$ con $m+1$ elementos tal que $a_{n+1}\notin C$ será un subconjunto de $\set{a_1,\dotsc,a_n}$ con $m+1$ elementos, así:

$ \# \set{C\subseteq A\mid \#C=m+1, a_{n+1}\notin C }=\binom{n}{m+1}.$

Concluimos que:

$\binom{n+1}{m+1}=\#\set{C\subseteq A\mid \#C=m+1}$

$= \# \set{C\subseteq A\mid \#C=m+1, a_{n+1}\in C } + \# \set{C\subseteq A\mid \#C=m+1, a_{n+1}\notin C } $

$= \binom{n}{m} + \binom{n}{m+1} .$

Y por lo tanto:

$ \binom{n+1}{m+1} = \binom{n}{m} + \binom{n}{m+1} $

que es lo que queríamos probar.

$\square$

El triángulo de Pascal

El triángulo de Tartaglia-Pascal fue estudiado por Niccolò Fontana, conocido como Tartaglia (1501-1557), y popularizado por Blaise Pascal (1623-1662), aunque ya se conocía desde siglos atrás en China y Persia. En este triángulo cada fila empieza y termina en 1 y los elementos intermedios son la suma de los que están arriba a la izquierda y arriba a la derecha. Si n es el número de la fila, empezando por 0 para el 1 del vértice, y m es la posición dentro de la fila, éste coincide con $\binom{n}{m}$.

Observa en los siguientes videos cómo se usa el teorema que acabamos de mostrar $ \binom{n+1}{m+1} = \binom{n}{m} + \binom{n}{m+1} $, para construir el triángulo de Pascal.

Revisa el siguiente enlace donde hay una construcción en geogebra del triángulo de Pascal.

https://www.geogebra.org/m/usruvfhg

Ve el siguiente video para conocer más sobre está maravillosa sucesión milenaria.

El binomio de Newton

Sean $a,b\in \mathbb R$, $n\in \mathbb N$, entonces se cumple que:

$(a+b)^n=\binom{n}{0}\, a^n\; b^0 + \binom{n}{1} a^{n-1} b^{1}+\dotsc+ \binom{n}{n-1} a^{1}b^{n-1}+\binom{n}{n} a^{0} b^{n} $ .

Demostración

La demostración se hará por inducción sobre $n$. Sean $a,b\in \mathbb R$, $n\in \mathbb N$.

Base de inducción

Si $n=0$ se cumple la fórmula:

$(a+b)^0=1=\binom{0}{0} a^0 b^0.$

Hipótesis de inducción

Supongamos que se vale para $n$.

$(a+b)^n=\binom{n}{0} a^n b^0 + \binom{n}{1} a^{n-1} b^{1}+\dotsc+ \binom{n}{n-1} a^{1} b^{n-1}+\binom{n}{n} a^{0} b^{n} $ .

Vamos a demostrar que se vale para $n+1$

Tenemos que:

$(a+b)^{n+1}=(a+b) (a+b)^{n}$, y por la hipótesis de inducción tenemos que

$(a+b)^{n+1}=(a+b)(a+b)^{n}=(a+b)\bigg[ \binom{n}{0} a^n b^0 + \binom{n}{1} a^{n-1} b^{1}+\dotsc+ \binom{n}{n-1} a^{1} b^{n-1}+\binom{n}{n} a^{0}b^{n}\bigg].$

Desarrollando tenemos que:

$(a+b)^{n+1}=a\bigg[\binom{n}{0}a^n b^0 + \binom{n}{1}a^{n-1}b^{1}+\dotsc+ \binom{n}{n-1} a^{1} b^{n-1}+\binom{n}{n} a^{0} b^{n} \bigg ]$ $+$

$b \bigg[\binom{n}{0} a^n b^0 + \binom{n}{1} a^{n-1} b^{1}+\dotsc+ \binom{n}{n-1} a^{1}b^{n-1}+\binom{n}{n} a^{0} b^{n} \bigg ]$

Multiplicando todos los términos tenemos que:

$(a+b)^{n+1}=$	$\binom{n}{0} a^{n+1}b^0+$	$\binom{n}{1} a^{n} b^{1}+$	$\dotsc+$	$\binom{n}{n} a^{1}b^{n}+$
	$+$	$\binom{n}{0}a^{n} b^{1}+$	$\dotsc+$	$\binom{n}{n-1} a^{1} b^{n}+$	$\binom{n}{n}a^0b^{n+1}$

Asociando los términos semejantes, tenemos que sus coeficientes son de la forma $\binom{n}{k+1}$ y $\binom{n}{k}$, y en virtud del teorema probado al inicio de esta nota tenemos que $\binom{n}{k+1}+ \binom{n}{k}= \binom{n+1}{k+1} $, y por lo tanto:

$(a+b)^{n+1}=\binom{n}{0} a^{n+1} + \binom{n+1}{1} a^{n} b^{1}+\dotsc+ \binom{n+1}{n} a^{1} b^{n}+\binom{n}{n} b^{n+1} $ .

Pero, dado que $\binom{n}{0}=1=\binom{n+1}{0}$ y que $\binom{n}{n}=1=\binom{n+1}{n+1} $ podemos reescribir lo anterior como

$(a+b)^{n+1}=\binom{n+1}{0} a^{n+1} + \binom{n+1}{1} a^{n} b^{1}+\dotsc+ \binom{n+1}{n} a^{1} b^{n}+\binom{n+1}{n+1} b^{n+1} $

y por lo tanto la fórmula también se cumple para $n+1$. Concluimos por el quinto axioma de Peano que se cumple para todo $n\in \mathbb N$.

Tarea Moral

Más adelante

Con esta nota hemos terminado la unidad 2. En la siguiente unidad veremos el importante concepto de espacio vectorial.

Enlaces relacionados

Página principal del curso.

Nota anterior. Nota 23. Combinaciones.

Nota siguiente. Nota 25. Espacios vectoriales.

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En la presente nota veremos el concepto de combinaciones, que considera todos los subconjuntos de un tamaño dado de un conjunto finito, esta idea es ampliamente usada en matemáticas, particularmente en probabilidad, y relacionada también íntimamente en cómo elevar un binomio a un exponente natural.

Demos formalmente la definición de combinaciones.

Definición

Sean $n,m\in \mathbb N^+$ con $m\leq n$, $A$ un conjunto con $n$ elementos. Las combinaciones de los elementos de $A$ tomados de $m$ en $m$ son los subconjuntos de $A$ de $m$ elementos. Denotamos por $\binom{n}{m}$ al número de combinaciones de un conjunto de $n$ elementos tomados de $m$ en $m$.

Ejemplo

Considera el conjunto $A=\set{a,b,c,d}$, con $a$, $b$, $c$ y $d$ elementos distintos. Obtengamos todas las combinaciones de $A$.

Sólo hay una combinación de los elementos de $A$ tomados de $0$ en $0$, el conjunto vacío, y sólo una combinación de los elementos de $A$ tomados de $4$ en $4$, el conjunto $A$, entonces

$\binom{4}{0}= \binom{4}{4}=1. $

Las combinaciones de los elementos de $A$ tomados de $1$ en $1$ son: $\set{a}$, $\set{b}$, $\set{c}$, $\set{d}$.

Las combinaciones de los elementos de $A$ tomados de $2$ en $2$ son $\set{a,b}$, $\set{a,c}$, $\set{a,d}$, $\set{b,c}$, $\set{b,d}$, $\set{c,d}$. Así

$\binom{4}{2}=6.$

Las combinaciones de los elementos de $A$ tomados de $3$ en $3$ son $\set{a,b,c}$, $\set{a,b,d}$, $\set{a,c,d}$, $\set{b,c,d}$, por lo que

$\binom{4}{3}=4.$

Observación 1

$\binom{n}{0}= \binom{n}{n}=1.$

Observación 2

$\binom{n}{1}= \binom{n}{n-1}=n.$

Considera que para obtener todos los subconjuntos de $n-1$ elementos de un conjunto $A$ con $n$ elementos, debemos tomar todos los elementos de $A$ salvo uno, y como $A$ tiene $n$ elementos entonces eso se puede hacer de $n$ formas distintas, una por cada elemento de $A$ que dejemos fuera del subconjunto. Por lo tanto existen $n$ subconjuntos de $A$ de $n-1$ elementos.

Teorema

Sean $n,m\in \mathbb N^+$, $m\leq n$, entonces $\binom{n}{m}P_m=O_{m}^{n}$.

Demostración

Sea $\mathscr O$ el conjunto de ordenaciones de $A$ tomados de $m$ en $m$, $\mathscr C$ el conjunto de las combinaciones de los elementos de $A$ tomados de $m$ en $m$.

Definimos $\varphi: \mathscr O\to \mathscr C $ como:

$\varphi(f)=\varphi\bigg(\begin{pmatrix}1 & \dotsi & m\\ f(1) & \dotsi & f(m)\end{pmatrix}\bigg)=\set{f(1),\dotsc,f(m)}$.

Veamos que $\varphi$ es suprayectiva. Si $c\in \mathscr C$, entonces $c$ es un subconjunto de $A$ con $m$ elementos, es decir $c=\set{b_1,\dotsc,b_m}$, con $ b_1,\dotsc,b_m\in A$ distintos. Así:

$f=\begin{pmatrix}1 & \dotsi & m\\ b_1 & \dotsi & b_m\end{pmatrix}\in \mathscr O$.

y entonces:

$\varphi(f)=\varphi\bigg(\begin{pmatrix}1 & \dotsi & m\\ b_1 & \dotsi & b_m\end{pmatrix}\bigg)=\set{b_1,\dotsc,b_m}$.

Y por lo tanto $\varphi$ es suprayectiva.

Sean $C_1,\dotsc,C_k$ los distintos subconjuntos de $A$ con $m$ elementos, donde $k=\binom{n}{m}$. Para cada $i\in\set{1,\dotsc,k}$ consideremos:

$O_i=\set{f\in \mathscr O\mid \varphi(f)=C_i}$

$\mathscr O$ es la unión disjunta de $O_1,\dotsc, O_k$ y entonces, por ser disjuntos y por el principio de la suma tenemos que:

$\#\mathscr O=\#(O_1\cup\dotsc,\cup O_k)=\#O_1+\dotsc+\#O_k.$

Pero si $f=\begin{pmatrix}1 & \dotsi & m\\ f(1) & \dotsi & f(m)\end{pmatrix}\in \mathscr O$, es tal que $\varphi(f)=C_1$, entonces las funciones de $O_1$ se obtendrán colocando en el segundo renglón del arreglo que describe la función, las distintas permutaciones de $\set{f(1),\dotsc,f(m)}$ que son $P_m$, y así:

$\#O_1=P_m.$

Y análogamente $\#O_i=P_m\,\,\, \,\,\, \forall i\in\set{1,\dotsc,k}.$

Por lo tanto:

$\#\mathscr O=\#O_1+\dotsc+\#O_k$, es decir la suma de $P_m$ $k$ veces, en consecuencia:

$\#\mathscr O= k P_m$,

y como $k=\binom{n}{m}$, entonces:

$\#\mathscr O= \binom{n}{m} P_m.$

Observa que $O_{n}^{m}=\#\set{f:\set{1,\dotsc, m}\to \set{a_1,\dotsc ,a_n}\mid \text{$f$ es inyectiva}}=\#\mathscr O.$

Por lo tanto $\binom{n}{m}P_m=O_{m}^{n}$ que es justamente lo que queríamos probar.

$\square$

Corolario

Sean $n,m\in \mathbb N^+$, $m\leq n$, entonces $\binom{n}{m}=\frac{ n! }{m!(n-m)!}$.

Demostración

Por el teorema anterior por lo que vimos en las entradas previas tenemos que:

$\binom{n}{m}=\frac{ O_{n}^{m} }{P_m}=\frac{n(n-1)\dotsc(n-m+1)}{m!}$.

Multiplicando arriba y abajo por $(n-m)!$ tenemos que:

$= \frac{n(n-1)\dotsc(n-m+1)(n-m)!}{m!(n-m)!}$

$= \frac{n(n-1)\dotsc(n-m+1)(n-m)\dotsc2\cdot1}{m!(n-m)!} $

$=\frac{n!}{m!(n-m)!}.$

$\square$

Tarea Moral

1. ¿Cuántas diagonales se pueden trazar en un polígono regular de $n$ lados?

2. Un club de Voleyball tiene $12$ jugadoras, una de ellas es la capitana María. ¿Cuántos equipos diferentes de $6$ jugadoras se pueden formar, sabiendo que en todos ellos siempre estará la capitana María.

3. Encuentra a qué es igual la expresion \[\sum_{k=0}\binom{n}{k}\] e interpreta tu respuesta en términos de subconjuntos.

4. Revisa el siguiente video.

Mas adelante

En la siguiente nota usaremos estos resultados para obtener el triángulo de Pascal, y probar la fórmula del binomio de Newton.

Enlaces relacionados.

Página principal del curso.

Nota anterior. Nota 22. Conteo. Ordenaciones.

Nota siguiente. Nota 24. El triángulo de Pascal y el binomio de Newton.

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En esta nota veremos como cuantificar el número de ordenaciones de $n$ objetos cuando son tomadas de $m$ en $m$ de ellos, para ello obtendremos el cardinal del número de funciones inyectivas del conjunto de los primeros $m$ naturales, en el conjunto de $n$ objetos.

Definición

Sean $n,m\in \mathbb N$. Dado un conjunto $A=\set{a_1,\dotsc ,a_n}$ con $n$ elementos, las ordenaciones de los elementos de $A$ tomados de $m$ en $m$ son las funciones inyectivas de $\set{1,\dotsc, m}$ en $A$. Al número de ordenaciones de los elementos de un conjunto con $n$ elementos, tomados de $m$ en $m$, lo denotaremos por $O_{n}^{m}$.

$O_{n}^{m}=\#\set{f\mid f:\set{1,\dotsc, m}\to A=\set{a_1,\dotsc ,a_n}, con\\\ f \\\ inyectiva}$

Observa que si $m>n$ entonces $O_{n}^{m}$ es cero.

Ejemplo

¿Cuántas banderas tricolores se pueden formar con rojo, naranja, verde, azul y morado?

Consideremos la bandera tricolor rojo, azul, naranja.

En el lugar $1$ asignamos el rojo, en el $2$ el azul y en el $3$ el naranja. Podemos verla como una función de $\set{1,2,3}$ en $A$, con $A$ el conjunto formado por los colores rojo, naranja, verde, azul y morado, es decir $A=\{rojo, naranja, verde, azul,morado\}$. En este caso la función sería:

$f: \set{1,2,3} \to A$ con $f(1)=rojo$, $f(2)=azul$, $f(3)=naranja.$

Veamos primero cuántas banderas tricolor hay que terminen en naranja.

Para ello debemos considerar todas las posibles maneras de iniciar una bandera que termine en naranja, lo cual corresponde a todas las formas de crear una bandera bicolor con los colores restantes. Las banderas bicolores formadas con rojo, verde, azul o morado son:

Hay 12 banderas bicolor con estos $4$ colores.

Fíjate que entonces hay $12$ banderas tricolor que terminan en naranja. De manera similar hay 12 que terminan rojo, 12 en verde, 12 en azul y 12 en morado, doce por cada color. Éstas son el total de las ordenaciones de 4 elementos tomadas de 2 en 2, $O_{4}^{2}$, el número de banderas tricolor es entonces:

$5\cdot 12=5\cdot O_{4}^{2}= O_{5}^{3}=60.$

Observa que $ O_{5}^{3} =5\cdot O_{4}^{2}$, probaremos que esto es válido en general y que $ O_{n+1}^{m+1} =(n+1)\cdot O_{n}^{m}$.

Lema

Sean $n,m\in \mathbb N^+$, $n\geq m$, entonces $O_{n+1}^{m+1}=(n+1)\cdot O_{n}^{m} $.

Demostración

Sean $n,m\in \mathbb N^+$, $n\geq m$ y $A=\set{a_1\dotsc,a_n,a_{n+1}}$ con $n+1$ elementos.

$O_{n+1}^{m+1}=\#\set{f:\set{1,\dotsc, m,m+1}\to A=\set{a_1,\dotsc ,a_n,a_{n+1}}\mid f \\\ es\\\ inyectiva}$.

Para cada $i\in \set{1,\dotsc,n+1}$ consideremos el siguiente conjunto:

$B_{i}=\set{ f:\set{1,\dotsc, m,m+1}\to A=\set{a_1,\dotsc ,a_n,a_{n+1}} \mid f \\\ es \\\ inyectiva\\\ y \\\ f(m+1)=a_i }$.

Estamos considerando sólo aquellas funciones que mandan al último elemento del dominio, $m+1$, a $a_i\in A$.

Cada una de estas funciones está determinada por su restricción a $\set{1,\dotsc, m}$, que es una función inyectiva de $\set{1,\dotsc, m}$ en $A$, y como en la imagen no aparecerá el elemento $a_i$, se puede considerar como una función inyectiva de $\set{1,\dotsc, m}$ en $A\setminus \set{a_i}$ (conjunto que tiene $n$ elementos). Entonces por la notación establecida para el número de ordenaciones:

$\#B_i=O_{n}^{m}$

Pero $ \set{ f:\set{1,\dotsc, m,m+1}\to A=\set{a_1,\dotsc ,a_n,a_{n+1}} \mid f \\\ es \\\ inyectiva}$ es la unión disjunta de $B_1,\dotsc, B_{n+1}$, es decir:

$B_1\cup \dotsc \cup B_{n+1}= \set{ f:\set{1,\dotsc, m,m+1}\to A=\set{a_1,\dotsc ,a_n,a_{n+1}} \mid f \\\ es \\\ inyectiva}$.

Por lo que

$\#(B_1\cup \dotsc \cup B_{n+1})= \# \set{ f:\set{1,\dotsc, m,m+1}\to A=\set{a_1,\dotsc ,a_n,a_{n+1}}\mid f \\\ es \\\ inyectiva}.$

Y por el principio generalizado de la suma tenemos que:

$\#B_1+ \dotsc + \# B_{n+1}= \# \set{ f:\set{1,\dotsc, m,m+1}\to A=\set{a_1,\dotsc ,a_n,a_{n+1}}\mid f \\\ es \\\ inyectiva}.$

Como $\#B_i=O_{n}^{m}$, para todo $i\in\set{1,\dotsc,n+1}$, entonces

$(n+1)\cdot O_{n}^{m}= \# \set{ f:\set{1,\dotsc, m,m+1}\to A=\set{a_1,\dotsc ,a_n,a_{n+1}} \mid f \\\ es \\\ inyectiva}.$

Y por lo tanto:

$ O_{n+1}^{m+1} =(n+1)\cdot O_{n}^{m} .$

$\square$

Ejemplo

En la fila de un avión hay $3$ lugares, ¿de cuántas formas podemos llenarla eligiendo a personas de una familia de 6 integrantes? o bien, ¿Cuántas ordenaciones hay de un conjunto con $6$ elementos tomados de $3$ en $3$?

Sabemos que:

$O_{6}^{3}=6\cdot O_{2}^{5}= 6\cdot5 \cdot O_{4}^{1}.$

Pero si $A=\set{a_1,a_2,a_3,a_4}$ es un conjunto con cuatro elementos, habrá $4$ funciones inyectivas de $\set{1}$ en $A$ y por lo tanto $ O_{4}^{1} =4$. Así:

$O_{6}^{3}=6\cdot5 \cdot 4=120$, y por lo tanto hay $120$ maneras de llenar la fila.

Teorema

Sean $n,m\in \mathbb N^+$, $n\geq m$, entonces $O_{n}^{m}=n(n-1)\dotsc(n-m+1)$

Demostración

Sean $n,m\in \mathbb N^+$, $n\geq m$

Haremos la prueba por inducción sobre $m$

Si $m=1$ consideremos $A=\set{a_1,\dotsc,a_n}$ con $n$ elementos. Tenemos que hay $n$ funciones inyectivas de $\set{1}$ en $A$, así:

$O_{n}^{1}=n=n-1+1$ y en este caso se cumple la fórmula.

Supongamos que resultado se cumple para $m$, es decir que $O_{t}^{m}=t(t-1)\dotsc (t-m+1)$ para toda $t\geq m$, que es nuestra hipótesis de inducción.

Sea $n\geq m+1$.

Si consideramos $O_{n}^{m+1}= O_{(n-1)+1}^{m+1} $, por el lema anterior esto es igual a

$ O_{(n-1)+1}^{m+1}=[(n-1)+1] O_{n-1}^{m} .$

Como $n-1\geq m$ usando la hipótesis de inducción tenemos que

$ O_{n-1}^{m} = (n-1)(n-2)\dotsc ((n-1)-m+1)$

de donde

$ O_{(n-1)+1}^{m+1}=[(n-1)+1] O_{n-1}^{m} = [(n-1)+1] (n-1)(n-2)\dotsc ((n-1)-m+1)$

Así $ O_{n}^{m+1}=[(n-1)+1] O_{n-1}^{m} = n(n-1)(n-2)\dotsc (n-m)$, probando con ello que el resultado se cumple para $m+1$.

Por el principio de inducción la fórmula se cumple para toda $m$.

$\square$

Tarea Moral

1. Entre un grupo de 7 personas se debe elegir una mesa directiva con un presidente, un secretario, un vocal y un suplente ¿de cuántas maneras se puede elegir esa mesa directiva?

2. En un concurso participan 30 alumnos y se decidirá quién se lleva cada uno de los tres primeros lugares ¿cuántos posibles resultados se tienen como ganadores del concurso?

3. i) ¿De cuántas maneras pueden posar tres hombres y dos mujeres en línea para una fotografía de grupo?
ii) ¿De cuántas maneras pueden colocarse en línea si una mujer debe estar en cada extremo?
iii) ¿De cuántas maneras las personas del mismo sexo están juntas?

Más adelante

En la siguiente nota continuaremos el estudio de las técnicas de conteo, daremos la definición formal de combinaciones, que son el número de subconjuntos de un conjunto dado.

Enlaces relacionados

Página principal del curso.

Enlace a la nota anterior. Nota 21. Conteo, ordenaciones con repetición.

Enlace a la nota siguiente. Nota 23. Combinaciones.

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

Una vez que tenemos construidos los números naturales, su primera aplicación será el conteo, en esta nota analizaremos la situación conocida como ordenaciones con repetición, que nos dan todas las posibilidades de formar una secuencia ordenada de $m$ posiciones, llenadas con los $n$ objetos de un determinado conjunto.

Definición

Sean $n,m\in \mathbb N$. Dado un conjunto $A=\set{a_1,\dotsc ,a_n}$ con $n$ elementos, las ordenaciones con repetición de los elementos de $A$ tomados de $m$ en $m$ son las funciones de $\set{1,\dotsc, m}$ en $A$. Al número de ordenaciones con repetición de los elementos de un conjunto de $n$ elementos de $m$ en $m$ lo denotaremos por $OR_{n}^{m}$.

$OR_{n}^{m}=\#\set{f\mid f:\set{1,\dotsc, m}\to A=\set{a_1,\dotsc ,a_n} }$

Ejemplo.

Sea $A=\set{a,e,i,o,u}$. Las ordenaciones con repetición de los elementos de $A$ tomados de dos en dos son las funciones de $\set{1,2}$ en $\set{a,e,i,o,u}$. Por ejemplo, una de esas ordenaciones es:

$1\longmapsto i$

$2\longmapsto a$

Recordemos que esta función se puede describir como:

\begin{pmatrix}1&2\\
i&a\end{pmatrix}

Lo que determina a esta función es la palabra $ia$ que aparece en el segundo renglón. ¿Cuántas funciones hay de $\set{1,2}$ en $A=\set{a,e,i,o,u}$ ?, o bien, ¿Cuántas palabras podemos formar con dos letras usando sólo vocales?.

Hay 5 palabras que inician con $i$: $ia$, $ie$, $ii$, $io$, $iu$.

Hay 5 palabras que inician con $a$: $aa$, $ae$, $ai$, $ao$, $au$.

Hay 5 palabras que inician con $e$: $ea$, $ee$, $ei$, $eo$, $eu$.

Hay 5 palabras que inician con $o$: $oa$, $oe$, $oi$, $oo$, $ou$.

Hay 5 palabras que inician con $u$: $ua$, $ue$, $ui$, $uo$, $uu$.

Por cada vocal inicial tenemos $5$ palabras, así que en total son tenemos $25$ palabras.

Podemos pensar a estas funciones o palabras como pares ordenados:

$\set{(i,a), (i,e), (i,i), (i,o), (i,u), (a,a), (a,e), (a,i), (a,o), (a,u),\dotsc }=A\times A$

Por lo que: $\#A\times A=\#A\cdot \#A=5\cdot 5=5^2=OR_{5}^{2}$

Acabamos de obtener que $ OR_{5}^{2}=5^2$, veremos en el siguiente teorema que esto es válido en general y que $OR_{n}^{m}=n^m$.

Teorema

Sean $n,m\in \mathbb N^+$ entonces $OR_{n}^{m}=n^m$

Demostración

Sea $A=\set{a_1,\dotsc, a_n}$ con $n$ elementos.

Por definición:

$OR_{n}^{m}=\#\set{f\mid f:\set{1,\dotsc, m}\to A=\set{a_1,\dotsc ,a_n} }$ .

Veamos que $ \#\set{f\mid f:\set{1,\dotsc, m}\to A=\set{a_1,\dotsc ,a_n} }=\#A^m$ dando una biyección entre ambos conjuntos.

Sea $\varphi: \set{f\mid f:\set{1,\dotsc, m}\to A=\set{a_1,\dotsc ,a_n} } \to A^m$ dada por:

$\varphi(f)=\varphi\bigg(\begin{pmatrix}1 & \dotsi & m\\ f(1) & \dotsi & f(m)\end{pmatrix}\bigg)=(f(1),\dotsc,f(m))$.

La función $\varphi$ es inyectiva ya que si $ f,g:\set{1,\dotsc, m}\to A$ son tales que $\varphi(f)= \varphi(g)$ , entonces $ (f(1),\dotsc,f(m))= (g(1),\dotsc,g(m)) $, y así $f(i)=g(i)\\\ \forall i\in \set{1,\dotsc, m}$, de donde $f$ y $g$ tienen la misma regla de correspondencia, y como coinciden en dominio y codominio entonces $f=g$. Por lo tanto $\varphi$ es inyectiva.

Además $\varphi$ es suprayectiva ya que si $(x_1,\dotsc,x_m)\in A^m$, consideremos la función:

$f=\begin{pmatrix}1 & \dotsi & m\\ x_1 & \dotsc & x_n\end{pmatrix}$

$\varphi(f)= \varphi\bigg(\begin{pmatrix}1 & \dotsi & m\\ x_1 & \dotsc & x_n\end{pmatrix} \bigg)= (x_1\dotsc x_m) $.

Así, $\varphi$ es también suprayectiva, y por lo tanto biyectiva. Entonces:

$ \#\set{f\mid f:\set{1,\dotsc, m}\to A=\set{a_1,\dotsc ,a_n} }=\#A^m.$

Recordemos que la notación antes establecida nos dice que $ \#\set{f\mid f:\set{1,\dotsc, m}\to A=\set{a_1,\dotsc ,a_n} }=OR_{n}^{m}.$

Por otro lado, por el principio generalizado del producto la cardinalidad de $A^m$ es $m$ veces la multiplicación de la cardinalidad de $A$ y así $\#A^m=n^m$. Concluimos finalmente que:

$OR_{n}^{m}=n^m$.

$\square$

Tarea moral

1. ¿Cuántos números telefónicos hay con 8 dígitos (del 0 al 9) que empiecen con 5?
2. ¿Cuántas placas hay que inicien con 3 números (del 0 al 9) y terminen con 3 letras (contando 27 en el alfabeto)?
3. ¿Cuántas palabras de 5 letras se pueden formar con el alfabeto de 27 letras?
4. Ve el siguiente video del profesor Luis Rincón.

Más adelante

En la siguiente nota continuaremos con el tema de conteo, ésta vez para las ordenaciones sin repetición.

Enlaces relacionados

Página principal del curso.

Enlace a la nota anterior. Nota 20. Principio del producto, funciones entre conjuntos finitos.

Enlace a la nota siguiente. Nota 22. Conteo. Ordenaciones.

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En esta nota deduciremos el resultado conocido como Principio del producto que nos garantiza que la cardinalidad del producto cartesiano de dos conjuntos finitos (ver nota 6) es igual al producto de las cardinalidades de cada conjunto. Así mismo probaremos que cuando se tiene una función entre conjuntos finitos de la misma cardinalidad, son equivalentes ser inyectiva, suprayectiva o biyectiva.

Empecemos probando un lema que nos ayudará a probar el principio del producto.

Lema 1

Sea $A$ un conjunto finito, $b$ un objeto, entonces $A\times \set{b}$ es finito y $\# (A\times \set{b})=\#A$.

Demostración

Sea $A$ un conjunto finito, $b$ un objeto, $n=\#A$, y $f:\set{1,\dotsc,n}\to A$ una biyección.

Sea $g:A\to A\times \set{b}$ dada por $g(a)=(a,b)$ $\forall a\in A$.

Observemos que la función $h:A\times \set{b}\to A$ dada por $h((a,b))=a\,\,\forall (a,b)\in A\times \set{b}$ es la inversa de g, pues:

$h\circ g(a)=h(g(a))=h((a,b))=a\,\,\forall a\in A$.

$g\circ h((a,b))=g(h((a,b)))=g(a)=(a,b)\,\,\forall (a,b)\in A\times \set{b}$.

Así $g$ es invertible y por tanto biyectiva.

Como $f$ y $g$ son biyectivas, entonces $g\circ f:\set{1,\dotsc,n}\to A\times \set{b} $ es biyectiva.

Así $\# (A\times \set{b})=n$ y por lo tanto $\# (A\times \set{b})=\#A$.

$\square$

Teorema. Principio del producto

Sean $A,B$ conjuntos finitos, entonces $A\times B$ es finito y $\#(A\times B)=\#A\cdot \#B$.

Demostración

Sean $A,B$ conjuntos finitos, $n=\#A$, $m=\#B$.

Entonces $B=\set{b_1,\dotsc,b_m}$ con $b_i\neq b_j\,\,\forall i,j.$

Observemos que $A\times B= (A\times \set{b_1})\cup (A\times \set{b_2})\cup\dotsc\cup (A\times \set{b_m})$ donde $ (A\times \set{b_i})\cap (A\times \set{b_j})=\emptyset\,\,\forall i\neq j$.

Así por el principio generalizado de la suma visto en la nota anterior.

$\#(A\times B)= \#(A\times \set{b_1})+ \# (A\times \set{b_2})+\dotsc+\# (A\times \set{b_m}).$

Por el lema previo $\forall i$ $ \#(A\times \set{b_i})=\#A$, entonces tenemos que:

$\#(A\times B)=m\cdot \#A$, y como $m=\#B$. Sustituyendo:

$\#(A\times B)=\#A\cdot \#B.$

$\square$

Nota

Este resultado se puede generalizar, si $A_1,\dotsc,A_t$ son conjuntos finitos, entonces $A_1\times\cdots\times A_t$ es finito y $\#(A_1\times\cdots\times A_t)=\#A_1\cdots \#A_t $, y se conoce como el principio generalizado del producto.

Veamos ahora qué información podemos obtener acerca de la cardinalidad de dos conjuntos finitos, a partir de las características de alguna función definida entre ellos.

Lema 2

Sean $A,B$ conjuntos finitos

i) Si existe $f:A\to B$ inyectiva, entonces $\#A= \#Im f$ y $ \#A\leq \#B$.

ii) Si existe $f:A\to B$ suprayectiva, entonces $ \#A\geq \#B$.

Demostración de i)

Sean $A$ y $B$ conjuntos finitos.

Supongamos que existe $f:A\to B$ inyectiva.

Consideremos la función $F:A\to Imf$ tal que $F(a)=f(a)\,\,\forall a\in A$.

Como $f$ es inyectiva $F$ también lo es, y por construcción $F$ es suprayectiva.

Así $F$ es biyectiva y entonces $\#A= \#Imf$.

Como $Imf\subseteq B$, entonces $ \#Imf\leq \#B$, de donde $ \#A = \#Imf\leq \#B$.

Demostración de ii)

Sean $A$ y $B$ conjuntos finitos.

Supongamos que existe $f:A\to B$ suprayectiva.

Sea $B=\set{b_1,\dotsc,b_m}$ con $m=\#B$ y $b_i\neq b_j\,\,\,\forall i,j$.

Como $f$ es suprayectiva, para cada $b_i\in B$ existe un elemento de $A$ que bajo $f$ va a dar a $b_i$, elijamos uno de ellos, digamos $a_i\in A$ tal que $f(a_i)=b_i$.

Definamos la función $g:B\to A$ con $g(b_i)=a_i\,\,\,\forall i\in \set{1,\dotsc, m}.$ Veamos que $g$ es invectiva.

Si $i,j\in \set{1,\dotsc, m}$ son tales que $g(b_i)=g(b_j)$ entonces $a_i=g(b_i)=g(b_j)=a_j$, de manera que $a_i=a_j$ y en consecuencia:

$b_i=f(a_i)=f(a_j)=b_j,$

por lo cual $b_i=b_j$, así $g$ es inyectiva.

Por el inciso $i)$ tenemos entonces que el dominio de $g$ tiene cardinalidad menor o igual a su condominio, es decir $\#B\leq \#A$.

$\square$

Observaciones

• Sea $A$ un conjunto finito. Si $A\neq \emptyset$, entonces $\#A\geq 1 $. De modo equivalente si $\#A=0$ entonces $A=\emptyset$.
• Sean $A,B$ conjuntos finitos con $A\subseteq B$. Si $\#A=\#B$, entonces $A=B$.

Teorema

Sean $A,B$ conjuntos finitos com $\#A= \#B$, $f:A\to B$.

Las siguientes afirmaciones son equivalentes:

a) $f$ es inyectiva.

b) $f$ es suprayectiva.

c) $f$ es biyectiva.

Demostración

Sean $A,B$ conjuntos finitos con $\#A= \#B$, $f:A\to B$.

a) $\Longrightarrow$b)

Supongamos que $f$ es inyectiva.

Por demostrar que $f$ es suprayectiva.

Como $f$ es inyectiva, por el Lema 2 $\#A= \#Imf $, tenemos entonces que

$\#B= \#A= \#Imf$

Así $Imf\subseteq B$ con $ \#Imf= \#B$, y por lo tanto $Imf=B$ y así $f$ es suprayectiva.

b) $\Longrightarrow$a)

Supongamos que $f$ es suprayectiva, es decir que $Imf=B$.

Por demostrar que $f$ es inyectiva.

Sea $n=\#A= \#B$, $A=\set{a_1,\dotsc,a_n}$ con $a_i\neq a_j\,\,\,\forall i\neq j$.

Como $Imf=B$, entonces $\#Imf= \#B=n$.

Supongamos por reducción al absurdo que $f$ no es inyectiva, entonces existen dos elementos de $A$ que bajo $f$ son iguales, sin pérdida de generalidad supongamos que $f(a_{n-1})=f(a_n)$, entonces:

$Imf=\set{f(a_1),\dotsc,f(a_{n-1})}$

La función $h:\set{1,\dotsc,n-1}\to Imf$ con $h(i)=f(a_i)\,\,\,\forall i$ sería entonces suprayectiva, así aplicando el Lema 2 tenemos que:

$n-1=\#\set{1,\dotsc,n-1}\geq \#Imf=\#B=n$, y entonces tendriamos que $n-1\geq n$, pero eso es una contradicción y por lo tanto $f$ es inyectiva.

Hemos probado entonces que, bajo nuestras hipótesis, $f$ es inyectiva si y sólo si es suprayectiva, así que si se cumple a) se tiene también b) y entonces $f$ es biyectiva y se cumple c). Análogamente si se cumple b) se tiene también a) y entonces $f$ es biyectiva y se cumple c). Además, si se cumple c) se tiene que $f$ es biyectiva y por lo tanto es inyectiva y suprayectiva, así que se cumplen a) y b).

Por lo tanto las condiciones a), b) y c) son equivalentes.

$\square$

Tarea moral

1. Sean $A$ y $B$ conjuntos finitos. Demuestra o da un contraejemplo:

i) Si $\#A\leq \#B$ y $f$ es una función $f:A\to B$, entonces $f$ es inyectiva.

ii) Si $\#A\geq \#B$ y $f$ es una función $f:A\to B$, entonces $f$ es suprayectiva.

iii) Si $\#A=\#B$ y $f$ es una función $f:A\to B$, entonces $f$ es biyectiva.

2. Para acceder a una aplicación se requiere una contraseña de 3 dígitos que pueden ser 0,1,2,3,4,5,6,7,8,9.
i) Describe a cada contraseña como una terna ordenada y al conjunto de contraseñas como un producto cartesiano
ii) ¿Cuántas contraseñas hay?
iii) Si ahora la contraseña puede ser de 3 o de cuatro dígitos ¿Cuántas contraseñas habrá?

3. Ve el siguiente vídeo y elabora tus propias observaciones, coméntalas con tus colegas.

Mas adelante

En las siguientes notas haremos énfasis en el estudio de las técnicas de conteo, ordenaciones, ordenaciones con repetición, y combinaciones serán objeto de nuestro estudio.

Enlaces relacionados

Página principal del curso.

Enlace a la nota anterior. Nota 19. Conjuntos equivalentes y cardinalidad.

Enlace a la nota siguiente. Nota 21. Conteo, ordenaciones con repetición.