1: Contar
- Page ID
- 115742
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Una de las primeras cosas que aprendes en matemáticas es cómo contar. Ahora queremos contar grandes colecciones de cosas de forma rápida y precisa. Por ejemplo:
- En un grupo de 10 personas, si todos dan la mano a todos los demás exactamente una vez, ¿cuántos apretones de manos se llevaron a cabo?
- ¿De cuántas formas puedes distribuir 1010 galletas de Girl Scouts a 77 boy scouts?
- ¿Cuántos anagramas hay de “anagrama”?
Antes de abordar preguntas como estas, veamos los conceptos básicos del conteo.
- 1.1: Principios Aditivos y Multiplicativos
- Considera este problema de conteo bastante simple: en Red Dogs and Donuts, hay 14 variedades de donas, y 16 tipos de hot dogs. Si quieres ya sea un donut o un perro, ¿cuántas opciones tienes? Esto no es demasiado duro, solo agrega 14 y 16. ¿Eso siempre funcionará? ¿Qué es lo importante aquí?
- 1.2: Coeficientes binomiales
- Aquí hay algunos objetos discretos aparentemente diferentes que podemos contar: subconjuntos, cadenas de bits, rutas de celosía y coeficientes binomiales. Vamos a dar un ejemplo de cada tipo de problema de conteo (y decir cuáles son estas cosas incluso). Como veremos, estos problemas de conteo son sorprendentemente similares.
- 1.3: Combinaciones y permutaciones
- Una permutación es un (posible) reordenamiento de objetos.
- 1.4: Pruebas combinatorias
- Para dar una prueba combinatoria de una identidad binomial, diga A=B haces lo siguiente: (1) Encuentra un problema de conteo podrás responder de dos maneras. (2) Explica por qué una respuesta al problema de conteo es A. (3) Explica por qué la otra respuesta al problema de conteo es B. Ya que tanto A como B son las respuestas a la misma pregunta, debemos tener A=B. Lo complicado es que se le ocurra la pregunta.
- 1.5: Estrellas y barras
- Muchos de los problemas de conteo en esta sección podrían parecer al principio como ejemplos de funciones de conteo. Después de todo, cuando tratamos de contar la cantidad de formas de distribuir cookies a los niños, estamos asignando cada cookie a un niño, al igual que asignas elementos del dominio de una función a elementos en el codominio.
- 1.6: Recuento avanzado usando PIE
- El Principio de Inclusión/Exclusión (PIE) da un método para encontrar la cardinalidad de la unión de conjuntos no necesariamente disjuntos. Si hay alguna superposición entre los conjuntos, esos elementos se cuentan varias veces. Entonces restamos las cosas en cada intersección de un par de conjuntos. Pero al hacer esto se eliminan los elementos que están en los tres conjuntos una vez con demasiada frecuencia, por lo que necesitamos agregarlo de nuevo.
- 1.S: Conteo (Resumen)
- Si bien hemos cubierto muchas técnicas de conteo, en realidad solo hemos rayado la superficie del gran tema de la combinatoria enumerativa. Hay matemáticos haciendo investigaciones originales en esta área incluso mientras lees esto. Contar puede ser muy difícil.