Kombinacioni

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)\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 Paskalit

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 + 3 − 1)!/(3!(10 − 1)! = 220 mënyra zgjedhjeje.

Kjo mund të shpjegohet kështu: Supozohet se janë n + 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 )}<k\cdot {\Bigl (}{\frac {N}{k}}+1-1{\Bigr )}=N$ - 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_{4}^{2}$ 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}}$.