Coeficients binomials P93625

El coeficient binomial o nombre combinatori $\binom{n}{k}$ és el nombre de maneres de triar $k$ objectes d’un total de $n$. La seva fórmula és ben coneguda: $$\binom{n}{k} = \frac{ n! }{ k! (n-k)! } \enspace ,$$ on $n!=n\cdot (n-1)\cdots 2\cdot 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, $$\binom{20}{10} = \frac{ 20! }{10! 10!} = \frac{2432902008176640000}{1316819440000} = 184756 \enspace ,$$ 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 $\binom{n}{k}$. Per exemple, els nombres combinatoris satisfan la propietat següent: $$\binom{n}{k} = \left\{ \begin{array}{ll} 1 & \mbox{si $k = 0$ o $k = n$} \\ \binom{n-1}{k-1} + \binom{n-1}{k} & \mbox{si $0<k<n$} \end{array} \right.$$ 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:

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\le n\le 30$ i $0\le k\le n$.

Sortida

Per a cada cas, cal escriure $\binom{n}{k}$.