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

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

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}.$