(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.