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)\cdots 1}}$

p.sh.: ${5 \choose 2}={\frac {5\cdot 4}{2\cdot 1}}={\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.

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