Forum Docentis

Combinatoria

Elena Castilla^1,2, Pedro J. Chocano^1*

¹Departamento de Matemática Aplicada, CC. e Ingeniería de los Materiales y Tec. Electrónica, URJC, España

²Instituto de Matemática Interdisciplinar (IMI), UCM, España

^*Autor de correspondencia: pedro.chocano@urjc.es

Introducción

Dar una definición de combinatoria suele ser complicado debido a las numerosas interacciones que esta tiene en diversas áreas de las matemáticas. Podemos decir que la combinatoria es el área de las matemáticas que aborda problemas de conteo o enumeración (estudia las distintas maneras de hacer agrupaciones o configuraciones de un conjunto o estructura matemática), la existencia de estructuras con propiedades previamente prefijadas (por ejemplo grafos con un grupo de automorfismos fijado), la construcción de las estructuras previas y la optimización de las mismas.

La palabra “Combinatoria” no fue usada hasta el siglo XVII por Leibniz en su Dissertatio de Arte Combinatoria. Sin embargo, son muchas las ocasiones en las que se habían empleado técnicas combinatorias a lo largo de la historia. Por ejemplo, Xenocrates de Chalcedon (siglo IV a.C) estudió el número de sílabas diferentes que se podían formar en la lengua griega. Otro ejemplo son los cuadrados mágicos (matrices cuadradas cuyas filas y columnas suman lo mismo), que aparecieron por primera vez en el I Ching, un libro chino del siglo XII a.C. Treinta siglos despúes, Alberto Durero incluyó un cuadrado mágico en su cuadro “Melancolía I”. Para el lector interesado en la historia y raíces de la combinatoria recomendamos la lectura de [1], entre otros.

En este artículo introducimos algunos conceptos básicos en combinatoria: el factorial, los números combinatorios y el triángulo de Pascal, así como las técnicas de conteo básicas.

1. Factorial y Números Combinatorios

1.1 Factorial y Número Combinatorio

Definición 1.1 (Factorial). Dado un número natural n ∈ ℕ, se llama factorial de n y se denota como n! a la siguiente cantidad:

n! = n . (n − 1) . (n − 2) ...2 . 1.

Por convenio, se considera que 0! = 1.

Definición 1.2 (Número Combinatorio). Dados n, k ∈ ℕ, k ≤ n, se denomina coeficiente binomial de n en k, y se denota como $\left(\begin{array}{l}n\\ k\end{array}\right)$, a la siguiente expresión:

$$\left(\begin{array}{l}n\\ k\end{array}\right)=\frac{n!}{k!(n-k)!.}$$

Teorema 1.1. Para todo n ≥ 0 se cumple:

$$\left(\begin{array}{l}n\\ n\end{array}\right)=\left(\begin{array}{l}n\\ 0\end{array}\right)=1.$$

Demostración. Basta con escribir la definición de coeficiente binomial.

□

Teorema 1.2 (Teorema de Pascal). Para todo n ≥ 0, k > 0 se cumple:

$$\left(\begin{array}{l}n\\ k\end{array}\right)=\left(\begin{array}{l}n-1\\ k-1\end{array}\right)+\left(\begin{array}{c}n-1\\ k\end{array}\right).$$

Demostración. Para ver que se cumple la igualdad vamos a desarrollar la parte de la derecha hasta llegar a la de la izquierda:

$$\begin{array}{rl}\left(\begin{array}{c}n-1\\ k-1\end{array}\right)+\left(\begin{array}{c}n-1\\ k\end{array}\right)& =\frac{(n-1)!}{(n-k)!(k-1)!}+\frac{(n-1)!}{(n-1-k)!k!}=\frac{(n-1)!k+(n-1)!(n-k)}{(n-k)!k!}\\ & =\frac{(n-1)!n}{(n-k)!k!}=\frac{n!}{(n-k)!k!}=\left(\begin{array}{c}n\\ k\end{array}\right).\end{array}$$

□

1.2 Triángulo de Pascal

Una forma de representar de manera visual los coeficientes binomiales y obtener un cálculo de los mismos de manera recursiva es mediante el conocido triángulo de Pascal. La fila n-ésima con la columna k-ésima se corresponderá con el coeficiente binomial $\left(\begin{array}{l}n\\ k\end{array}\right)$

$$\begin{array}{cccccccccccccc}n=0& & & & & & & 1& & & & & & \\ n=1& & & & & & 1& & 1& & & & & \\ n=2& & & & & 1& & 2& & 1& & & & \\ n=3& & & & 1& & 3& & 3& & 1& & & \\ n=4& & & 1& & 4& & 6& & 4& & 1& & \\ n=5& & 1& & 5& & 10& & 10& & 5& & 1& \\ n=6& 1& & 6& & 15& & 20& & 15& & 6& & 1\end{array}$$

Usando el Teorema de Pascal, tenemos la fórmula recursiva necesaria para calcular los elementos de la fila n a partir de la fila n − 1. Veamos esto último con un par de sencillos ejemplos:

◾ Vamos a obtener la fila 4 partir de la fila 3, es decir, $\left(\begin{array}{c}4\\ i\end{array}\right)$ con i = 1, 2, 3, pues $\left(\begin{array}{l}4\\ 0\end{array}\right)=\left(\begin{array}{l}4\\ 4\end{array}\right)=1$. En la fila tres tenemos que $\left(\begin{array}{l}3\\ 0\end{array}\right)=1,\left(\begin{array}{l}3\\ 1\end{array}\right)=3,\left(\begin{array}{l}3\\ 2\end{array}\right)=3\text{ y }\left(\begin{array}{l}3\\ 3\end{array}\right)=1$. Si usamos el teorema de Pascal obtenemos que $\left(\begin{array}{l}4\\ 1\end{array}\right)=\left(\begin{array}{l}3\\ 0\end{array}\right)+\left(\begin{array}{l}3\\ 1\end{array}\right)=1+3=4,\left(\begin{array}{l}4\\ 2\end{array}\right)=\left(\begin{array}{l}3\\ 1\end{array}\right)+\left(\begin{array}{l}3\\ 2\end{array}\right)=3+3=6$ y que $\left(\begin{array}{l}4\\ 3\end{array}\right)=\left(\begin{array}{l}3\\ 2\end{array}\right)+\left(\begin{array}{l}3\\ 3\end{array}\right)=3+1=4$ (véase Figura 1).

Figura 1. Obtenemos $\left(\begin{array}{l}4\\ i\end{array}\right)$ con i = 1, 2, 3.

◾ Vamos a obtener $\left(\begin{array}{l}7\\ 4\end{array}\right)$ a partir de elementos de la sexta fila. Aplicando la fórmula recursiva tenemos que $\left(\begin{array}{l}7\\ 4\end{array}\right)=\left(\begin{array}{l}6\\ 3\end{array}\right)+\left(\begin{array}{l}6\\ 4\end{array}\right)=20+15=35$.

Vamos a ver algunas relaciones o aplicaciones de los números combinatorios y el triángulo de Pascal.

1.2.1 La sucesión de Fibonacci

La famosa sucesión de Fibonacci se define de manera recursiva como:

F₀ =0, F₁ = 1 y Fn = F_n−1 + F_n−2n ≥ 2.

Por tanto, tenemos:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

Teorema 1.3. $F_{n+1}={\sum }_{k=0}^{[n/2]}\left(\begin{array}{c}n-k\\ k\end{array}\right)$donde [n/2] denota la parte entera de la división.

Demostración. Probaremos el resultado por inducción. Veamos los dos primeros casos.

$$\sum _{k=0}^0\left(\begin{array}{c}0-k\\ k\end{array}\right)=1=F_1\sum _{k=0}^{[1/2]}\left(\begin{array}{c}1-k\\ k\end{array}\right)=\left(\begin{array}{l}1\\ 0\end{array}\right)=F_2.$$

Supongamos que el resultado es cierto para n y n + 1, demostremos el caso n + 2. Dado que F_n+2 = F_n+1 + F_n basta con comprobar si la siguiente igualdad es correcta:

$$\sum _{k=0}^{[(n+1)/2]}\left(\begin{array}{c}n+1-k\\ k\end{array}\right)=\sum _{k=0}^{[n/2]}\left(\begin{array}{c}n-k\\ k\end{array}\right)+\sum _{k=0}^{[(n-1)/2]}\left(\begin{array}{c}n-1-k\\ k\end{array}\right).$$

Para ello vamos a desarrollar la parte de la derecha. Reajustando los subíndices del segundo sumatorio, podemos obtener:

$$\sum _{k=0}^{[n/2]}\left(\begin{array}{c}n-k\\ k\end{array}\right)+\sum _{k=0}^{[(n-1)/2]}\left(\begin{array}{c}n-1-k\\ k\end{array}\right)=\sum _{k=0}^{[n/2]}\left(\begin{array}{c}n-k\\ k\end{array}\right)+\sum _{k=1}^{[(n-1)/2]+1}\left(\begin{array}{c}n-k\\ k-1\end{array}\right).$$

Supongamos que n + 1 es impar, luego [(n + 1)/2] = [n/2] = [(n − 1)/2] − 1. Usando el Teorema de Pascal obtenemos:

$$\sum _{k=0}^{[n/2]}\left(\begin{array}{c}n-k\\ k\end{array}\right)+\sum _{k=1}^{[n/2]}\left(\begin{array}{c}n-k\\ k-1\end{array}\right)=\left(\begin{array}{c}n-k\\ 0\end{array}\right)+\sum _{k=1}^{[n/2]}\left(\begin{array}{c}n+1-k\\ k\end{array}\right)=\sum _{k=0}^{[(n+1)/2]}\left(\begin{array}{c}n+1-k\\ k\end{array}\right)=F_{n+2}$$

Podemos repetir un argumento similar cuando n + 1 es par.

□

Veamos cómo localizar la sucesión de Fibonacci en el triángulo de Pascal a partir de la fórmula obtenida mediante unos sencillos ejemplos. La idea fundamental es observar las diagonales en el triángulo de Pascal, ver Figura 2.

Figura 2. Sucesíon de Fibonacci en el tríangulo de Pascal.

◾ F₄ usando la fórmula obtenida en el anterior resultado se puede obtener como:

$$F_4=\sum _{k=0}^{[3/2]}\left(\begin{array}{c}3-k\\ k\end{array}\right)=\left(\begin{array}{l}3\\ 0\end{array}\right)+\left(\begin{array}{l}2\\ 1\end{array}\right)=1+2=3.$$

Es decir, sumando los elementos de la diagonal que comienza en la cuarta fila.

◾ F₆ se puede expresar como:

$$F_6=\sum _{k=0}^{[5]/2}\left(\begin{array}{c}5-k\\ k\end{array}\right)=\left(\begin{array}{l}5\\ 0\end{array}\right)+\left(\begin{array}{l}4\\ 1\end{array}\right)+\left(\begin{array}{l}3\\ 2\end{array}\right)=1+4+3=8.$$

O lo que es lo mismo, como la suma de los elementos de la diagonal que comienza en la sexta fila.

1.2.2 El número e

Consideremos el producto de los elementos de cada fila en el triángulo de Pascal

$$p_n=\prod _{k=0}^n\left(\begin{array}{l}n\\ k\end{array}\right)=\prod _{k=0}^n\frac{n!}{(n-k)!k!}=n{!}^{n+1}\prod _{k=0}^n\frac{1}{k{!}^2}.$$

La razón de la sucesión formada por estos productos es:

$$r_n=\frac{p_{n+1}}{p_n}=\frac{(n+1){!}^{n+2}\prod _{k=0}^{n+1}\frac{1}{k{!}^2}}{n{!}^{n+1}\prod _{k=0}^n\frac{1}{k{!}^2}}=\frac{(n+1){!}^n}{n{!}^{n+1}}=\frac{(n+1{)}^n}{n!}$$

A su vez, la razón de la sucesión formada por r_n es:

$$\frac{r_{n+1}}{r_n}=\frac{\frac{p_{n+2}}{p_{n+1}}}{\frac{p_{n+1}}{p_n}}=\frac{p_{n+2}{p}_n}{p_{n+1}^2}=r_{n+1}\frac{1}{r_n}=\frac{(n+2{)}^{n+1}}{(n+1)!}\frac{n!}{(n+1{)}^n}=\frac{(n+2{)}^{n+1}}{(n+1{)}^{n+1}}={\left(\frac{n+2}{n+1}\right)}^{n+1}$$

Si tomamos el límite cuando n tiende a infinito en la razón que acabamos de obtener llegamos precisamente al número e:

$$\underset{n⟶\mathrm{\infty }}{lím}{\left(\frac{n+2}{n+1}\right)}^{n+1}=e.$$

Otras relaciones interesantes pueden encontrarse con otros célebres números como por ejemplo el número π o sucesiones importantes como los números de Catalan (consultar [2] para más información e historia).

1.2.3 Fractales

Si coloreamos los números que aparecen en el triángulo de Pascal siguiendo patrones de divisibilidad podemos obtener algunos fractales. Por ejemplo, si pintamos los números que aparecen en el triángulo de Pascal que sean pares, obtenemos el triángulo de Sierpiński (ver Figura 3).

Figura 3. Tríangulo de Sierpiński.

1.2.4 Matrices de Riordan

Si consideramos el triángulo de Pascal como una matriz, obtenemos una matriz triangular inferior infinito dimensional invertible:

$$\left(\begin{array}{cccccccc}1& & & & & & & \\ 1& 1& & & & & & \\ 1& 2& 1& & & & & \\ 1& 3& 3& 1& & & & \\ 1& 4& 6& 4& 1& & & \\ 1& 5& 10& 10& 5& 1& & \\ 1& 6& 15& 20& 15& 6& 1& \\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& \ddots \end{array}\right)$$

Esta matriz forma parte de una familia de matrices conocidas como matrices de Riordan. Dichas matrices son muy utilizadas no solamente en combinatoria, también en otras áreas de las matemáticas como teoría de grafos, polinomios ortogonales, teoría de grupos, etc. El lector interesado puede consultar más información en [3].

1.3 Binomio de Newton

El Binomio de Newton nos permite calcular la forma de cualquier potencia de un binomio. Esta viene dada por:

$$(x+y{)}^n=\sum _{k=0}^n\left(\begin{array}{l}n\\ k\end{array}\right)x^{n-k}{y}^k.$$

Demostración. Probemos el resultado por inducción. El caso base n = 1 se cumple trivialmente. Supongamos que el resultado es cierto para n > 1 y demostremos el caso n + 1. Tenemos pues las siguientes igualdades donde estamos usando la hipótesis de inducción en la segunda:

$$\begin{array}{rl}(x+y{)}^{n+1}& =(x+y)(x+y{)}^n=(x+y)\sum _{k=0}^n\left(\begin{array}{c}n\\ k\end{array}\right)x^{n-k}{y}^k=x\sum _{k=0}^n\left(\begin{array}{c}n\\ k\end{array}\right)x^{n-k}{y}^k+y\sum _{k=0}^n\left(\begin{array}{c}n\\ k\end{array}\right)x^{n-k}{y}^k\\ & =\sum _{k=0}^n\left(\begin{array}{c}n\\ k\end{array}\right)x^{n-k+1}{y}^k+\sum _{k=0}^n\left(\begin{array}{c}n\\ k\end{array}\right)x^{n-k}{y}^{k+1}.\end{array}$$

Vamos a ajustar las potencias del segundo término para que coincidan con las del primer término, esto es sencillo si empezamos a contar en k = 1, terminamos en n+1 y cambiamos $x^{n-k}\text{ y }{y}^{k+1}\text{ por }{x}^{n-(k-1)}\text{ y }{y}^{(k-1)+1}$ respectivamente, es decir,

$$\sum _{k=0}^n\left(\begin{array}{l}n\\ k\end{array}\right)x^{n-k+1}{y}^k+\sum _{k=0}^n\left(\begin{array}{l}n\\ k\end{array}\right)x^{n-k}{y}^{k+1}=\sum _{k=0}^n\left(\begin{array}{l}n\\ k\end{array}\right)x^{n-k+1}{y}^k+\sum _{k=1}^{n+1}\left(\begin{array}{c}n\\ k-1\end{array}\right)x^{n-k+1}{y}^k.$$

Sacando el primer término del primer sumatorio y del segundo el último, obtenemos:

$$\left(\begin{array}{l}n\\ 0\end{array}\right)x^{n+1}+\sum _{k=1}^n\left(\begin{array}{c}n\\ k-1\end{array}\right)x^{n-k+1}{y}^k+\sum _{k=1}^n\left(\begin{array}{l}n\\ k\end{array}\right)x^{n-k+1}{y}^k+\left(\begin{array}{l}n\\ n\end{array}\right)y^{n+1}.$$

Si simplificamos en la anterior expresión y usamos el Teorema de Pascal llegamos a el resultado deseado:

$$x^{n+1}+\sum _{k=1}^n\left(\begin{array}{c}n+1\\ k\end{array}\right)x^{n-k+1}{y}^k+y^{n+1}=\sum _{k=0}^{n+1}\left(\begin{array}{c}n+1\\ k\end{array}\right)x^{n-k}{y}^k.$$

Nótese que los coeficientes que aparecen acompañando a las potencias de x e y en el desarrollo previo se corresponden con los números que aparecen en la fila n-ésima del triángulo de Pascal.

Ejercicio 1.3. Demuestra que para todo n ≥ 1 se tiene

$$\left(\begin{array}{l}n\\ 0\end{array}\right)-\left(\begin{array}{l}n\\ 1\end{array}\right)+\left(\begin{array}{l}n\\ 2\end{array}\right)-\dots (-1{)}^n\left(\begin{array}{l}n\\ n\end{array}\right)=0.$$

Solución: Basta con aplicar el binomio de Newton a (1 − 1)ⁿ.

Ejercicio 1.4. Demuestra que si p es un número primo entonces p divide a $\left(\begin{array}{l}p\\ k\end{array}\right)$ si 1 < k < p.

2. Combinatoria

En esta sección haremos una breve introducción a la combinatoria como herramienta para contar el número de posibles situaciones que se pueden dar al ordenar o agrupar un número finito de acciones o elementos. Primero introduciremos algunos conceptos claves en la técnica del conteo.

2.1 Reglas básicas de conteo

Principio del producto: Si una primera acción se puede hacer de n₁ maneras diferentes y en cada caso una segunda acción se puede hacer de n₂ maneras diferentes, entonces hay n₁ ·n₂ maneras de realizar ambas acciones conjuntamente. De manera general, si una vez realizada la segunda acción tenemos n₃ maneras de realizar una tercera acción y así sucesivamente, tendremos n₁ · n₂ · n₃ · · · n_k maneras de realizar k eventos de manera conjunta.

Ejemplo 2.1. Supongamos que tenemos 4 casas en una calle y queremos pintar cada una de ellas de un color entre azul, amarillo y verde.

Una primera manera sería pintarlas de azul, verde, amarillo y azul:

Fijando el color de las últimas tres casas, podríamos cambiar el color de la primera a verde o amarillo:

Es decir, tenemos tres opciones para la primera casa fijadas las otras tres. De manera análoga, tenemos tres opciones para la segunda casa una vez fijadas las restantes. Es decir tenemos 3 · 3 = 9 opciones diferentes de pintar las dos primeras casas una vez fijado el color de las últimas dos. En total tenemos 3 · 3 · 3 · 3 = 3⁴ = 81 maneras de pintar las cuatro casas con tres colores diferentes.

Principio de adicción: Este principio, también conocido como regla de la suma, nos dice que si tenemos dos sucesos mutuamente excluyentes (sólo uno de ellos puede ocurrir), y el primero se puede hacer de n₁ maneras diferentes, mientras que el segundo se puede hacer de n₂ maneras diferentes, entonces hay n₁ + n₂ maneras de realizar una de las dos acciones. De manera general, si tenemos k eventos mutuamente excluyentes, tendremos n₁ + n₂ + n₃ + · · · + n_k maneras de realizar uno de los k eventos.

Ejemplo 2.2. Supongamos que queremos realizar un viaje y tenemos que elegir entre metro, autobús o andando. Si hay 2 posibles rutas en metro, 4 en autobús y 3 andando habrá 2 + 4 + 3 = 9 posibles rutas.

A partir de estas reglas, y según las características de los grupos y naturaleza de los elementos que forman parte de éstos, distinguiremos entre tres grandes casos, los cuáles también se pueden combinar: permutaciones, variaciones y combinaciones. Un esquema puede encontrarse en la Figura 4.

Figura 4. Esquema combinatoria

2.2 Permutaciones

Supongamos que queremos ordenar n objetos en una fila, y nos preguntamos cuántas maneras diferentes tenemos de hacerlo. En este caso, en cada agrupación tomaremos todos los elementos del conjunto. Distinguiremos dos casos, si todos los elementos son diferentes o se repiten:

◾ Sin repetición: En general, n objetos distintos pueden ordenarse en fila de

n! = n · (n − 1) · (n − 2) · · · 2 · 1.

formas diferentes.

◾ Con repetición: En general, una colección de n objetos, clasificados en k grupos de objetos idénticos entre sí, el primero con n₁ objetos, el segundo con n₂ objetos, etc., puede ordenarse en fila de

$$\frac{n!}{n_1!n_2!\dots n_k!}$$

formas diferentes, siempre que no se consideren distintas las ordenaciones donde dos objetos iguales han permutado su posición.

Ejemplo 2.3. En un bar, cinco amigos han pedido 3 cafés y 2 cervezas. Contabilizar de cuántas maneras pueden repartir las cinco bebidas:

1. Supongamos que los cafés son diferentes (por ejemplo, sólo, cortado y con leche) y las cervezas también (con alcohol y sin alcohol). En este caso, hay n = 5 bebidas diferentes, por lo que habrá 5! = 120 maneras de repartirlas.

2. Supongamos que las cervezas y los cafés son iguales entre sí, por lo que pueden ser permutados entre sí, sin que el resultado se vea afectado. Entonces tenemos n = 5 bebidas agrupadas en k = 2 grupos diferentes de tamaños n₁ = 3, n₂ = 2. Habrá entonces

$$\frac{5!}{2!·3!}=10$$

maneras diferentes de repartirlas entre los amigos.

2.3 Variaciones

En este caso, queremos calcular las posibles muestras ordenadas de r elementos que se pueden extraer de un conjunto de n elementos. De nuevo, distinguimos dos casos:

◾ Sin repetición: En general, las posibles muestras ordenadas de r elementos distintos que se pueden extraer de un conjunto de n elementos, siendo r ≤ n viene dada por:

$$\frac{n!}{(n-r)!}=n·(n-1)...(n-r+1).$$

◾ Con repetición: Las posibles muestras ordenadas de r elementos no necesariamente distintos que se pueden extraer de un conjunto de n elementos es igual a n^r.

A diferencia de las permutaciones, aquí no todos los elementos del conjunto entran en cada agrupación.

Ejemplo 2.4. En una carrera con n = 6 atletas, calculamos el número de maneras distintas de repartir las medallas de oro, plata y bronce (r = 3).

$$\frac{6!}{(6-3)!}=6·5·4=120.$$

Ejemplo 2.5. La cantidad de números distintos de r = 3 cifras que se escriben usando solamente las cifras 1, 2, 3 y 4 (n = 4) es 4³ = 64.

2.4 Combinaciones

De nuevo, no todos los elementos del conjunto entran en cada agrupación, pero, a diferencia de las variaciones, aquí no es importante el orden. Distinguimos de nuevo entre repetición o no:

◾ Sin repetición: El número de posibles muestras no ordenadas de r elementos distintos que se pueden extraer de un conjunto de n elementos, con r ≤ n viene dado por el número combinatorio de n sobre r:

$$\left(\begin{array}{l}n\\ r\end{array}\right)=\frac{n!}{r!(n-r)!}.$$

◾ Con repetición: El número de posibles muestras no ordenadas de r elementos no necesariamente distintos que se pueden extraer de un conjunto de n elementos es

$$\left(\begin{array}{c}n+r-1\\ r\end{array}\right).$$

Ejemplo 2.6. La Primitiva consiste en elegir 6 números diferentes entre 1 y 49, con el objetivo de acertar la combinación ganadora en el sorteo. ¿Cuántas combinaciones posibles existen? En este caso, no importa el orden y los números no pueden repetirse por lo que habrá un total de

$$\left(\begin{array}{c}49\\ 6\end{array}\right)=\frac{49!}{6!·43!}=\frac{49·48\dots 43!}{6!·43!}=13983816$$

(casi 14 millones) combinaciones posibles.

Ejemplo 2.7. Queremos calcular de cuántas formas podemos sacar r = 4 cartas de una baraja de n = 40 cartas, devolviendo cada vez la carta, sin importar el orden en el que las sacamos. En este caso

$$\left(\begin{array}{c}43\\ 4\end{array}\right)=\frac{43!}{39!·4!}=123410.$$

Ejercicio 2.1. Determinar cuántas soluciones tiene la ecuación x + y + z = 8 con x, y, z enteros mayores que cero. Generaliza el resultado para x₁ + x₂ + · · · + x_k = n.

Solución: 8 se podría expresar como una sucesión de ocho “unidades”: uuuuuuuu, por lo que el problema consistiría en “introducir” dos signos “+”. Por ejemplo:

uuu + uu + uuu ⇒ x = 3, y = 2, z = 3.

Al ser mayores estrictos de cero, tenemos 7 huecos, así que habrá

$$\left(\begin{array}{l}7\\ 2\end{array}\right)=21$$

soluciones diferentes. Generalizando a k variables y una suma de n tenemos:

$$\left(\begin{array}{l}n-1\\ k-1\end{array}\right)\text{.}$$

El lector interesado en ejercicios resueltos y muy aplicados puede consultar [4]. Si desea profundizar en contenidos más avanzados o teóricos, se sugiere la consulta de [5, 6], entre otros.

3. Ejercicios

1. Demostrar la identidad $2^n=\sum _{i=0}^n\left(\begin{array}{c}n\\ i\end{array}\right)$.

2. Determinar cuántos números de tres cifras pueden tenerse si se emplean sólo cifras impares.

3. ¿Cuántos subconjuntos hay de cinco elementos de {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} que contienen al menos un número impar?

4. Se tienen dos mesas con capacidad para 6 y 3 personas. Determinar de cuántas maneras se pueden repartir 9 invitados (sin importar el orden en cada mesa).

5. Se rellena un test de 12 preguntas, a cada una se puede responder “verdadero” o “falso”. Se decide contestar a 6 preguntas de manera aleatoria. Calcula de cuántas formas puede hacerse.

6. Tenemos 5 bombillas, de las cuáles tres no funcionan y dos puntos de luz en una habitación oscura. Calcula el número de maneras en las que la habitación puede ser iluminada (nos vale con que una bombilla funcione).

7. Determinar de cuantas formas pueden ordenarse las letras de la palabra “catarata”.

8. Encuentra el número de contraseñas de 10 caracteres bajo las siguientes restricciones (consideramos 27 letras en el alfabeto).

a) todos los caracteres deben ser letras minúsculas,

b) todos los caracteres deben ser letras minúsculas diferentes entre sí.

9. Un palíndromo es una palabra o expresión que es igual si se lee de izquierda a derecha que de derecha a izquierda. ¿Cuántos palíndromos de 9 letras (no necesariamente con significado) pueden formarse usando todas las letras del abecedario español?

Referencias

¹ N. L. Biggs, “The roots of combinatorics”, Historia Mathematica 6, 109–136 (1979).

² A. Edwards, Pascal’s Arithmetical Triangle: The Story of a Mathematical Idea (Dover, 2019).

³ L. Shapiro, R. Sprugnoli, G. Cheon, T. He, D. Merlini y W. Wang, The Riordan Group and Applications, 1.^a ed. (Ed. Springer, 2022).

⁴ N. Vilenkin, ¿De cuántas formas? Combinatoria, Tomo 1 (Ed. MIR Moscú, 1972).

⁵ L. Lovász, Combinatorial Problems and Exercises (Ed. Elsevier, North Holland, 1993).

⁶ J. Riordan, Introduction to Combinatorial Analysis (Ed. Dover, 2003).