PROBLEMA 7:             Permutari (part I)
DEADLINE:               Duminica, 24 ianuarie 1999
TIMP DE IMPLEMENTARE:   90 minute
DOMENIU:                Nascocire de formule

Se dau doua numere naturale N si K, 1<=N<=45, 0<=K<=N*(N-1)/2. Sa se
tipareasca numarul de permutari ale multimii {1, 2, ..., N} in care
exista K inversiuni.

INTRAREA: Fisierul PERM.IN contine o singura linie pe care se afla
valorile lui N si K, despartite printr-un spatiu.

IESIREA: Pe ecran se va afisa un singur numar (nimic altceva, svp),
respectiv numarul de permutari cu K inversiuni.

EXEMPLE:
PERM.IN                         Raspuns
3 0                             1

PERM.IN                         Raspuns
4 2                             5

COMPLEXITATE RECOMANDATA: O(N^2*C), unde C este numarul de cifre al
raspunsului.

TIMP DE EXECUTIE: O secunda pe un Cyrix/166/96 MB RAM/Windows '95

Bafta!
-------------


BREVIAR: PERMUTARI (pentru cei mici)

Permutarile unei multimi sunt toate ordinile posibile in care putem
aseza elementele acelei multimi. De exemplu, permutarile multii {1, 2,
3} sunt:

123, 132, 213, 231, 312, 321

Se poate arata ca numarul permutarilor unei multimi cu N elemente este
egal cu N!.

Dandu-se o permutare P, numarul de inversiuni al ei este numarul de
perechi (i,j) pentru care i<j si P[i]>P[j]. De exemplu, pentru
permutarea cu 5 elemente:

P=52314, perechile (i,j) in dezordine sunt:

(1,2):    1<2 dar 5>2
(1,3):    1<3 dar 5>3
(1,4):    1<4 dar 5>1
(1,5):    1<5 dar 5>4
(2,4):    2<4 dar 2>1
(3,4):    3<4 dar 3>1

Asadar permutarea in cauza are 6 inversiuni. Numarul minim de
inversiuni al unei permutari de N elemente este 0 (pentru permutarea
1 2 3 ... N-1 N), iar numarul maxim de inversiuni este N*(N-1)/2
(pentru permutarea N N-1 ... 3 2 1).

Cam atat ajunge, pentru inceput. Mai am in minte o problema cu
permutari.