8.1: ¿Qué es Combinatoria?

Última actualización
Guardar como PDF

Page ID: 112979

\( \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 combinatoria estudia los arreglos de los objetos de acuerdo con algunas reglas. Las preguntas que se pueden hacer incluyen

Existencia. ¿Existen los arreglos?
Clasificación. Si los arreglos existen, ¿cómo podemos caracterizarlos y clasificarlos?
Enumeración. ¿Cuántos arreglos hay?
Construcción. ¿Existe un algoritmo para construir todos los arreglos?

Ejemplo\(\PageIndex{1}\label{eg:whatiscombo-01}\)

¿De cuántas maneras pueden sentarse cinco personas en una mesa redonda? ¿Y si cierto par de ellos se niega a sentarse uno al lado del otro? ¿Y si hay\(n\) gente?

Ejemplo\(\PageIndex{1}\label{eg:whatiscombo-02}\)

Dados enteros\(n_1 \geq n_2 \geq \cdots \geq n_t \geq 1\), un cuadro Young de la forma\((n_1,n_2,\dots,n_t)\) consiste en\(t\) filas de celdas justificadas a la izquierda, con\(n_i\) celdas en la fila\(i\) th (contando desde la fila superior). Estas celdas están ocupadas por los enteros del 1 al\(n\), donde\(n=n_1+n_2+\cdots+n_t\), de tal manera que las entradas están en orden descendente a través de cada fila de izquierda a derecha, y hacia abajo de cada columna de arriba a abajo. Por ejemplo, los tres cuadros Young de la forma\((3,1)\) se representan en la Figura\(\PageIndex{1}\).

Screen Shot 2020-01-15 at 12.53.20 PM.png — Figura\(\PageIndex{1}\): Los tres cuadros jóvenes de la forma (3, 1).

Se sabe que hay 35 cuadros jóvenes de la forma\((4,2,1)\). ¿Puedes enumerarlos todos? En general, uno puede preguntarse, ¿cuántos cuadros jóvenes hay de forma\((n_1,n_2,\ldots,n_t)\), y cómo podemos generarlos todos?

Ejemplo\(\PageIndex{3}\label{eg:whatiscombo-03}\)

Una cadena binaria es una secuencia de dígitos, cada uno de los cuales es 0 o 1. \(a_n\)Sea el número de cadenas binarias de longitud\(n\) que no contengan 1s consecutivos. Es fácil comprobarlo\(a_1=2\),\(a_2=3\), y\(a_3=5\). ¿Para qué sirve la fórmula general\(a_n\)?

Ejemplo\(\PageIndex{4}\label{eg:whatiscombo-04}\)

La complejidad de un algoritmo nos dice cuántas operaciones requiere. Al comparar la complejidad de varios algoritmos para resolver el mismo problema, podemos determinar cuál es el más eficiente. Dejar\(b_n\) ser el número de operaciones requeridas para resolver un problema de tamaño\(n\). Si se sabe que\[b_n = 2b_{n-1}+3b_{n-2}, \qquad n\geq3, \nonumber\] dónde\(b_1=1\) y\(b_2=3\), ¿para qué sirve la fórmula general\(b_n\)?