Kombinacioni

Nga Wikipedia, enciklopedia e lirë
Shko te: navigacion, kërko

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 kombinimet 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 {n\choose k}

Ky numër mund të njehsohet sipas formulës së mëposhtme: {n\choose k}=\frac{n!}{k!(n-k)!}=\frac{n(n-1)(n-2) \cdots(n-k+1)}{k(k-1)(k-2) \cdots1}

p.sh.: {5\choose 2}=\frac{5 \cdot4}{2 \cdot1}=\frac{20}{2}=10 {6\choose 2}={15}

Trekëndëshi i Pascalit[redakto | redakto tekstin burimor]

Pastedpic 01152009 232346.png

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 \binom{n}{k}. Duke u bazuar në formulën e tanishme

\binom{n}{k}=\binom{n-1}{k} + \binom{n-1}{k-1}\,

e cila tregon se ç'do element i tabelës i cili nuk i takon rreshtit të parë ose kolonës së parë është i barabartë me shumën e elementit mbi të dhe e fqiut të tij të majtë.

Numri i kombinacioneve me përsëritje[redakto | redakto tekstin burimor]

Ky numër mund të llogaritet si vijon :

{{(n + k - 1)!} \over {k!(n - 1)!}} = {{n + k - 1} \choose {k}} = {{n + k - 1} \choose {n - 1}}

p.sh nëse kemi 10 objekteve zgjedhim 3 atëherë (10 + 3 − 1)!/(3!(10 − 1)! = 220 mënyra zgjedhjeje<end>.

Kjo mund të spjegohet kështu. Supozojmë se kemi n + k kuti të njëjta të renditura në vijë. Prej këtyre kutive(përveç të parës), rastësisht zgjedhim k prej tyre dhe kutinë e zgjedhur e kuptojmë si të zbrazët. Kutitë e mbetura mund të plotësohen me n elemente nga bashkësia S. Për ç'do kuti jo të zbrazët e cila pasohet nga M kuti të zbrazëta, ne zgjedhim elementin përkatës nga kutia jo e zbrazët M herë. Si përfundim, ç'do renditje apo zgjedhje e kutisë së zbrazët i përket një zgjedhje e k elementeve prej n elementeve prej të cilave disa ose të gjitha mund të përsëriten. Pra numri i kombinacioneve me përsëritje është:

 {n+k-1 \choose k}.