html
El coeficiente binomial o número combinatorio (
)
es el número de maneras de escoger k objectos de un total de n.
Su fórmula es bien conocida:
donde n!=n· (n−1)⋯ 2· 1.
Esta fórmula no es demasiado práctica desde un punto de vista computacional,
porque se tiene que trabajar con números muy grandes (los factoriales)
para acabar obteniendo un resultado mucho más pequeño. Por ejemplo,
| = | | = | | 2432902008176640000 |
|
| 1316819440000 |
| = 184756 ,
|
donde se puede ver que, pese a que el número final sólo tiene 6 cifras,
nos ha hecho falta calcular 20!, que tiene 19. Esto puede ser un problema,
puesto que el tipo int de 32 bits
no puede almacenar números de más de 10 cifras.
Este, sin embargo, no es el único modo de calcular (
).
Por ejemplo, los números combinatorios satisfacen la
propiedad siguiente:
| = | ⎧
⎪
⎨
⎪
⎩ | | 1 | si k = 0 o k = n |
| si 0<k<n |
|
|
Esta fórmula recursiva permite calcular los números combinatorios sin multiplicaciones
ni divisiones, mediante un procedimiento conocido hoy en día como
“Triángulo de Pascal” o “Triángulo de Tartaglia”,
aunque tenga referencias históricas con más de 1000 años de antigüedad:
||
| | | | | 1 | | | | |
| | | | 1 | | 1 | | | |
| | | 1 | | 2 | | 1 | | |
| | 1 | | 3 | | 3 | | 1 | |
| 1 | | 4 | | 6 | | 1 | | 1 |
| | | | | … | | | | |
||
||
| | | | | () | | | | |
| | | | () | | () | | | |
| | | () | | () | | () | | |
| | () | | () | | () | | () | |
| () | | () | | () | | () | | () |
| | | | | … | | | | |
||
Para calcular más números combinatorios sólo hay que
llenar más filas del triángulo.
Usad esta idea para calcular diversos números combinatorios.
Entrada
La entrada consiste en diversos casos,
cada uno con dos naturales n y k,
donde 0≤ n≤ 30 y 0≤ k≤ n.
Salida
Para cada caso, escribid (
).