Principio de adición

En combinatoria , el principio de adición ^{[ 1 ] [ 2 ]} o regla de la suma ^{[ 3 ] [ 4 ]} es un principio básico de conteo . Dicho de forma sencilla, es la idea intuitiva de que si tenemos A maneras de hacer algo y B maneras de hacer otra cosa y no podemos hacer ambas al mismo tiempo, entonces hay${\displaystyle A+B}$formas de elegir una de las acciones. ^{[ 3 ] [ 1 ]} En términos matemáticos, el principio de adición establece que, para conjuntos disjuntos A y B , tenemos${\displaystyle |A\cup B|=|A|+|B|}$, ^{[ 2 ]} siempre que la intersección de los conjuntos no tenga ningún elemento.

La regla de la suma es un hecho de la teoría de conjuntos , ^{[ 5 ]} como se puede ver con la ecuación mencionada anteriormente para la unión de conjuntos disjuntos A y B que es igual a |A| + |B|. ^{[ 6 ]}

El principio de adición se puede extender a varios conjuntos. Si${\displaystyle S_{1},S_{2},\ldots ,S_{n}}$son conjuntos disjuntos dos a dos, entonces tenemos: ^{[ 1 ] [ 2 ]}$${\displaystyle |S_{1}|+|S_{2}|+\cdots +|S_{n}|=|S_{1}\cup S_{2}\cup \cdots \cup S_{n}|.}$$Esta afirmación puede probarse a partir del principio de adición por inducción sobre n . ^{[ 2 ]}

Una persona ha decidido ir de compras hoy a una tienda, ya sea en la zona norte o en la zona sur de la ciudad. Si va a la zona norte, comprará en un centro comercial, una mueblería o una joyería (3 opciones). Si va a la zona sur, comprará en una tienda de ropa o en una zapatería (2 opciones).

Por lo tanto hay${\displaystyle 3+2=5}$Posibles tiendas en las que la persona podría terminar comprando hoy.

El principio de inclusión-exclusión (también conocido como principio de la criba ^{[ 7 ]} ) puede considerarse una generalización de la regla de la suma, ya que también enumera el número de elementos en la unión de algunos conjuntos (pero no requiere que los conjuntos sean disjuntos). Establece que si A ₁ , ..., A _n son conjuntos finitos, entonces ^{[ 7 ]}$${\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|+\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ +(-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.}$$

De manera similar, para un conjunto finito S dado, y dado otro conjunto A, si${\displaystyle A\subset S}$, entonces${\displaystyle |A^{c}|=|S|-|A|}$. ^{[ 8 ] [ 9 ]} Para probar esto, observe que${\displaystyle |A^{c}|+|A|=|S|}$por el principio de adición. ^{[ 9 ]}

El principio de adición se puede utilizar para demostrar la regla de Pascal de forma combinatoria. Para calcular${\displaystyle {\binom {n+1}{k}}}$, se puede ver como el número de maneras de elegir k personas de una habitación que contiene n niños y 1 maestro. Luego hay${\displaystyle {\binom {n}{k}}}$formas de elegir personas sin elegir al maestro, y${\displaystyle {\binom {n}{k-1}}}$formas de elegir personas que incluyan al maestro. Por lo tanto${\displaystyle {\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}}}$. ^{[ 10 ] : 83}

El principio de adición también puede utilizarse para demostrar el principio de multiplicación . ^{[ 2 ]}

• Principio combinatorio
• Regla del producto
• Principio de inclusión-exclusión