html
El coeficient binomial o nombre combinatori (
)
és el nombre de maneres de triar k objectes d’un total de n.
La seva fórmula és ben coneguda:
on n!=n· (n−1)⋯ 2· 1.
Aquesta fórmula no és massa pràctica des d’un punt de vista computacional,
perquè s’ha de treballar amb nombres molt grossos (els factorials) per
acabar obtenint un resultat molt més petit. Per exemple,
| = | | = | | 2432902008176640000 |
|
| 1316819440000 |
| = 184756 ,
|
on es pot veure que, tot i que el nombre final només té 6 xifres, ens
ha fet falta calcular 20!, que en té 19. Això pot ser un problema, ja que
el tipus int de 32 bits no pot emmagatzemar
nombres amb més de 10 xifres.
Aquesta, però, no és l’única manera de calcular (
).
Per exemple, els nombres combinatoris satisfan la
propietat següent:
| = | ⎧
⎪
⎨
⎪
⎩ | | 1 | si k = 0 o k = n |
| si 0<k<n |
|
|
Aquesta fórmula recursiva permet calcular els nombres combinatoris
sense multiplicacions ni divisions, mitjançant un procediment
conegut avui en dia com a “Triangle de Pascal” o “Triangle
de Tartaglia”, encara que tingui referències històriques amb més de
1000 anys d’antiguitat:
||
| | | | | 1 | | | | |
| | | | 1 | | 1 | | | |
| | | 1 | | 2 | | 1 | | |
| | 1 | | 3 | | 3 | | 1 | |
| 1 | | 4 | | 6 | | 1 | | 1 |
| | | | | … | | | | |
||
||
| | | | | () | | | | |
| | | | () | | () | | | |
| | | () | | () | | () | | |
| | () | | () | | () | | () | |
| () | | () | | () | | () | | () |
| | | | | … | | | | |
||
Per calcular més nombres combinatoris només cal
omplir més files del triangle.
Feu servir aquesta idea per calcular diversos nombres combinatoris.
Entrada
La entrada consisteix en diversos casos,
cadascun amb dos naturals n i k,
on 0≤ n≤ 30 i 0≤ k≤ n.
Sortida
Per a cada cas, cal escriure (
).