Hasta ahora hemos trabajado con relaciones binarias, es decir, aquellas que vinculan elementos de dos conjuntos y que, representadas en forma de tabla, poseen únicamente dos columnas. El prefijo «bi» en una relación binaria R hace referencia precisamente a este hecho: cada par ordenado (a,b) corresponde a una fila en una tabla de dos atributos.

Sin embargo, en muchos contextos resulta más útil y natural extender esta idea y permitir que una tabla contenga un número arbitrario de columnas. De esta manera, una relación con n atributos se denomina relación n-aria , y cada fila de la tabla representa una n-upla. Este enfoque constituye la base de las bases de datos relacionales, donde la información se organiza en tablas que reflejan de manera directa las generalizaciones de las relaciones matemáticas estudiadas.

El modelo de bases de datos relacionales, introducido por Edgar Codd en 1970, se fundamenta justamente en esta visión matemática de las relaciones. En dicho modelo, cada tabla es una relación n-aria, cada fila corresponde a un registro (o tupla) y cada columna se interpreta como un atributo que proviene de un dominio específico. Este marco formal ofrece varias ventajas:

• Permite describir y manipular la información con un alto grado de precisión.
• Facilita el diseño de sistemas en los que la integridad de los datos es prioritaria.
• Hace posible expresar consultas complejas mediante un lenguaje algebraico, que luego puede traducirse en implementaciones prácticas (como SQL).

Recordemos que una relación puede entenderse como un subconjunto de un producto cartesiano. Hasta el momento hemos trabajado principalmente con relaciones binarias, es decir, relaciones entre dos conjuntos. Sin embargo, es posible ampliar esta noción a más de dos conjuntos, permitiendo así representar situaciones más complejas y realistas.

Recordemos que, dados los conjuntos A_1,A_2,…,A_n, se define el producto cartesiano de A_1,A_2,…,A_n como

\[ A_1 \times A_2 \times \cdots \times A_n = \{ (x_1, x_2, \dots, x_n) : x_1 \in A_1, \, x_2 \in A_2, \, \dots, \, x_n \in A_n \} \]

Así, una relación n-aria puede verse como una colección de n-uplas que describen cómo interactúan elementos de distintos conjuntos (Epp 2020).

Definición 1: Relación n-aria

Dados los conjuntos A_1,…,A_n, se dice que R es una relación n-aria en A_1,…,A_n si R⊆A_1×A_2×⋯×A_n. A los conjuntos A_i se los denomina dominios de la relación y n es el grado de la relación.

En otras palabras, una relación n-aria está formada por n-uplas que vinculan simultáneamente elementos de varios conjuntos. Las relaciones binarias son un caso particular en el que n=2.

Ejemplo 1. Sea A={"Guillermo","María","Beatriz"} el conjunto de estudiantes y B={"Álgebra","Cálculo"} el conjunto de cursos. La relación R⊆A×B dada por

\[ S = \{ ("Guillermo", "Álgebra"), ("María", "Cálculo"), ("Beatriz", "Álgebra") \} \]

representa qué estudiante está inscrito en qué curso. Aquí tenemos una relación binaria (n=2), cuyos dominios son A y B.

Visto como base de datos, cada par ordenado corresponde a un registro, con dos campos: el estudiante y el curso. Los atributos de la relación son precisamente los conjuntos A (Estudiantes) y B (Cursos).

En el contexto de las bases de datos, a una relación n-aria R en A_1,…,A_n se denomina una tabla de datos, a cada elemento de R se lo llama registro; a cada entrada de un registro se la denomina campo; y a cada conjunto A_i se lo llama atributo.

Así, en el ejemplo anterior, tenemos que la tabla tiene dos atributos (Estudiantes y Curso), además tiene tres registros (tres elementos o tres filas), por ejemplo ("Guillermo" ,"Álgebra" ) es un registro; finalmente, cada registro tiene dos campos, así, el campo Estudiante del segundo registro es María.

Ejemplo 2. Ahora supongamos que además queremos incluir la calificación obtenida en cada curso. Introducimos un tercer conjunto C={0,10,20,30,40,50} que representa las notas posibles. La relación R⊆A×B×C puede expresarse como

\[ R = \{ ("Guillermo", "Álgebra", 40), ("María", "Cálculo", 50), ("Beatriz", "Álgebra", 20) \} \]

Se trata de una relación ternaria (n=3), cuyos dominios son A, B y C. En este caso, cada 3-upla constituye un registro, y cada valor dentro de la tupla es un campo. Los atributos de la relación son los conjuntos: Estudiantes (A), Cursos (B) y Calificaciones (C).

Estos ejemplos muestran cómo, al aumentar el número de dominios, crecen también el grado y la complejidad de la relación, dando lugar a estructuras tabulares que forman la base de las bases de datos relacionales.

En el contexto de las bases de datos relacionales, las operaciones que se realizan sobre las tablas están inspiradas en las operaciones de conjuntos. Estas operaciones permiten extraer, combinar o transformar información, y forman parte del llamado álgebra relacional

El álgebra relacional proporciona un conjunto de operadores bien definidos que reciben como entrada una o varias relaciones y producen como salida otra relación. De esta manera, se garantiza que el resultado de cualquier consulta pueda seguir siendo tratado con las mismas reglas, manteniendo la consistencia dentro del modelo relacional. Entre las operaciones más comunes se encuentran la selección, que permite filtrar registros según condiciones específicas; la proyección, que se utiliza para escoger columnas determinadas; y la reunión (join), que combina información de varias tablas en función de atributos compartidos.

A continuación, estudiaremos con detalle algunas de estas operaciones, ilustrando su definición formal y su aplicación práctica mediante ejemplos en tablas.

Definición 2: Operador selección.

Sean R una relación n-aria y C una condición sobre los elementos de A_1×⋯×A_n. Se define

\[ \sigma_C (R) = \{ (x_1, \dots, x_n) \in R : (x_1, \dots, x_n) \text{ cumple } C \} \]

El operador selección permite obtener únicamente los registros que cumplen cierta condición. Por ejemplo, si R es la relación ternaria Estudiantes–Cursos–Calificaciones de la sección anterior, podemos seleccionar únicamente los estudiantes que aprobaron con nota mayor o igual a 30.

\[ \sigma_{\text{Calificación} \ge 30}(R) = \{ ("Guillermo", "Álgebra", 40), ("María", "Cálculo", 50) \} \]

Definición 3: Operador proyección.

Sea R una relación n-aria y {i_1,…,i_m}⊆{1…n}. Para (x_1,…,x_n )∈R, se define

\[ \pi_{(i_1, \dots, i_m)} (R) = \{ (x_{i_1}, \dots, x_{i_m}) : (x_1, \dots, x_n) \in R \} \]

La proyección permite elegir solo algunos atributos de una relación, descartando los demás. Por ejemplo, si proyectamos la relación R de Estudiantes–Cursos–Calificaciones sobre los atributos Estudiante y Curso, se obtiene:

\[ \pi_{\text{Estudiante, Curso}} (R) = \{ ("Guillermo", "Álgebra"), ("María", "Cálculo"), ("Beatriz", "Álgebra") \} \]

Definición 4: Operador producto cartesiano.

Sean R⊆A_1×⋯×A_m y S⊆B_1×⋯×B_n dos relaciones. El producto cartesiano de R y S, denotado R×S, es la relación

\[ R \times S = \{ (x_1, \dots, x_m, y_1, \dots, y_n) : (x_1, \dots, x_m) \in R, \, (y_1, \dots, y_n) \in S \} \]

El operador producto cartesiano permite combinar todos los registros de una relación con todos los registros de otra. Si R tiene r registros y S tiene s, entonces R×S tendrá r⋅s registros.

Consideremos la relación S de Cursos–Docentes:

\[ S = \{ ("Álgebra", "Prof.Merino"), ("Cálculo", "Prof.Cueva") \} \]

Entonces el producto cartesiano es:

\[ R \times S = \left\{ \begin{array}{l} (\text{"Guillermo"}, \text{"Álgebra"}, 40, \text{"Álgebra"}, \text{"Prof. Merino"}), \\ (\text{"Guillermo"}, \text{"Álgebra"}, 40, \text{"Cálculo"}, \text{"Prof. Cueva"}), \\ (\text{"María"}, \text{"Cálculo"}, 50, \text{"Álgebra"}, \text{"Prof. Merino"}), \\ (\text{"María"}, \text{"Cálculo"}, 50, \text{"Cálculo"}, \text{"Prof. Cueva"}), \\ (\text{"Beatriz"}, \text{"Álgebra"}, 20, \text{"Álgebra"}, \text{"Prof. Merino"}), \\ (\text{"Beatriz"}, \text{"Álgebra"}, 20, \text{"Cálculo"}, \text{"Prof. Cueva"}) \end{array} \right\} \, . \]

El producto cartesiano por sí mismo genera todas las posibles combinaciones entre los registros de dos relaciones, lo cual puede resultar de utilidad para ciertos análisis. Sin embargo, en la práctica, rara vez se requiere toda esta información, ya que el número de combinaciones puede crecer rápidamente y producir resultados redundantes.

Lo interesante del producto cartesiano es que sirve como base para definir una de las operaciones más importantes del álgebra relacional: la reunión (join). De hecho, la reunión no es más que una combinación de dos operaciones: primero se aplica el producto cartesiano entre dos relaciones y luego una selección que filtra las combinaciones que cumplen cierta condición.

Definición 5: Operador reunión (Theta-join).

Sean \( R \subseteq A_1 \times \cdots \times A_m \) y \( S \subseteq B_1 \times \cdots \times B_n \) dos relaciones, y sea \( \theta \) una condición sobre los atributos de \( R \) y \( S \). La reunión de \( R \) y \( S \) bajo la condición \( \theta \), denotada

\[ R \bowtie_\theta S \]

se define como

\[ R \bowtie_\theta S = \sigma_\theta (R \times S) \]

La reunión (o join) permite combinar dos relaciones a partir de una condición sobre atributos comunes, eliminando las combinaciones que no son relevantes.

Siguiendo el ejemplo anterior, el producto cartesiano R×S genera todas las combinaciones posibles (como se mostró antes). Si ahora aplicamos la condición R."Curso"=S."Curso" (es decir, el atributo Curso en la relación R coincida con el atributo Curso de la relación S), obtenemos la reunión:

\[ R \bowtie_{R.\text{"Curso"} = S.\text{"Curso"}} S = \left\{ \begin{array}{l} (\text{"Guillermo"}, \text{"Álgebra"}, 40, \text{"Prof. Merino"}), \\ (\text{"María"}, \text{"Cálculo"}, 50, \text{"Prof. Cueva"}), \\ (\text{"Beatriz"}, \text{"Álgebra"}, 20, \text{"Prof. Merino"}) \end{array} \right\} \, . \]

La utilidad de la operación de reunión radica en que permite combinar información proveniente de distintas relaciones en una sola estructura. En el ejemplo anterior, a partir de la relación Estudiantes–Cursos–Calificaciones y de la relación Cursos–Docentes, hemos obtenido una nueva relación que incluye no solo el curso y la calificación de cada estudiante, sino también el docente responsable de dicho curso. De esta manera, la reunión enriquece los datos disponibles y facilita responder preguntas más complejas, como: ¿qué docente colocó calificaciones inferiores a 30?

Para esto, deberíamos hacer un par de operaciones más, primero seleccionar los registros que tengas calificaciones menores a 30:

\[ \sigma_{\text{"Calificación"} < 30} \left( R \bowtie_{R.\text{"Curso"} = S.\text{"Curso"}} S \right) = \left\{ (\text{"Beatriz"}, \text{"Álgebra"}, 20, \text{"Prof. Merino"}) \right\} \, . \]

Finalmente, tomemos una proyección para tener solo el nombre de los docentes:

\[ \pi_{\text{"Docente"}} \Big( \sigma_{\text{"Calificación"} < 30} \big( R \bowtie_{R.\text{"Curso"} = S.\text{"Curso"}} S \big) \Big) = \left\{ (\text{"Prof. Merino"}) \right\} \, . \]

En álgebra relacional, una consulta (en inglés, query) es una expresión que combina operadores como selección, proyección y reunión para responder una pregunta sobre los datos. El resultado de una consulta es siempre una nueva relación. En el ejemplo anterior, se tenía la pregunta «¿qué docente colocó calificaciones inferiores a 30?», la consulta (query) necesaria para responder fue:

\[ \pi_{\text{Docente}} \big( \sigma_{\text{Calificación} < 30} ( R \bowtie_{R.\text{Curso} = S.\text{Curso}} S ) \big) \]

y obtuvimos que el docente Merino es el único que colocó calificaciones inferiores a 30.

Consideremos el siguiente ejemplo del uso del álgebra relacional.

Ejemplo 3. En un Campeonato Universitario, cada equipo pertenece a un grupo (A o B) y se registran los partidos disputados. Trabajaremos con dos relaciones:

• Equipos: relación 3-aria. Dominios: nombres de equipos (Eq), Grupos, Ciudades.
• Partidos: relación 5-aria. Dominios: Jornadas, Equipos, Equipos, Goles locales (GolesL), Goles visitantes (GolesV).

Pregunta: ¿Qué equipos del Grupo A ganaron al menos un partido como visitantes?

Para dar respuesta, construyamos la consulta (query) como composición de operaciones.

% Filtrar partidos ganados por el visitante \[ P_1 = \sigma_{\text{GolesV} > \text{GolesL}} (\text{Partidos}) \] Con esto, la relación \(P_1\) contiene únicamente victorias de visitante.

% Anexar el grupo del equipo visitante \[ P_2 = P_1 \bowtie_{\text{Visitante} = \text{Eq}} \text{Equipos} \] Ahora cada fila lleva, además de los datos del partido, el Grupo y la Ciudad del equipo visitante.

% Quedarnos solo con visitantes del Grupo A \[ P_3 = \sigma_{\text{Grupo} = 'A'} (P_2) \]

% Obtener la lista de equipos \[ \text{Resultado} = \pi_{\text{Eq}} (P_3) \]

Resumiendo, la consulta es:

\[ \pi_{\text{Eq}} \Big( \sigma_{\text{Grupo} = 'A'} \big( \sigma_{\text{GolesV} > \text{GolesL}} (\text{Partidos}) \; \bowtie_{\text{Visitante} = \text{Eq}} \; \text{Equipos} \big) \Big) \]

Con este resultado, los equipos del Grupo A que ganaron al menos un partido como visitantes son Alfa (jornadas 2 y 3) y Beta (jornada 1).

Te invitamos a escribir la tabla resultante en cada paso para comprobar las operaciones realizadas.

En las bases de datos relacionales es fundamental poder identificar de manera única cada registro de una tabla. Para ello se utilizan las claves, que pueden ser primarias o compuestas.

Definición 6: Clave primaria.

Sean R una relación n-aria en A_1,…,A_n. Se dice que el atributo A_i es una clave primaria para R si para todo x,y∈R se cumple que

\[ x_i = y_i \quad \text{implica} \quad x = y \]

Es decir, no existen dos registros diferentes con el mismo valor en el atributo A_i.

Aquí el atributo ID es una clave primaria, pues cada valor de ID identifica de forma única a un estudiante.

Definición 7: Clave Compuesta

Sean R una relación n-aria en A_1,…,A_n. Se dice que los atributos A_(i_1 ),…,A_(i_m ) forman una clave compuesta para R si para todo x,y∈R se cumple que

\[ (x_{i_1}, \dots, x_{i_m}) = (y_{i_1}, \dots, y_{i_m}) \quad \text{implica} \quad x = y \]

En este caso, la combinación de varios atributos permite distinguir de manera única cada registro.

Ejemplo 5. Consideremos la relación de Matrículas:

En esta tabla no hay un único atributo que identifique a los registros: un mismo estudiante puede estar en varios cursos, y un curso puede tener varios estudiantes. La clave compuesta está formada por la pareja (Estudiante, Curso), que garantiza que no se repita un mismo registro.

De esta manera, vemos que las claves permiten garantizar la unicidad de los registros en una base de datos relacional. Según el contexto, puede bastar con un solo atributo que actúe como clave primaria, o puede ser necesario recurrir a la combinación de varios atributos formando una clave compuesta. Estos mecanismos resultan fundamentales para mantener la coherencia y la organización de la información dentro de las tablas.

Además, las claves no solo cumplen un papel de identificación, sino que también facilitan la creación de vínculos entre distintas relaciones. En sistemas más complejos, un registro de una tabla puede estar relacionado con registros de otra a través de atributos comunes, y son precisamente las claves las que hacen posible establecer estas conexiones de manera confiable. Así, las claves primarias y compuestas se convierten en la base para que las bases de datos no sean simplemente colecciones de tablas aisladas, sino sistemas estructurados en los que la información puede integrarse y consultarse de forma eficiente.

Contar es una de las actividades más naturales que realizamos a diario: desde calcular cuántos libros hay en un estante hasta determinar el número de posibles contraseñas en un sistema. En matemáticas, esta idea se formaliza a través del concepto de cardinalidad. Recordemos que la cardinalidad de un conjunto A, denotada por |A|, indica cuántos elementos contiene dicho conjunto.

Así, realizar un conteo no es más que determinar la cardinalidad de un conjunto asociado a un problema. A partir de esta noción básica, desarrollaremos principios que nos permiten calcular de manera ordenada y eficiente el número de formas en que ciertos eventos o elecciones pueden ocurrir, sin necesidad de listar explícitamente todas las posibilidades.

Ejemplo 1. Supongamos que Juan debe elegir una contraseña formada por un número del 1 al 5 y una vocal. Podemos representar los conjuntos como

\[ N = \{1,2,3,4,5\}, \quad V = \{a,e,i,o,u\} \]

Las posibles contraseñas corresponden al producto cartesiano N×V. Si listamos todas las opciones, obtenemos:

\[ \{ 1a, 1e, 1i, 1o, 1u, \; 2a, 2e, 2i, 2o, 2u, \; 3a, \dots, 5u \} \]

En total, |N|⋅|V|=5×5=25 posibles contraseñas.

En este caso fue sencillo en listar todas las posibilidades porque el conjunto es pequeño. Pero, ¿qué pasaría si Juan tuviera que generar una contraseña de 8 caracteres, que incluya al menos una letra y al menos un número? Claramente, en ese escenario la estrategia de listar dejaría de ser práctica, y necesitaremos principios más generales de conteo para encontrar la respuesta.

10.1. Principio multiplicativo

Imagina nuevamente el caso de Juan y sus contraseñas. Debe escoger un número entre cuatro opciones {1,2,3,4} y una vocal entre cinco opciones {a,e,i,o,u}. Primero elige el número: tiene 4 formas distintas de hacerlo. Después elige la vocal: tiene 5 posibilidades.

Si pensamos en todo el proceso, vemos que la elección completa (número + vocal) puede realizarse de

4⋅5=20

formas distintas. Lo que está ocurriendo aquí no es más que analizar el producto cartesiano de los conjuntos de posibilidades en cada tarea:

\[ N = \{1,2,3,4\}, \quad V = \{a,e,i,o,u\}, \quad N \times V \]

Y calcular cuántos pares distintos se pueden formar equivale a determinar la cardinalidad de ese producto cartesiano:

\[ |N \times V| = |N| \cdot |V| = 4 \cdot 5 = 20 \]

De manera general, el

principio multiplicativo

establece que cuando una tarea puede dividirse dos pasos sucesivos e independientes, el número total de formas de realizar la tarea es el producto de las posibilidades de cada paso. En otras palabras: si una tarea se divide en dos etapas independientes, y la primera puede hacerse de n_1 maneras y la segunda de n_2 maneras, entonces en total existen n_1⋅n_2 formas distintas de realizarla.

De manera general, si hay m etapas independientes, si la primera etapa se puede realizar de n_1 maneras, la segunda de n_2 maneras, y así hasta la etapa m con n_m maneras, entonces el total es:

\[ n_1 \cdot n_2 \cdot \dots \cdot n_m \]

Ejemplo 2. Beatriz quiere elegir un almuerzo en la cafetería: primero debe escoger un plato fuerte y luego una bebida. Si los platos fuertes son {"pollo,pescado,carne"} (3 opciones) y las bebidas son {"agua,jugo"} (2 opciones), entonces existen

3⋅2=6

formas distintas de combinar plato y bebida.

Ejemplo 3. Beatriz, en otra cafetería, tiene también dos opciones de postre {"fruta,helado"}, así que debe seleccionar su almuerzo combinando 3 opciones de plato fuerte, 2 opciones de bebida y 2 opciones de postre. En esta situación, Beatriz tiene

3⋅2⋅2=12

opciones distintas de almuerzo.

A veces es útil visualizar el principio multiplicativo mediante un diagrama en forma de árbol. En este tipo de representación, cada rama corresponde a una elección posible en una etapa, y de cada una de ellas surgen nuevas ramas con las elecciones de la siguiente etapa.

De esta manera, el número total de caminos distintos coincide con el número total de formas de realizar la tarea completa. Esta visualización nos permite entender con claridad cómo se combinan las opciones en cada paso y por qué el conteo final se obtiene multiplicando las posibilidades.

Ejemplo 4. Consideremos el alfabeto {A,B,C,D,E} y construyamos cadenas de longitud 4 sin permitir repeticiones de letras. ¿Cuántas de estas cadenas existen?

La cadena se forma en cuatro pasos sucesivos:

• Para la primera posición hay 5 opciones (cualquiera de las letras).
• Una vez elegida la primera letra, quedan 4 opciones para la segunda.
• Luego, para la tercera posición, solo quedan 3 opciones.
• Finalmente, para la cuarta posición, restan 2 opciones.

Por el principio multiplicativo, el número total de cadenas es:

5⋅4⋅3⋅2=120.

Ejemplo 5. ¿Cuántas de esas cadenas empiezan con la letra B?

Si fijamos B en la primera posición, el problema se reduce a formar las tres letras restantes con el conjunto {A,C,D,E}, sin repeticiones.

• Segunda posición: 4 maneras.
• Tercera posición: 3 maneras.
• Cuarta posición: 2 maneras.

Así, el número de cadenas es:

4⋅3⋅2=24.

Ejemplo 6. Ahora pensemos en cadenas de ocho bits que comienzan con 101. ¿Cuántas de estas cadenas existen?

Si la cadena comienza con 101, los primeros tres bits ya están fijos, y nos quedan cinco posiciones por completar. Cada una de esas posiciones puede tomar dos valores posibles (0 o 1). Por tanto, hay:

• \(2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 2^5 = 32\)

cadenas que empiezan con 101.

En muchas situaciones no se trata de realizar varias acciones a la vez, sino de elegir entre opciones excluyentes. Por ejemplo, supongamos que María va a la cafetería y debe decidir entre tomar un café o un té. El café puede pedirse en dos presentaciones (americano o expreso), mientras que el té puede pedirse en tres sabores distintos (limón, menta o frutos rojos).

Dado que María no puede pedir café y té al mismo tiempo, el total de formas de elegir una bebida es:

2+3=5.

Este razonamiento nos lleva al principio aditivo: Si una tarea se puede realizar de n_1 maneras y una segunda tarea se puede realizar de n_2 maneras, y si no se pueden realizar las dos a la vez, entonces hay \(n_1 + n_2\) maneras de realizar alguna de ellas.

De manera más general, si una tarea puede realizarse de n_1 maneras, otra tarea de n_2 maneras, otra más de n_3 maneras, y así sucesivamente hasta una tarea de n_m maneras, y ninguna de estas tareas puede realizarse simultáneamente, entonces existen en total:

• \(n_1 + n_2 + n_3 + \cdots + n_m\)

formas posibles de realizar una de ellas.

Ejemplo 7. Imagina que Guillermo quiere elegir cómo trasladarse a la universidad. Tiene dos opciones:

• Tomar un bus, con 3 rutas posibles.
• Usar una aplicación de transporte privado, con 2 conductores disponibles.

Dado que no puede usar bus y aplicación a la vez, el total de formas de transporte posibles es

3+2=5.

Ejemplo 8. Un caso real donde se evidencia la fuerza del conteo lo encontramos en la propagación del virus Melissa (Johnsonbaugh 2018), que a fines de los 90 causó serios problemas en sistemas informáticos.

El virus se transmitía por correo electrónico: al abrir el archivo adjunto, el macro reenviaba automáticamente el mensaje a las primeras 50 direcciones de la libreta de contactos. Cada nuevo receptor que abre el adjunto hace exactamente lo mismo (reenviar a 50 nuevas direcciones). Supón que en cada iteración las direcciones alcanzadas son disjuntas de las anteriores.

• ¿Cuántos correos nuevos se generan en la t-ésima iteración?
• ¿Cuántos correos en total se han generado tras k iteraciones?
• Evalúa para k=4.

Cada receptor genera 50 envíos nuevos; por tanto, el número de correos nuevos en la t-ésima iteración es

• \(50 \cdot 50 \cdot 50 \cdots 50 = 50^t\)

pues en cada «nivel» del árbol de reenvíos se multiplican por 50 las posibilidades respecto al nivel anterior.

El total hasta la k-ésima iteración es la suma de las olas (excluyentes) de correos nuevos:

• \(50 + 50^2 + \cdots + 50^k = \sum_{t=1}^{k} 50^t = \frac{50(50^k - 1)}{49}\)

Para k=4:

• \(50 + 50^2 + 50^3 + 50^4 = 50 + 2,500 + 125,000 + 6,250,000 = 6,377,550\)

Revisemos algunos ejemplos más, adaptados del libro de Johnsonbaugh (2018).

Ejemplo 9. En una feria tecnológica se exhiben dispositivos de tres categorías: 5 laptops distintas, 3 tablets distintas y 2 teléfonos distintos. ¿Cuántas maneras existen de elegir dos dispositivos de categorías diferentes?

Solución.

Solución. Analizamos caso por caso aplicando el principio multiplicativo:

• Elegir una laptop y una tablet: 5⋅3=15 maneras.
• Elegir una laptop y un teléfono: 5⋅2=10 maneras.
• Elegir una tablet y un teléfono: 3⋅2=6 maneras.

Ahora, como estas elecciones corresponden a categorías excluyentes (no pueden darse simultáneamente), usamos el principio aditivo para sumar los resultados:

15+10+6=31.

Es decir, hay 31 formas distintas de elegir dos dispositivos de categorías diferentes en la feria.

Ejemplo 10. Un comité de seis personas (Alicia, Benjamín, Consuelo, Adolfo, Eduardo y Francisco) debe seleccionar un presidente, un secretario y un tesorero.

• ¿De cuántas maneras pueden hacerlo?

Para designar los tres cargos se procede en tres pasos sucesivos: primero se elige al presidente (6 maneras), luego al secretario (5 maneras) y finalmente al tesorero (4 maneras). Por el principio multiplicativo, el número total de formas de hacerlo es

6⋅5⋅4=120

• ¿De cuántas maneras pueden hacerlo si Eduardo debe ocupar uno de los puestos?

Si Eduardo es presidente, quedan 5⋅4=20 formas de asignar los otros dos cargos. Si es secretario, también hay 5⋅4=20 posibilidades, y si es tesorero, igualmente 5⋅4=20. Dado que estos casos son excluyentes, por el principio aditivo el número total es

20+20+20=60.

Otra forma de verlo es asignar primero el puesto a Eduardo (3 opciones), luego el cargo más alto que queda (5 opciones) y finalmente el último cargo (4 opciones). Así, por el principio multiplicativo, existen 3⋅5⋅4=60 formas de hacerlo.

En ocasiones, al contar elementos que pertenecen a varios conjuntos, corremos el riesgo de contar dos veces a aquellos que están en la intersección. El principio de inclusión/exclusión nos ofrece una fórmula ordenada para corregir ese exceso en el conteo y obtener el número exacto de elementos en una unión de conjuntos.

Teorema 1: Principio de inclusión-exclusión para dos conjuntos.

Sean A₁ y A₂ dos conjuntos finitos. Entonces:

\(|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|\)

Es decir, sumamos las cardinalidades de ambos conjuntos y restamos la intersección, para evitar duplicar los elementos que pertenecen a ambos.

Ejemplo 11. En una clase hay 30 estudiantes que llevan Matemáticas y 25 que llevan Física.

De ellos, 10 están inscritos en ambas materias. ¿Cuántos estudiantes hay en total?

Si simplemente sumáramos 30+25=55, estaríamos contando dos veces a los 10 estudiantes que están en ambos cursos. Aplicando el principio de inclusión-exclusión:

$$|M \cup F| = |M| + |F| - |M \cap F| = 30 + 25 - 10 = 45$$

Por lo tanto, 45 estudiantes es el total.

Para tres conjuntos, el principio toma la siguiente forma: Sean A_1, A_2 y A_3 tres conjuntos finitos. Entonces:

$$|A_1 \cup A_2 \cup A_3| = |A_1| + |A_2| + |A_3| - (|A_1 \cap A_2| + |A_1 \cap A_3| + |A_2 \cap A_3|) + |A_1 \cap A_2 \cap A_3|$$

La idea es: primero se suman todos los conjuntos, luego se restan las intersecciones dobles (porque cada elemento común fue contado dos veces), y finalmente se suma la intersección triple (que había quedado restada de más).

Finalmente, para n conjuntos finitos, la fórmula general es:

La fórmula sigue un patrón de alternancia de signos: se suman todas las cardinalidades individuales; se restan todas las intersecciones de dos en dos; se suman las intersecciones triples; se restan las intersecciones cuádruples, y así sucesivamente.

De este modo, cada elemento de la unión aparece contado exactamente una vez, sin repeticiones.

El principio del palomar, también llamado principio de las casillas o principio de Dirichlet (Epp 2020), establece que si se busca distribuir k+1 objetos en k cajas, entonces al menos una caja debe contener al menos dos objetos.

Este principio, formulado por primera vez de manera formal por Dirichlet. Se ilustra de manera sencilla pensando en palomas que vuelan hacia casillas: si n palomas vuelan hacia m casillas, y n>m, entonces alguna casilla debe contener al menos dos palomas.

De manera más general: si se distribuyen N objetos en k cajas, entonces existe al menos una caja que contiene al menos

$$\left\lceil \tfrac{N}{k} \right\rceil$$

objetos. Aquí el símbolo ⌈⋅⌉ denota la función techo, que redondea cualquier número real hacia arriba hasta el entero más cercano. Por ejemplo, ⌈3.2⌉=4 y ⌈5⌉=5. Este redondeo es necesario porque, aunque N/k puede no ser un número entero, el número de objetos en una caja siempre debe ser un número natural.

Ejemplo 12. En un grupo de 13 personas, ¿debe haber al menos dos que nacieron en el mismo mes?

Aquí tenemos N=13 objetos (personas) y k=12 cajas (meses del año). Aplicando el principio del palomar:

$$\left\lceil \tfrac{13}{12} \right\rceil = 2$$

Esto significa que, inevitablemente, al menos dos personas comparten el mismo mes de nacimiento.

Ejemplo 13. Un cajón contiene 10 calcetines blancos y 10 calcetines negros. Si se extraen calcetines al azar sin mirar, ¿cuál es el número mínimo que se debe sacar para asegurarse de obtener un par del mismo color?

Las «cajas» son los dos colores: blanco y negro (k=2). Queremos garantizar que haya al menos una caja con 2 objetos. Aplicando el principio del palomar, si se extraen

$$\left\lceil \tfrac{3}{2} \right\rceil = 2$$

no basta, porque podríamos tener uno blanco y uno negro. Pero al extraer 3 calcetines, el principio asegura que al menos dos corresponden al mismo color.

Así, el número mínimo de calcetines a sacar es 3.