PERMUTACIONET

PERMUTACIONET

Permutacion i një bashkësie të fundme quhet ç'do renditje e të gjitha elementeve të saj në varg. Për shembull të gjitha permutacionet e bashkësisë A={1,2,3} janë:

123,132,213,231,312,321

Shohim se kjo bashkësi ka gjithsejt 6 permutacione. ngjajshëm vërejmëë se bashkësia me 4 elemente B={1,2,3,4} ka 4 herë më shumë permutacione se bashkësia B sepse lehtë vërejmë se ç'do permutacion i A gjeneron 4 permutacione të B ashtuqë elementin 4 e vendosim në fillim, në mes dy elementeve të para, në mes elementit të dytë dhe elementit të tretë ose në fund të vargut gjegjësisht permutacionit të baashkësisë A. Në këtë mënyrë permutacioni 123 i A gjeneron këto 4 permutacione të B

4123,1423,1243,1234

permutacioni 132 i A gjeneron këto 4 permutacione të B

4132,1432,1342,1324

permutacioni 213 i A gjeneron këto 4 permutacione të B

4213,2413,2143,2134

permutacioni 231 i A gjeneron këto 4 permutacione të B

4231,2431,2341,2314

permutacioni 312 i A gjeneron këto 4 permutacione të B

4312,3412,3142,3124

dhe në fund permutacioni 321 i A gjeneron këto 4 permutacione të B

4321,3421,3241,3214

Numri i permutacioneve
Le të jetë n numri i elementeve të bashkësisë prmutacionet e të cilës duam ti gjejmë do të tregojmë se numri i permutacioneve të saj është i barabartë me n!, ku "!" është operatori faktoriel. Për të konstruktuar një permutacion ka n mënyra të ndryshme për të zgjedhur elementin e parë. Pas zgjedhjes së tij mbeten, n ? 1 elemente prej të cilave zgjedhim një dhe e vendosim në vendin e dytë në n ? 1 mënyra. Kështu për vendosjen e dy elementeve të para ekzistojnë gjithsejt :n × (n ? 1) mënyra. Për zgjedhjen e elementit të tretë mbesin n ? 2 elemente, prandaj me plotësimin e tre vendeve të para fitohen,

n × (n ? 1) × (n ? 2) permutacione.
Duke vazhduar në këtë mënyrë derisa të mbeten dy elemente të pazgjedhur për të cilat mbeten 2 mundësi, në fund mbetet një element praandaj për numrin e të gjitha permutacioneve prej n elementesh e fitojmë formulën gjegjësisht numrin

n × (n ? 1) × (n ? 2) × ... × 2 × 1
i cili shkurtimisht shënohet me n!.