7: Técnicas de Prueba III - Combinatoria
- Page ID
- 113958
\( \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}}\)
La tragedia es cuando me corté el dedo. La comedia es cuando caes en una alcantarilla abierta y mueres.
—Mel Brooks
- 7.1: Conteo
- El título de esta sección, “Contando”, no pretende evocar el proceso habitual de contar ovejas, o cambio de conteo. Lo que queremos es poder contar alguna colección en principio para que podamos descubrir una fórmula para su tamaño. Hay dos principios que serán indispensables para contar las cosas: la “regla de multiplicación” que nos dice cuándo debemos multiplicar, y la “regla de la suma” que nos dice cuándo debemos agregar.
- 7.2: Argumentos de paridad y conteo
- Esta sección se ocupa de dos elementos muy poderosos del arsenal de pruebas: “Paridad” es una forma de referirse al resultado de un cálculo par/impar; Contar argumentos que suelen tomar la forma de contar alguna colección de dos maneras distintas —y luego comparar esos resultados. Estas técnicas tienen poco que ver entre sí, pero cuando son aplicables tienden a producir pequeños argumentos realmente elegantes.
- 7.3: El principio del encasillamiento
- La palabra “casillero” puede referirse a un agujero en el que una paloma duerme (es decir, más o menos como suena) o una serie de recesos aproximadamente cuadrados en un escritorio en el que se podría ordenar la correspondencia. Ya sea que prefieras pensar en aves dormidas o que se ordenen letras, la primera y más fácil versión del principio del encasillamiento es que si tienes más “cosas” de las que tienes “contenedores” debe haber un contenedor conteniendo al menos dos cosas.
- 7.4: El álgebra de combinaciones
- Un binomio es un polinomio con dos términos. Parece probable que ya hayas visto la disposición de estos coeficientes binomiales en una matriz triangular —conocida como el triángulo de Pascal. Lo que hace que este triángulo sea tan agradable y que lleva al extraño nombre de “coeficientes binomiales” para el número de k-combinaciones de un n-set es que puedes usar el triángulo para (muy rápidamente) calcular potencias de binomios.