Stars and Bars

Stars and Bars este o metoda de rezolvare a unor probleme de combinatorica. Aceasta se rezuma la determinarea posibilitatilor de a grupa un numar de stele intr-un set de bare.
Mai pe intelesul tuturor, gruparea unui numar de bile (identice) intr-un numar de cutii.

Teorema si demonstratia exista deja pe pbinfo, asa ca nu o sa intru in partea teoretica foarte mult.

Mai intai ne trebuie cele 2 formule:
(1) \( C_{n+k-1}^{k-1} \) Numărul de a variante de a plasa n obiecte identice în k cutii;

(2) \( C_{n-1}^{k-1} \) Numărul de a variante de a plasa n obiecte identice în k cutii astfel încât fiecare cutie conține cel puțin un obiect.

Cele 2 formule sunt pe aceasi baza cu formula de la Combinari, asa ca voi face explicatia pe cazul general.

\( C_{n}^{k} \)

Pentru (1): n = n + k – 1, k = k – 1;
Pentru (2): n = n – 1, k = k – 1;

Daca n este mai mare de 20, n! trece tipul de date long long int, iar in problemele #3330 #3741 #3742 , n si k ajung pana la 500.
Atunci ne gandim la o rezolvare cu aritmetica numerelor mari, dar si aici intampinam un mare obstacol: impartirea a doua numere mari. In articolul cu aritmetica numerelor mari, impartirea se poate face doar cu un numar mare si cu un numar mic.

In acest moment intervine matematica.

Noi avem (la baza) o fractie. Oare nu am putea sa reducem fractia la o forma ireductibila?

$$ C_{n}^{k} = \frac{( n! )}{ k! * ( n – k )! } = \frac{ ( 1 * 2 * 3 * … * k ) * ( ( k + 1 ) * ( k + 2 ) * ( k + 3 )… * (n – k) ) * (( n – k + 1 ) * ( n – k + 2 ) * ( n – k + 3 ) … * n )}{ ( 1 * 2 * 3* … * k ) * 1 * 2 * 3* … * k * ( ( k + 1 ) * ( k + 2 ) * ( k + 3 ) … * ( n – k ) ) } $$

Dupa simplificari, ecuatia devine: $$ C_{n}^{k} = \frac{(n-k+1) * (n-k+2) * … * (n-k+k)}{ 1 * 2 * … * k} = \prod_{i=1}^{k} \frac{n-(i-1)}{i} $$

In acest moment, impartitorul poate sa fie maxim 500, deci putem aplica impartirea unui numar mare la un numar mic.

Implementarea se afla in atasament.