(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 de $n$ elementos tomados de $m$ en $m$, que son todas las secuencias ordenadas de $m$ entradas, llenadas con los $n$ objetos de un determinado conjunto.

Definición

Sean $n,m\in \mathbb N^+$. Dado un conjunto finito $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 tomados 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 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 (recuerda que $A^m$es el producto cartesiano de $A$ consigo mismo $m$ veces).

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$, podemos considerar la función:

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

$\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 el número de elementos de $A^m$ es el número de elementos de $A$ multiplicado $m$ veces. 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, esta 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.