Binomski koeficient

Iz Wikipedije, proste enciklopedije

Binómski koeficiènt naravnega števila n in celoštevilčnega k je v matematiki določen kot naravno število

${n \choose k} = \frac{n!}{k!(n-k)!} , \quad ( n\geq k\geq 0) \qquad (1)$

${n \choose k} = 0 , \quad ( k<0 ) \mbox{ ali } ( k>n ).$

Tukaj je z m! označena fakulteta m. Binomski koeficient n in k zapišemo tudi kot C(n,k) ali kot _nC_k.

Na primer:

${7 \choose 3} = \frac{7\cdot 6 \cdot 5}{3\cdot 2\cdot 1} = 35.$

Binomski koeficienti so koeficienti razvitja binoma (dvočlenika) (x + y)ⁿ (odtod tudi ime):

$(x+y)^n = \sum_{k=0}^{n} {n \choose k} x^k y^{n-k} \qquad (2)$

To posplošimo z binomskim izrekom, ki dovoljuje, da je eksponent n negativen ali neceloštevilski.

Pomembna rekurenčna enačba:

${n \choose k} + {n \choose k+1} = {n+1\choose k+1} \qquad (3)$

izhaja neposredno iz definicije. Uporabimo jo lahko skupaj z matematično indukcijo pri dokazu, da je C(n, k) naravno število za vse n in k, kar ni povsem razvidno iz definicije. Enačba nam da znani Pascalov aritmetični trikotnik binomskih koeficientov:

    n
    0                     1
    1                   1   1
    2                 1   2   1
    3               1   3   3   1
    4             1   4   6   4   1
    5           1   5   10  10   5   1
    6         1   6   15  20  15   6   1
    7       1   7   21  35  35   21  7   1
    8     1   8  28   56  70  56   28  8   1
    9   1   9  36  84  126  126  84  36  9   1
   10 1  10  45 120  210  252  210 120 45  10  1

Vsaka vrstica, ki jo določa n vsebuje števila C(n, k) za k = 0,...,n. Trikotnik nastane, če v vsaki vrstici od zunaj začnemo z enicami in seštevamo sosednji števili, vsoto pa napišemo pod njima. Na ta način lahko hitro izračunamo binomske koeficiente brez uporabe ulomkov ali množenj. Na primer, če pogledamo vrstico z n = 5, lahko hitro preberemo:

(x + y)⁵ = 1x⁵ + 5 x⁴y + 10 x³y² + 10 x²y³ + 5 x y⁴ + 1y⁵.

Trikotnik je opisal Džu Šidžje leta 1303 v svoji knjigi Dragoceno ogledalo štirih elementov. V svoji knjigi je Ču omenil, da so trikotnik uporabljali že davno, okoli 200 let pred njim, za reševanje binomskih koeficientov. To nam nakazuje, da so metodo poznali kitajski matematiki že 5. stoletij pred Pascalom.

Če v trikotniku obarvamo vsa soda števila in pustimo liha neobarvana, dobimo Sierpinskijev trikotnik. Pascalov trikotnik lahko zapišemo tudi kot kvadratno Pascalovo matriko, kjer binomski koeficienti nastopajo po njenih diagonalah:

$A_{10,10} = \begin{bmatrix} 1& 1& 1& 1& 1& 1& 1& 1& 1& 1\\ 1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ 1& 3& 6& 10& 15& 21& 28& 36& 45& 55\\ 1& 4&10& 20& 35& 56& 84& 120& 165& 220\\ 1& 5&15& 35& 70& 126& 210& 330& 495& 715\\ 1& 6&21& 56& 126& 252& 462& 792& 1287& 2002\\ 1& 7&28& 84& 210& 462& 924& 1716& 3003& 5005\\ 1& 8&36&120& 330& 792&1716& 3432& 6435& 11440\\ 1& 9&45&165& 495&1287&3003& 6435&12870& 24310\\ 1&10&55&220& 715&2002&5005& 11440&24310& 48620 \end{bmatrix} \; ,$

določeno kot:

$A_{1,i} = A_{i,1} = 1 \;$ za i = 1..n

$A_{i,j} = A_{i-1,j} + A_{i,j-1} \;$ drugače.

Simetrična matrika ima precej zanimivih lastnosti in zanimivih razcepitev. Njena determinanta je 1, saj je njen inverz celoštevilčna matrika. Lastne vrednosti so vse realne in pozitivne. Matrika je strogo pozitivno definitna.

[uredi] Kombinatorika in statistika

Binomski koeficienti so pomembni v kombinatoriki, ker nam priskrbijo enačbe za določene pogoste probleme pri preštevanju:

vsaka množica z n elementi ima C(n, k) različnih podmnožic, vsaka s k elementi. To so k-kombinacije)
število znakovnih nizov dolžine n, ki vsebuje k enic in n-k ničel je C(n, k),
število znakovnih nizov s k enicami in n ničlami, kjer noben ni drugemu soseden je C(n+1, k),
število zaporedij, ki vsebuje n naravnih števil, katerih vsota je enaka k je C(n+k-1, k); to je tudi število načinov izbire k elementov iz množice n, če se lahko ponavljajo,
Catalanova števila imajo enostavno enačbo z binomskimi koeficienti. Z njimi lahko preštevamo različne strukture, kot so drevesa ali izrazi z oklepaji.

Binomski koeficienti nastopajo tudi v enačbi za binomsko porazdelitev v statistiki in v enačbi za Bezierovo krivuljo.

[uredi] Enačbe z binomskimi koeficienti

Včasih nam pridejo prav naslednje enačbe:

$C(n, k) = \mathrm{C}(n, n-k) . \qquad (4)$

To sledi, če pri razvoju binoma uporabimo (x + y)ⁿ = (y + x)ⁿ.

$\sum_{k=0}^{n} \mathrm{C}(n,k) = 2^n . \qquad (5)$

Če pri razvoju binoma uporabimo x = y = 1, sledi:

$\sum_{k=1}^{n} k \mathrm{C}(n,k) = n 2^{n-1} . \qquad (6)$

Iz razvoja binoma, po odvajanju in zamenjavi x = y = 1, sledi:

$\sum_{j=0}^{k} \mathrm{C}(m,j) \mathrm{C}(n,k-j) = \mathrm{C}(m+n,k) . \qquad (7)$

Če razvijemo (x + y)ⁿ (x + y)^m = (x + y)^m+n z binomom (tukaj je C(n, k) nič, če je k > n). S to enačbo posplošimo zgornjo rekurenčno enačbo (3):

$\sum_{k=0}^{n} \mathrm{C}(n,k)^2 = \mathrm{C}(2n,n) . \qquad (8)$

Iz predhodnje enačbe (7) z razvojem m = k = n in C(n, k) = C(n, n-k), sledi:

$\sum_{k=0}^{n} \mathrm{C}(n-k,k) = \mathrm{F}(n+1) . \qquad (9)$

Tukaj F(n+1) označuje Fibonaccijeva števila. To enačbo za diagonale Pascalovega trikotnika lahko dokažemo z matematično indukcijo za n v zgornji rekurenčni enačbi (3):

$\sum_{j=k}^{n} \mathrm{C}(j,k) = \mathrm{C}(n+1,k+1) . \qquad (10)$

[uredi] Delitelji binomskih koeficientov

Prafaktorje C(n, k) lahko obravnavamo na naslednji način: če je p praštevilo in je p^r najvišja potenca p, ki deli C(n, k), potem je r enako številu naravnih števil j, da je decimalni del k/p^j večji kot decimalni del n/p^j. Posebej je C(n, k) vedno deljivo zn/(n,k), kjer je (n,k) največji skupni delitelj n in k..