12.4: Contando elementos de conjuntos finitos con biyecciones

Última actualización
Guardar como PDF

Page ID: 118320

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

En un capítulo futuro, comenzaremos a aprender a contar colecciones complicadas contando las “elecciones” necesarias para determinar un elemento arbitrario en la colección. En esta sección, analizamos cómo contar las colecciones encontrando una colección del mismo tamaño que sea más fácil de contar.

Ejemplo\(\PageIndex{1}\): Counting paths with words.

Considera caminos en la\(5 \times 10\) cuadrícula de abajo que comienzan en la parte inferior izquierda y terminan en la parte superior derecha, y solo se mueven hacia arriba o hacia la derecha en cada paso. (Uno de esos caminos se dibuja en.) ¿Cuántos caminos de este tipo hay?

Vamos a\(P\) representar el conjunto de todos esos caminos. Podemos distinguir cada elemento de\(P\) por la secuencia de direcciones que toma en cada paso. Dejar\(\Sigma = \{R,U\}\text{,}\) dónde\(R\) y\(U\) estar de pie para las direcciones “derecha” y “arriba”, respectivamente. Entonces para cada camino\(p \in P\) podemos construir una palabra\(w_p \in \Sigma ^{\ast}\) estableciendo las letras de\(w_p\) para que correspondan a los pasos en el camino. Por ejemplo, la ruta en el diagrama anterior correspondería a la palabra\(RRURUURRRRURR\text{.}\)

¡Esta asignación de palabras en\(\Sigma ^{\ast}\) caminos adentro\(P\) es una función! Vamos a llamarlo\(f: P \rightarrow \Sigma ^{\ast}\text{,}\) y establecer\(W = f(P)\text{,}\) la imagen de\(f\) en\(\Sigma ^{\ast}\text{.}\) Esta función es claramente uno a uno, ya que diferentes caminos deben producir diferentes palabras de indicadores de dirección. Y como cada función mapea su dominio surjectivamente sobre su imagen, obtenemos una biyección\(f: P \rightarrow W\) restringiendo el codominio. Por lo tanto, podemos contar los caminos en lugar\(P\) de contar las palabras en\(W\text{!}\)

Dado que cada camino en\(P\) toma exactamente\(13\) pasos, exactamente\(4\) de los cuales deben ser hacia arriba y exactamente\(9\) de los cuales deben estar a la derecha, vemos que\(W\) consiste precisamente en esas palabras en\(\Sigma ^{\ast}\) que tienen longitud\(13\) y contienen exactamente\(4\)\(U\) s y \(9\)\(R\)s. una vez aprendamos algunas técnicas básicas de conteo más adelante en el curso, podrás volver a este ejemplo para verificar que

\ begin {ecuación*}\ vert P\ vert =\ vert W\ vert = 715\ texto {.} \ end {ecuación*}