El coeficiente binómico \(\require{AMSmath}\)\(\binom{n}{r}\) puede definirse como el número de grupos o subconjuntos de \(r\) elementos tomados de un conjunto de \(n\) elementos. Su número puede calcularse a partir del número de secuencias de \(r\) elementos. Las secuencias se caracterizan por estar ordenadas mientras que los grupos o subconjuntos no lo están.
Para formar una secuencia de tamaño \(r\) elegimos el primer elemento de \(n\) formas posibles. El segundo elemento puede elegirse de \(n -1\) formas posibles, para el tercero tenemos \(n -2\) opciones, así hasta el que estará en último lugar para el que habrá \(n -(r -1)\) opciones. El principio del producto nos dice que habrá $$n (n -1) (n -2) \dots (n -r + 1)$$ secuencias de longitud \(r.\) Si nos interesa solo los elementos que aparecen en una secuencia y no su orden, ¿qué otras secuencias tienen los mismos elementos? Por cada secuencia de \(r\) elementos tendremos \(r!\) secuencias con los mismos elementos, por tanto, grupos o subconjuntos de \(r\) elementos tendremos $$\frac{n (n -1) (n -2) \dots (n -r + 1)}{r!} \tag{1}\label{eq1}$$ Estos grupos se denominan combinaciones y su número se denota por cualquiera de los símbolos $$_nC_r \;, \quad C_{n,r} \;, \quad C_n^{\,r}\;, \quad \binom{n}{r}$$ Completando el numerador de \(\eqref{eq1}\) los factores que faltan hasta obtener \(n!\) $$\binom{n}{r} = \frac{n (n-1) (n-2) \dots (n-r + 1) \cdot (n -r)!}{r! \, (n-r)!} = \frac{n!}{r! \, (n-r)! }.\tag{2}\label{eq2}$$ Esta expresión con factoriales nos ayudará a encontrar las fórmulas recursivas que buscamos.
Coeficientes recursivos
Cualquier coeficiente binómico se encuentra en una línea horizontal, en una línea diagonal izquierda y en una línea diagonal derecha del triángulo de Pascal.[1]
En la línea considerada, un coeficiente se puede expresar en términos del coeficiente que le precede. $$\eqalign { &\color {darkorange} {\small \text{ Situado en una línea horizontal}} \\ \binom{n}{r} &= \frac{n!}{r! \, (n-r)!} = \frac{n!}{(r-1)! \, (n-r + 1)!} \cdot \frac{n-r + 1}{r} \\ &= \binom{n}{r-1} \frac{n-r + 1}{r} \\ &\color {mediumvioletred} {\small \text{ Situado en una línea diagonal izquierda}} \\ \binom{n}{r} &= \frac{n!}{r! \, (n-r)!} = \frac{(n-1)!}{(r-1)! \; (n-r)!} \cdot \frac{n}{r} \\ &= \binom{n-1}{r-1} \; \frac{n}{r} \\ &\color {darkblue} {\small \text{ Situado en una línea diagonal derecha}} \\ \binom{n}{r} &= \frac{n!}{r! \, (n-r)!} = \frac{(n-1)!}{r! \, (n-r-1)!} \cdot \frac{n}{n-r} \\ &= \binom{n-1}{r} \; \frac{n}{n-r} }$$
"""
Números combinatorios recursivos
www.elcartapacio.es
"""
import math
def binom_h(n, r):
"""Calcula un coeficiente recurriendo a los que
le preceden en la misma línea horizontal.
"""
# aplicar reducción por simetría
if r > math.floor(n / 2): r = n - r
if r == 0 : return 1
return binom_h(n, r - 1) * (n - r + 1) / r
def binom_di(n, r):
"""Calcula un coeficiente recurriendo a los que
le preceden en la misma diagonal izquierda.
"""
if r == 0 : return 1
return binom_di(n - 1, r - 1) * n / r
def binom_dd(n, r):
"""Calcula un coeficiente recurriendo a los que
le preceden en la misma diagonal derecha.
"""
if n == r : return 1
return binom_dd(n - 1, r) * n / (n - r)
# Las tres funciones dan los mismos resultados,
# solo difieren en la fórmula recursiva.
# Prueba de la función binom_di()
def diagonal_i(nivel, longitud):
"""Construye elementos de la diagonal izquierda."""
return [int(binom_di(nivel + r, r)) for r in range(longitud)]
print("Diagonal", 3, diagonal_i(3, 10))
# Diagonal 3 [1, 4, 10, 20, 35, 56, 84, 120, 165, 220]
def pascal(altura):
"""Presenta el triángulo aritmético.
Construye los elementos de cada fila mediante la recurrencia
binom_di(n, r) = binom_di(n - 1, r - 1) * n / r
y los presenta en columnas de ancho fijo.
"""
sep = " "
ancho = 3
for num_fila in range(altura + 1):
fila_actual = [1]
print(fila_actual[-1], end = sep)
for col in range(num_fila + 1, altura + 1):
fila_actual.append(int(fila_actual[-1] * col / (col - num_fila)))
print(str(fila_actual[-1]).rjust(ancho), end = sep)
# fila_actual contiene los elementos de la fila actual
print()
pascal(9)
# Resultado para 10 filas
# 1 1 1 1 1 1 1 1 1 1
# 1 2 3 4 5 6 7 8 9
# 1 3 6 10 15 21 28 36
# 1 4 10 20 35 56 84
# 1 5 15 35 70 126
# 1 6 21 56 126
# 1 7 28 84
# 1 8 36
# 1 9
# 1
def pascal_bin(altura)
"""Presenta el triángulo del tamaño deseado."""
for num_fila in range(altura + 1):
fila_actual = [int(binom_h(num_fila, r)) for r in range(num_fila + 1)]
print(fila_actual, "-", sum(fila_actual))
print()
pascal_bin(9)
# Resultado para 10 filas
# [1] - 1
# [1, 1] - 2
# [1, 2, 1] - 4
# [1, 3, 3, 1] - 8
# [1, 4, 6, 4, 1] - 16
# [1, 5, 10, 10, 5, 1] - 32
# [1, 6, 15, 20, 15, 6, 1] - 64
# [1, 7, 21, 35, 35, 21, 7, 1] - 128
# [1, 8, 28, 56, 70, 56, 28, 8, 1] - 256
# [1, 9, 36, 84, 126, 126, 84, 36, 9, 1] - 512
[1]↑ Para conocer más propiedades del triángulo de Pascal consulte El triángulo de Pascal.