Биномни коефицијент

Из Википедије, слободне енциклопедије

У математици, а посебно у комбинаторици, биномни коефицијент природног броја n и целог броја k дефинисан је као природни број:

 {n \choose k} = \frac{n!}{k!(n-k)!}
=\prod_{i=1}^k{n+1-i\over i}, 
\quad n\geq k\geq 0 \qquad \mbox{(1)}

и

 {n \choose k} = 0 ako је k<0 или k>n.

(За природни број m, m! означава факторијел броја m.)

Биномни коефицијент од n и k се такође пише и као C(n, k) или Cnk и чита као »n над k«. Према Николасу Хигаму, нотацију  {n \choose k} је увео у употребу Алберт фон Етингхаузен 1826, иако се за ове бројеве знало вековима пре тога (погледати: Паскалов троугао).

Пример:

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

Биномни коефицијенти су коефицијенти у развоју бинома (x + y)n (одатле и назив):

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

Ово је генерализовано биномном теоремом која дозвољава да n буде негативан или реалан број.

Паскалов троугао[уреди]

Важна рекурзивна релација

C(n,k) + C(n,k+1) = C(n+1,k+1) \qquad (3)

следи директно из дефиниције биномног коефицијента. Овом релацијом, и математичком индукцијом се може доказати да је C(n, k) природни број, за свако n и k (што није најочигледније одмах из дефиниције).


На тај начин се конструише Паскалов троугао:

ред 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

n.-ти ред садржи бројеве C(n, k) за k = 0,...,n. Паскалов троугао се конструише тако да се креће од 1, а нови број се добија сабирањем суседа из претходног реда. Овако се брзо могу израчунати биномни коефицијенти без потребе за множењем и дељењем. Нпр. само гледајући 5. ред, можемо константовати:

(x + y)5 = 1x5 + 5 x4y + 10 x3y2 + 10 x2y3 + 5 x y4 + 1y5.

1303. године у делу Драгоцено огледало четири елемента (Precious Mirror of the Four Elements) Цу Шиђе (Zhu Shijie) помиње овај троугао за решавање биномних коефицијената, што указује да је овај метод био познат кинеским математичарима пет векова пре Блез Паскала.

Комбинаторика и статистика[уреди]

Биномни коефицијенти су од велике важности у комбинаторици јер нуде готове формуле за честе проблеме пребројавања:

  • Сваки скуп са n поседује тачно {n\choose k} различитих подскупова који имају k елемената
  • Број бинарних бројева дужине n које садрже k јединица и n − k нула је {n\choose k}.
  • Број бинарних бројева који садрже k јединица и n нула тако да никоје две нису суседне је {n+1\choose k}.
  • Број различитих секвенци од n природних бројева чији је укупни збир k је {n+k-1\choose k}; ово је такође број различитих начина да се из скупа са n елемената изабере k елемената уколико је дозвољено понављање.

Биномни коефицијенти се појављују и у формули за биномну расподелу у статистици, као и у формули за Безијерову криву.

Формуле са биномним коефицијентима[уреди]

Следеће формуле могу бити корисне:

C(n,k)=C(n, n-k)\qquad\qquad(4)\,

Ово следи из развоја (2) користећи (x + y)n = (y + x)n, и огледа се у нумеричкој симетричности Паскаловог троугла.

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

Из развоја (2) стављајући x = y = 1. Види се и из Паскаловог троугла да је сума свих чланова једног реда једнака степену двојке.

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

Из развоја (2) после диференцирања и замењујући x = y = 1.

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

Развијајући (x + y)n (x + y)m = (x + y)m+n из (2) (C(n, k) је дефинисано као 0 за k > n). Ова једначина генерализује (3).

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

Из развоја (7) стављајући m = k = n и користећи једначину (4).

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

Овде, F(n + 1) представља Фибоначијеве бројеве.

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

Ова једначина може бити доказана индукцијом по n користећи (3).

Генерализација са комплексним аргументом[уреди]

Биномни коефицијент {z\choose k} може се дефинисати за било који комплексни број z и било који природни број k:

{z\choose k} = {1 \over k!}\prod_{n=0}^{k-1}(z-n)= \frac{z(z-1)(z-2)\cdots (z-k+1)}{k!} \qquad (11)

Ова генерализација је позната као уопштени биномни коефицијент и користи се при формулацији биномне теореме, а задовољава и својства (3) и (7).

За константно k, израз {z\choose k} је полином по z степена k са рационалним коефицијентима. Сваки полимом p(z) степена d може се написати у форми

 p(z) = \sum_{k=0}^{d} a_k {z\choose k}

са одговарајућим коефицијентима ak. Ово је нарочито важно у теорији диференцијалних једначина и може се посматрати као дискретна аналогија Тејлорове теореме.

Границе биномних коефицијената[уреди]

За биномни коефицијент C(n, k) важе следеће границе:

  •  {n \choose k} \le \frac{n^k}{k!}
  •  {n \choose k} \le \left(\frac{n\cdot e}{k}\right)^k
  • {n\choose k}\ge \left(\frac{n}{k}\right)^k

Референце[уреди]

Спољашње везе[уреди]