Preg tirea lotului na ional de informatic Alba Iulia 2004

Permut ri1. No iuni introductiveSe nume te permutare o func ie bijectiv p:AA.

Prof. Nistor Mo

De obicei se consider A={1,2,,n} i permutarea se scrie sub forma 1 2 3 ... n dar toate rezultatele r mn valabile dac se p (1) p (2) p (3) ... p (n) nlocuie te mul imea {1,2,n} cu orice mul ime cu n elemente (evident, n programare nu se lucreaz cu mul imi infinite). De asemenea ordinea numerelor din primul rnd este neesen ial , de exemplu 1 2 3 4 2 3 1 4 permutarea poate fi scris i , n ambele cazuri p(1)=2, 2 4 1 3 4 1 2 3 p(2)=4, etc. Vom nota mul imea permut rilor lui {1,2,,n} cu Sn . Se nume te permutarea identic ( i se noteaz de obicei cu e) func ia identic a mul imii A (1A) adic permutarea p n care p(1)=1, p(2)=2,,p(n)=n. Se nume te punct fix al unei permut ri pSn un num r x{1,2,,n} pentru care avem p(x)=x. Evident permutarea identic are n puncte fixe Se nume te transpozi ie o permutare pSn cu n2 puncte fixe. Dac p(i)=j i p(j)=i, restul valorilor fiind puncte fixe, transpozi ia se mai noteaz i (i j). Opera ia de baz n mul imea Sn este compunerea permut rilor, o vom nota cu o permut rile fiind func ii este vorba despre compunerea func iilor. Se cunosc propriet ile : compunerea este asociativ adic (poq)or=po(qor) compunerea nu este comutativ - adic n general poq qop permutarea identic este element neutru adic poe=p i eop=p fiecare permutare are o permutare invers astfel nct compunnd cele dou permut ri ob inem permutarea identic - pop1 = e i p1op = e. Inversa unei permut ri se poate ob ine inversnd cele dou rnduri, apoi eventual reordonnd tabloul n ordinea cresc toare a numerelor de pe primul rnd. Pentru exemplul de mai sus 1 2 3 4 inversa este 3 1 4 2 O transpozi ie compus cu ea ns i d permutarea identic , deci este propria ei invers . Problema 1. Calcula i cte cifre are num rul de permut ri pentru n1000000000.

Preg tirea lotului na ional de informatic Alba Iulia 2004

Rezolvarea se poate face folosind propriet ile logaritmilor : lg n! = lg 1 + lg 2 + + lg n, partea ntreag a logaritmului zecimal +1 ne va da num rul de cifre. Dar un for mergnd de la 1 la 1000000000 dep e te timpul normal pentru execu ia unui program (dac calculatorul adun 10.000.000 logaritmi pe secund vor fi necesare 100 secunde !). Exist o formul celebr (formula lui Stirling) ce aproximeaz foarte bine (pentru numere mari) pe n!, pentru n>100 num rul de cifre va fi dat f r eroare de aceast formul , chiar i primele cifre sunt date corect. Formula este :

n 2n (n formul apar dou numere ira ionale e2,71 i 3,14) e Cu aceast formul logaritmul lui n! se calculeaz imediat n(lg nlg e)+(lg n+lg 2)/2. n!= Se nume te inversiune a unei permut ri pSn o pereche (i,j) cu 1ip(j). Num rul inversiunilor unei permut ri joac un rol important n multe aplica ii ale permut rilor.Problema 2. (din lista lui Frncu) Se dau doua numere naturale N si K, 1