Probleme Cu Aranjamente Si Combinari
Niklas Terki
Cu alte cuvinte, produsul cartezian al doua multimi ( A A A si B B B) este multimea de perechi construite punand elemente din A A A pe prima pozitie si elemente din B B B pe a doua pozitie. Astfel imperechem fiecare element din A A A cu fiecare element din B B B.
Observam astfel ca o submultime nu este altceva decat o functie care atribuie fiecarui element din A A A o valoare din multime 0 , 1 \0, 1\ 0,1. Cum numarul acestor functii este 2 n 2^n 2n, acesta este si numarul de submultimi.
Intrebare: Pentru n n n si m m m date, cate astfel de aranjamente exista?
Pentru a gasi numarul de aranjamente vom parcurge aceeasi pasi ca la numarul de permutari, oprindu-ne insa la cea de m m m-a intrebare:
Intrebare: Pentru n n n si m m m date, cate astfel de combinari exista?
Pentru a rezolva aceasta problema, trebuie sa vedem care este legatura dintre combinari si aranjamente. La aranjamente ordinea elementelor alese conteaza, pe cand la combinari, nu.
Fiecarei combinari ii putem asocia in mod unic un numar fix de aranjamente, pe care le putem genera permutand in toate modurile posibile elementele combinarii. Avem astfel ca pentru o combinare putem genera m ! m! m! aranjamente. Cum un aranjament poate fi generat de o singura combinare, avem ca numarul de aranjamente este de m ! m! m! de ori mai mare decat numarul de combinari.
Exista tehnici pentru a calcula restul impartirii pentru fractii unde cunoastem doar resturile numaratorului si numitorului. Acestea insa depasesc pentru moment scopul acestei prezentari, dar daca doriti sa investigati mai departe, un punct bun de plecare este problema Invers modular de pe infoarena si indicatiile de rezolvare de aici.
ATENTIE!! Aveti girja la calculele care pot duce la overflow. Atunci cand calculati (a*b)%MOD, chiar daca a, b si MOD sunt de tip int, inmultirea din paranteza poate depasi limita de 2 31 2^31 231. Un truc comun este de a forta calculul din paranteza sa fie facut pe tipul de date long long inmultind la inceput cu literalul 1LL (numarul 1 1 1 dar pe tipul long long): (1LL * a * b) % MOD.
Pentru valorile care apar de doua ori nu avem ce decizie sa luam, am vazut mai devreme ca una dintre ele ajunge in partea stanga, iar cealalta in partea dreapta. Notam cu unic numarul de valori care apar o singura data in sirul dat la input (cu exceptia valorii maxime!). Putem alege acum orice submultime a acestora sa fie pusa in stanga maximului, iar complementara ei sa fie pusa in dreapta. Numarul de moduri de a face acest lucru este chiar numarul de submultimi ( 2 u n i c 2^unic 2unic).
Atentie la cazul in care toate valorile din sirul de la input apar o singura data. Formula de mai sus va numara si cazul in care maximul este primul element al muntelui (submultimea aleasa pentru partea stanga este submultimea vida), sau ultimul (submultimea aleasa pentru partea stanga este multimea tuturor valorilor), aceste doua cazuri trebuie scazute de la rezultat. Daca avem cel putin o valoare cu doua aparitii, acest caz particular nu mai apare, deoarece avem garantat ca de-a stanga si de-a dreapta maximului avem cel putin o valoare.
Folosim urmatoarele notatii:
n r l i t nrlit nrlit: numarul de litere distincte din sirul de la intrare
u n i c unic unic: numarul de litere distincte care apar o singura data in sirul de intrare
p o l i poli poli: numarul de litere distincte care apar de cel putin doua ori in sirul de intrare
Evident n r l i t = u n i c + p o l i nrlit = unic + poli nrlit=unic+poli
Cu alte cuvinte, divizorul nu are voie sa contina in descompunerea sa alti factori primi decat n n n, iar exponentul acestora trebuie sa fie mai mic sau egal cu cel din decompunerea lui n n n (posibil si 0 0 0, intrucat divizorul poate sa nu contina anumiti factori primi din descompunerea lui n n n).
Demonstratia este faptul ca daca am desface parantezele fiecare termen al sumei finale ar fi un produs intre cate un element din fiecare paranteza. Cum in fiecare paranteza avem factori primi la puteri mai mici sau egale decat cea cu care apar in descompunerea lui n n n, toti termenii pe care ii obtinem reprezinta divizorii lui n n n.
Observam usor ca un K K K-sir trebuie sa contina doar divizori ai lui N N N, altfel cmmmc-ul acestora nu va fi N N N. Insa aceasta conditie nu este si suficienta, ci ne garanteaza doar ca cmmmc-ul K K K-sirului il divide pe N N N.
In cate moduri putem fixa exponentul lui p p p in descompunerea celor K K K numere din sir? Intrucat fiecare numar din sir il divide pe N N N, putem sa ii fixam exponentul lui p p p orice valoare intreaga din intervalul [ 0 , t ] [0,t] [0,t] (in total t + 1 t+1 t+1 variante). Avem t + 1 t+1 t+1 variante pentru primul numar, t + 1 t+1 t+1 variante pentru cel de-al doilea s.a.m.d., deci in total avem ( t + 1 ) K (t+1)^K (t+1)K variante de a distribui exponentii lui p p p printre numerele din K K K-sir.
Problema este ca in aceasta formula numaram si cazurile in care toate cele K K K numere primesc exponenti strict mai mici decat t t t, iar daca pentru un astfel de K K K-sir calculam cmmmc-ul, acesta va avea in descompunere p p p la o putere mai mica decat t t t, deci nu poate fi egal cu N N N.
Numararile pe care le facem pentru un factor prim p p p si pentru un factor prim q q q sunt independente (ce exponenti setam pentru p p p numerelor din K K K-sir nu influenteaza ce exponenti setam pentru q q q). Astfel la numarul total de posibilitati aceste cazuri se vor inmulti.
Dificultatea problemei sta in faptul ca nu se mai cere rezultatul ca rest la impartirea cu un numar, ci se doreste valoarea exacta. Pentru aceasta, factorialul trebuie calculat folosind o reprezentare a numerelor cu oricat de multe cifre.
Obtinem ca rezultatul inmultirii este numarul 162864 162864 162864. Nu am facut altceva decat sa simulam pe acest vector inmultirea de mana. Aceasta ar fi o sugestie de implementare a unei functii care inmulteste un numar mare cu un numar mic:
Problema ne cere sa numaram in cate moduri putem sa organizam orasele ca o multime de cicluri. Prin ciclu intelgem un mod de a uni o submultime de orase, astfel incat fiecare oras este unit cu alte doua si putem ajunge de la orice oras la orice alt oras din ciclu (imaginati-va ca orasele dintr-un ciclu sunt puse intr-un cerc, iar fiecare oras este unit cu vecinul din stanga si cu vecinul din dreapta sa).
Definitie factorial. Definitie aranjamente. Definitie combinari. Formula combinarilor complementare. Formula de recurenta pentru combinari. Suma sub-multimilor de combinari ale unei multimi. Numarul functiilor injective / bijective / strict crescatoare / strict descrescatoare. Binomul lui Newton. Formula termenului general. Exercitiu - ecuatie raport factoriali.
1-Aranjamente ; 2-Combinari ; 3-Binomul lui Newton ; 4-Exercitiul 1