5: El principio de inclusión y exclusión
- Page ID
- 112549
\( \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}}\)
Uno de nuestros primeros principios de conteo fue el principio de suma que dice que el tamaño de una unión de conjuntos disgregados es la suma de sus tamaños. El cálculo del tamaño de los conjuntos superpuestos requiere, naturalmente, información sobre cómo se superponen. Tomar en cuenta dicha información nos permitirá desarrollar una poderosa extensión del principio de suma conocido como el “principio de inclusión y exclusión”.
- 5.1: El tamaño de una unión de conjuntos
- Uno de nuestros primeros principios de conteo fue el principio de suma que dice que el tamaño de una unión de conjuntos disjuntos es la suma de sus tamaños. Calcular el tamaño de los conjuntos superpuestos requiere, naturalmente, información sobre cómo se superponen. Tomar en cuenta dicha información nos permitirá desarrollar una poderosa extensión del principio de suma conocido como el “principio de inclusión y exclusión”.
- 5.2: Aplicaciones de Inclusión y Exclusión
- Definimos una gráfica para que consista en el conjunto V de elementos llamados vértices y un conjunto E de elementos llamados bordes de tal manera que cada borde se une a dos vértices. Una coloración de una gráfica por los elementos de un conjunto C (de colores) es una asignación de un elemento de C a cada vértice de la gráfica; es decir, una función del conjunto de vértices V de la gráfica a C. Una coloración se llama apropiada si por cada borde que une dos vértices distintos, los dos vértices que une tienen diferentes colores.
- 5.3: Deleción-Contracción y el Polinomio Cromático
- En el Capítulo 2 se introdujo la recurrencia deleción-contracción para contar árboles de expansión de una gráfica. En esta sección, utilizaremos la recurrencia deleción-contracción para reducir el cálculo del polinomio cromático de una gráfica (ejemplificada por la Figura 5.3.1) al cálculo de polinomios cromáticos que se pueden calcular fácilmente.
- 5.4: El Principio de Inclusión y Exclusión (Ejercicios)
- Esta sección contiene los problemas suplementarios relacionados con los materiales tratados en el Capítulo 5.
Miniaturas: inclusión: exclusión ilustrada por un diagrama de Venn para tres conjuntos. (CC BY-SA 3.0; Wikipedia).