Kombinacioni

parapamje|Nënbashkësitë me 3 elemente nga një bashkësi me 5 elemente
**Kombinacioni** në matematikë, *me n

 elemente, i klasës p(p

 ≤ n)

,* është çdo nënbashkësi me  p

 elemente, të marrë nga bashkësia me n

 elemente pa përsëritje*.* Dy kombinacione të klasës p

 janë të ndryshme në qoftë se njëri përmban së paku një element që nuk e përmban tjetri, (pa e shikuar radhën). P.sh.: kombinacione të klasës së tretë të bashkësisë M=\{1, 2, 3, 4, 5\}, janë:

\{1, 2, 3\}, \{1, 2, 4\}, \{1, 2, 5\}, \{1, 3, 4\}, \{1, 3, 5\}, \{1, 4, 5\}, \{2, 3, 4\}, \{2, 3, 5\}, \{2, 4, 5\}, \{3, 4, 5\},

 ose shkurt:

123, 124, 125, 134, 135, 145, 234, 235, 245, 345.

Problemi kryesor në lidhje me kombinacionet është gjetja e numrit të tyre. Numrin e kombinacioneve të klasës k prej n elementesh e shënohen 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 Paskalit 
djathtas|500x500px
Trekëndëshi i Paskalit i jep vlerat e numrit të kombinacioneve, i cili në të shumtën e rasteve jepet në trajtën e një trekëndëshi barabrinjës. Këtu jepet 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 vendoset numri \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 janë 10 objekte zgjidhen 3 atëherë (10&nbsp;+&nbsp;3&nbsp;−&nbsp;1)!/(3!(10&nbsp;−&nbsp;1)!&nbsp;=&nbsp;220 mënyra zgjedhjeje.

Kjo mund të shpjegohet kështu: Supozohet se janë *n*&nbsp;+&nbsp;*k* kuti të njëjta të renditura në vijë. Prej këtyre kutive (përveç të parës), rastësisht zgjidhen *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, zgjidhet elementi 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ë zgjedhjeje 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}. 

## Parimi i Diriblesë 
Dirible (Filozof francez). Parimi mbi katrorët e pëllumbave.

k - katrorë 

k+1 - pëllumba

\Box_1 \Box_2...\Box_k

P.sh.: Për të siguruar që në një klasë dy prej tyre e kanë ditëlindjen në të njëjtën ditë do të n`a nevojiteshim 367 individë.

## Parimi i përgjithësuar i Diriblesë 
Nëse N objekte vendosen në k kuti atëherë ekziston të paktën një kuti me \left \lceil \frac{N}{k} \right \rceil(pjesa e plotë e sipërme) objekte.

## Vërtetim i parimit 
Përndryshe çdo kuti do të kishte jo më shumë se \left \lceil \frac{N}{k} \right \rceil-1 objekte. Atëherë numri i përgjithshëm i objekteve është:

k\cdot\Bigl(\left \lceil \frac{N}{k} \right \rceil-1\Bigr) - Kontradiksion.

## Kombinacionet pa përsëritje, renditja nuk ka rëndësi 
C_p^n=\binom{n}{p}= \frac{n!}{p!(n-p)!}

Në sa mënyra mund t`i zgjedhim dy shkronja nga 4 shkronja a, b, c, d?

{ ab\ , ac\ , ad , bc\ , bd, cd}

Pra, C^2_4  kështu në 6 mënyra.

## Vetitë e kombinacioneve 
1. \binom{n}{r} = \binom{n}{n-r}, r\leq n\ r,n \gtrless \geq 0

2. Trekëndëshi i Paskalit

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

3.  \sum_{k=0}^n\binom{n}{k}=2^n

4. Identiteti i Vandermondit

\binom{m+n}{r}= \sum_{k=0}^r\binom{m}{r-k}\binom{n}{k}

5.
 Teorema e binomit

x, y  variabla, n\in N

(x+y)^n = \sum_{j=0}\binom{n}{j}x^{n-j}y^j

(x+y)(x+y)...(x+y)

6.
 n\in N

\sum_{k=0}(-1)^k\binom{n}{k}=0

7.  \binom{n}{k}= \sum_{i=k}^n\binom{i-1}{k-1}

Për k numra =\binom{k-1}{k-1}+\binom{k}{k-1}\binom{k-1}{k-1}+...+\binom{n-1}{k-1}.

## Referime