Kombinatorika

Titulli: Kombinatorika Sun Feb 14, 2010 4:02 am

Kombinatorika merret me studimin e bashkësive të fundme, me grupimin e elementeve të tyre sipas ndonjë kriteri të caktuar, me renditjen e elementeve etj. Kuptimet themelore të kombinatorikës janë permutacioni, kombinacioni, variacioni, multibashkësia etj. . Ajo është e lidhur ngushtë me degë tjera rë matematikës si Algjebra, Teoria e gjasës, dhe Gjeometria, dhe ka zbatime të shumta në Shkencat kompujterike në Statistikë etj. Aspekte të kombinatorikës konsistojnë në llogaritjen e numrit të objekteve të cilat plotësojnë ndonjë kriter të caktuar që përbën objektin e studimit të Kombinatorikës numerike, Gjetjen e elementit ose objektit më të madh ose më të vogël ose zgjedhjen optimal që probleme këto që i studjon Kombinatorika ekstrmale, poashtu zhvillimi dhe gjetja e strukturave të cilat i plotësojnë objektet kombinatorike, i studjon Kombinatorika algjebrike.

Kombinatorika më shumë merret me zgjidhjen e problemeve se me ndërtimin e një teorie, por kjo nuk do të thotë se gjatë kësaj nuk është ndërtuar një teori e fuqishme e kombinatorikës sidomos në fund të shekullit XX . Njëra nga pjesët e kombinatorikës është edhe Teoria e grafeve.

Matematikani i cili është i specializuar në kombinatorikë quhet kombinatorist.

Titulli: Re: Kombinatorika Sun Feb 14, 2010 4:02 am

Historia e kombinatorikës
Gjurmë të kombinatorikës gjejmë te Xhainistët në Indi matematikani Pingala e zbuloi methodën e përcaktimit të numrit të kombinacioneve të një numri të dhënë shkronjash, prej të cilave zgjedhim 1, 2, etj. Mahavira rreth vitit 850 i dha formulat e përgjithshme për gjetjen e numrit të permutacioneve dhe kombinacioneve të një bashkësie të fundme. Bhaskaracharya për kombinatorikën përdorte emërtimin Anka Pasha në Lilavati. Ai dha disa formula të reja në kombinatorikë. [1] Disa arritje të rëndësishme janë dhënë nga grekët e vjetër dhe kinezët. Disa matematikan arab dhe çifut kanë përdorur konceptet e permutacionit dhe kombinacionit gjatë vështrimeve astronomike p.sh. Rabbi ben Ezra rreth vitit 1140). Libri i parë modern i shkruajtur me subjekt kombinatorikën është Ars Conjectandi i shkruajtur nga matematikani i shquar Jacob Bernoulli i cili u botua në vitin 1713.

Kombinatorika numerike
Kombinatorika numerike është fusha më klasike e kombinatorikës, ajo merret me llogaritjen e numrit të konfiguracioneve të cilat përkufizohen nga elementet e një bashkësie të caktuar objektesh. Shumica e problemeve të cilat hasen në kombinatorikën numerike kanë formulim të thjeshtë kombinatorik p.sh disa prej tyre janë Numrat e Fibonaccit, Numrat e Catalanit, Numri i permutacioneve, kombinacioneve, Particioni i numrit natyral Particioni i bashkësisë, Kompozicioni i numrit natyral etj.

Kombinatorika analitike
Kombinatorika analitike merret me studdimin e strukturave kombinatorike duke shfrytëzuar konceptet nga Analiza komplekse dhe nga Teoria e gjasës. Përderisa kombinatorika numerike nxjer formula eksplicite duke i shfrytëzuar p.sh funksionet gjeneratrisa kombinatorika analitike përfundimet i jep me formula asimptotike.

Titulli: Re: Kombinatorika Sun Feb 14, 2010 4:03 am

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!.

Titulli: Re: Kombinatorika Sun Feb 14, 2010 4:07 am

Kombinacioni

Kombinacioni është njëri prej kuptimeve themelore të kombinatorikës.

Përkufizim: Ç'do nënbashkësi me k elemente e zgjedhur nga një bashkësi me n elemente quhet kombinacion pa përsëritje i klasës “k” prej “n” elementesh. P.sh të gjitha kombinacionet e klasës së tretë të bashkësisë A={a,b,c,d} janë: (a,b,c), {a,b,d}, (a,c,d), (b,c,d} Problem kryesor në lidhje me kombinacionet është gjetja e numrit të tyre. Numrin e kombinacioneve të klasës k prej n elementesh e shënojmë me $Kombinatorika 3f5c2191d5128f36ec6b726c77df3b06$
Ky numër mund të njehsohet sipas formulës së mëposhtme
$Kombinatorika 5d81ca2da5ff8aab062c87693747d726$
psh: $Kombinatorika 29b79cf34b5ae830f6bbe7585bac7d07$
Numeri i kombinacioneve me perseritje:
$Kombinatorika 6feefb21b8972dc73c059c0f3d03801e$
rekëndëshi i Pascalit

Trekëndëshi i Pascalit i jep vlerat e numrit të kombinacioneve, ky trekëndësh në të shumtën e rasteve jepet në trajtën e një trekëndëshi barabrinjës. Ne këtu e kemi dhënë në trajtën e një trekëndëshi kënddrejt numrash sipas rrjeshtave n dhe sipas kolonave k. Në prerjen e rrjeshtit n me kolonën k e vendosim numrin $Kombinatorika 3f5c2191d5128f36ec6b726c77df3b06$
Duke u bazuar në formulën rekurrente $Kombinatorika 3f5c2191d5128f36ec6b726c77df3b06$ = $Kombinatorika 09430f293c53fa1d2b50300a4c97c432$ + $Kombinatorika D68ebedaaa6482da9ca89d15521603cd$
cila tregon se ç'do element i tabelës i cili nuk i takon rrjeshtit të parë ose kolonës së parë është i barabartë me shumën e elementit mbi të dhe e fqiut të tij të majtë

Titulli: Re: Kombinatorika Sat Mar 27, 2010 6:48 am

N`kuader t'kombinatorikes jon edhe variacionet !