Binomni poučak

Binomni koeficijenti se mogu izračunati kao dijelovi Pascalova trokuta, gdje je svaki broj zbroj ona dva iznad njega.

U elementarnoj algebri, binomni poučak opisuje algebarsko proširivanje potencije binoma. Prema tom poučku moguće je (x + y)ⁿ proširiti u sumu koja uključuje izraze oblika ax^by^c, gdje su b i c pozitivni cijeli brojevi, i koeficijent a je specifični pozitivni broj ovisan o n i b. Kada je eksponent jednak nuli, taj se element izostavi iz niza. Na primjer :

[math]\displaystyle{ (x+y)^4 \;=\; x^4 \,+\, 4 x^3y \,+\, 6 x^2 y^2 \,+\, 4 x y^3 \,+\, y^4. }[/math]

Koeficijent a u izrazu ax^by^c je također poznat kao binomni koeficijent [math]\displaystyle{ \tbinom nb }[/math] ili [math]\displaystyle{ \tbinom nc }[/math] (ova dva imaju istu vrijednost). Ovi koeficijenti za različite n i b se mogu složiti u Pascalov trokut. Ovi se brojevi također pojavljuju u kombinatorici, gdje [math]\displaystyle{ \tbinom nb }[/math] daje broj različitih kombinacija b elemenata izabranih iz skupa od n elemenata.

Povijest

Formula i prikaz binomnih koeficijenata u obliku trokuta se često pripisuju Blaiseu Pascalu, koji ih je opisao u 17. stoljeću, iako je bio poznat mnogim matematičarima prije njega. U 4. stoljeću pr. Kr grčki matematičar Euklid je znao posebni slučaj binomnog poučka za n=2, kao i u 3. stoljeću pr. Kr indijski matematičar Pingala za više eksponente. Općeniti binomni poučak i takozvani "Pascalov trokut" su bili poznati u 10. stoljeću poslije Krista indijskom matematičaru Halayudhi i perzijskom matematičaru Al-Karaji, te u 11. stoljeću perzijskom pjesniku i matematičaru Omaru Khayyamu,i u 13. stoljeću kineskom matematičaru Yangu Huiu, koji su svi imali slične rezultate. Al-Karaji je također dokazao binomni poučak i "Pascalov trokut", koristeći matematičku indukciju.

Iskaz poučka

Prema poučku, moguće je proširiti bilo koju potenciju od x + y u zbroj oblika :

[math]\displaystyle{ (x+y)^n = {n \choose 0}x^n y^0 + {n \choose 1}x^{n-1}y^1 + {n \choose 2}x^{n-2}y^2 + \cdots + {n \choose n-1}x^1 y^{n-1} + {n \choose n}x^0 y^n, }[/math], gdje je [math]\displaystyle{ \tbinom nk }[/math] specifični pozitivan broj poznat kao binomni koeficijent. Ovo je također poznato kao binomna formula ili binomni identitet. Također se može zapisati kao :

[math]\displaystyle{ (x+y)^n = \sum_{k=0}^n {n \choose k}x^{n-k}y^k = \sum_{k=0}^n {n \choose k}x^{k}y^{n-k}. }[/math]

Jedna od varijanti binomne formule se dobiva zamjenom 1 za y, tako da ima samo jednu varijablu. U ovom obliku, formula izgleda ovako :

[math]\displaystyle{ (1+x)^n = {n \choose 0}x^0 + {n \choose 1}x^1 + {n \choose 2}x^2 + \cdots + {n \choose {n-1}}x^{n-1} + {n \choose n}x^n, }[/math]

ili ekvivalentno :

[math]\displaystyle{ (1+x)^n = \sum_{k=0}^n {n \choose k}x^k. }[/math]

Dokazi

Kombinatorni dokaz

Kub binoma

Dokazat ćemo teorem za [math]\displaystyle{ n = 3, }[/math] a analogno se dokazuje za bilo koji prirodni broj [math]\displaystyle{ n. }[/math]

Želimo izračunati [math]\displaystyle{ (x + y)^3 = (x + y)(x + y)(x + y). }[/math]

Prema distributivnom pravilu u algebri proširujemo izraz: [math]\displaystyle{ xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy. }[/math]

Uočimo da će svaki pribrojnik imati točno tri faktora te da su neki pribrojnici jednaki, tj. da se ponavljaju. Ta pravilna ponavljanja će nam dati tzv. binomne koeficijente. Uočimo da smo raspisivanjem na ovaj način dobili svaku moguću listu ili poredak dva objekta, [math]\displaystyle{ x, y }[/math] raspoređenih na [math]\displaystyle{ 3 }[/math] mjesta. Napomenimo još da je svaki poredak, tj. pribrojnik u raspisu, naveden točno jednom (iako su, očito nakon računanja, primjerice, pribrojnici [math]\displaystyle{ xxy, xyx }[/math] jednaki) te svaki pribrojnik odgovara nekom od mogućih poredaka. Zato će biti moguće jednostavno provesti sljedeći kombinatorni račun.

Nađimo, na primjer, koliko ima pribrojnika koji sadrže točno dva faktora [math]\displaystyle{ y }[/math], tj. nabrojimo koliko ima pribrojnika koji su jednaki [math]\displaystyle{ xy^2. }[/math]

Označimo prvo mjesto liste s [math]\displaystyle{ 1, }[/math] drugo s [math]\displaystyle{ 2 }[/math], itd. te neka je [math]\displaystyle{ S = \{1, 2, ..., n\}. }[/math] Sada zapravo tražimo na koliko načina možemo izabrati 2 elementa skupa [math]\displaystyle{ S }[/math] s tim da poredak u potpunosti zanemarujemo, tj. npr. odabir [math]\displaystyle{ (1, 2) }[/math] je očito jednak odabiru [math]\displaystyle{ (2, 1) }[/math] jer ne permutiramo jedan objekt, u ovom slučaju faktor [math]\displaystyle{ y }[/math].

Tih odabira ima točno [math]\displaystyle{ {3 \choose 2} = \frac{3 \cdot 2}{2} = 3. }[/math]

Dakle, faktora [math]\displaystyle{ x^3 }[/math] ima [math]\displaystyle{ {3 \choose 0} = 1 }[/math], faktora [math]\displaystyle{ x^2y }[/math] ima [math]\displaystyle{ {3 \choose 1} = 3, }[/math] faktora [math]\displaystyle{ xy^2 }[/math] ima [math]\displaystyle{ {3 \choose 2} = 3 }[/math] te konačno faktora [math]\displaystyle{ y^3 }[/math] ima [math]\displaystyle{ {3 \choose 3} = 1. }[/math]

Ovdje je moguće uočiti i osnovne relacije iz Pascalova trokuta zbog simetričnosti strukture koju promatramo.

Generalni slučaj

Sada možemo prijeći na generalni slučaj, [math]\displaystyle{ (x + y)^n = (x + y) \cdot ... \cdot (x + y) \ (n \text{ faktora}) }[/math] te koristimo distributivno pravilo na gore navedeni način.

Svaki pribrojnik će imati [math]\displaystyle{ n }[/math] faktora. Označimo prvo mjesto s [math]\displaystyle{ 1, }[/math] drugo mjesto s [math]\displaystyle{ 2, }[/math] itd. Dakle, zapravo tražimo broj načina za izabrati [math]\displaystyle{ k }[/math] elemenata iz [math]\displaystyle{ S = \{1, 2, ..., n\}. }[/math]

Tražimo koliko ima pribrojnika koji imaju [math]\displaystyle{ 0 \leq k \leq n }[/math] faktora [math]\displaystyle{ y. }[/math] Sada je jasno da zapravo tražimo broj načina za izabrati [math]\displaystyle{ k }[/math] elemenata iz [math]\displaystyle{ S = \{1, 2, ..., n\}. }[/math] Broj načina je jednak [math]\displaystyle{ \frac{n!}{(n - k)!k!} = {n \choose k}. }[/math]

Uz to, uočimo još da je prema gornjoj argumentaciji [math]\displaystyle{ k }[/math]-ti član u raspisu zaista [math]\displaystyle{ {n \choose k - 1}x^{n - k}y^k. }[/math]

Dokaz indukcijom

Binomna se formula, odnosno ekspanzija izraza [math]\displaystyle{ (a + b)^n }[/math], jednostavno može dokazati metodom matematičke indukcije.

Za [math]\displaystyle{ n = 1 }[/math] valjanost formule je očigledna.

Pretpostavimo zato da je formula ispravna za neki prirodni broj [math]\displaystyle{ n }[/math].

Tada je [math]\displaystyle{ {(a + b)}^{n + 1} = (a + b){(a + b)}^n }[/math].

Prema pretpostavci, sada pišemo [math]\displaystyle{ (a + b)^{n + 1} = (a + b)\sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k }[/math], što daje [math]\displaystyle{ \sum_{k=0}^{n} \binom{n}{k} a^{n+1-k} b^k + \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^{k + 1} }[/math].

Zbrajajući članove ove ekspanzije, dobivamo da je binomni koeficijent ispred monoma [math]\displaystyle{ a^{n + 1 - k}b^k }[/math] jednak [math]\displaystyle{ {n}\choose{k} }[/math] [math]\displaystyle{ + }[/math] [math]\displaystyle{ {n}\choose{k - 1} }[/math].

Pascalovom pravilo za binomne koeficijente je

Vrijedi identitet za binomne koeficijente

[math]\displaystyle{ {n}\choose{k} }[/math] [math]\displaystyle{ + }[/math] [math]\displaystyle{ {n}\choose{k - 1} }[/math] [math]\displaystyle{ = }[/math] [math]\displaystyle{ {n + 1}\choose{k} }[/math], a zovemo ga Pascalovom formulom (ili pravilom), a njenom primjenom odmah slijedi valjanost formule za [math]\displaystyle{ n+1 }[/math].

Primjeri

Pascalov trokut

Najjednostavniji primjer je kvadrat od x+y :

[math]\displaystyle{ (x + y)^2 = x^2 + 2xy + y^2.\! }[/math]

Binomni koeficijenti 1, 2, 1 se pojavljuju u trećem redu Pascalova trokuta. Koeficijenti za veće eksponente se nalaze u nižim redovima Pascalova trokuta.

[math]\displaystyle{ \begin{align} (x+y)^3 & = x^3 + 3x^2y + 3xy^2 + y^3, \\[8pt] (x+y)^4 & = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4, \\[8pt] (x+y)^5 & = x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5xy^4 + y^5, \\[8pt] (x+y)^6 & = x^6 + 6x^5y + 15x^4y^2 + 20x^3y^3 + 15x^2y^4 + 6xy^5 + y^6, \\[8pt] (x+y)^7 & = x^7 + 7x^6y + 21x^5y^2 + 35x^4y^3 + 35x^3y^4 + 21x^2y^5 + 7xy^6 + y^7. \end{align} }[/math]

Primijetite da :

1. eksponenti od x se smanjuju dok ne dođu do nule ([math]\displaystyle{ x^0=1 }[/math]), a početna im je vrijednost n
2. eksponenti od y rastu dok ne dođu do n, a početna im je vrijednost 0 ([math]\displaystyle{ x^0=1 }[/math])
3. N-ti red Pascalova trokuta će biti koeficijenti proširenog binoma. (Red na vrhu je red 0)
4. Za svaki red Pascalova trokuta, zbroj koeficijenata je jednak [math]\displaystyle{ 2^n }[/math].

Za binome koji imaju oduzimanje, poučak se također može primijeniti, sve dok mijenjamo predznak svako drugom koeficijentu u izrazu :

[math]\displaystyle{ (x-y)^3 = x^3 - 3x^2y + 3xy^2 - y^3.\! }[/math]

Geometrijski dokaz

Geometrijski dokaz binomnog poučka

Za pozitivne vrijednosti a i b, binomni poučak za n = 2, geometrijski je očito da se kvadrat sa stranicom (a+b) može izrezati u kvadrat sa stranicom [math]\displaystyle{ a^2 }[/math], kvadrat sa stranicom [math]\displaystyle{ b^2 }[/math], i dva pravokutnika da stranicama a i b. Za n=3, poučak kaže da se kocka sa stranicom (a + b) može izrezati u kocku sa stranicom [math]\displaystyle{ a^3 }[/math], kocku sa stranicom [math]\displaystyle{ b^2 }[/math], tri kvadra oblika a×a×b te tri kvadra oblika a×b×b.

Binomni koeficijenti

Koeficijenti koji se pojavljuju u binomnom poučku se zovu binomni koeficijenti.

Formule

Koeficijent od x^n−ky^k je zadan formulom

[math]\displaystyle{ {n \choose k} = \frac{n!}{k!\,(n-k)!} }[/math],

koji je definiran funkcijom faktorijela. Također, formula se može zapisati kao  :

[math]\displaystyle{ {n \choose k} = \frac{n (n-1) \cdots (n-k+1)}{k (k-1) \cdots 1} = \prod_{\ell=1}^k \frac{n-\ell+1}{\ell} }[/math]

Iako ova formula sadrži razlomak, rezultat je uvijek cijeli broj. Dokaz:

1. Potrebno je dokazati da k! dijeli umnožak k uzastopnih cijelih brojeva.
2. Rastavimo umnoške na proste faktore. Dokazat ćemo da se neki prosti faktor p pojavljuje u k! manje ili jednako puta koliko u umnošku k uzastopnih brojeva.
3. Indukcijom, p se u umnošku k uzastopnih brojeva najmanje puta pojavljuje za n = k p + 1 (k ∈ ℤ) jer će mu najduže trebati da prođe prvi višekratnik, pa sljedeći itd.
4. Za k = 0, n = 1 te je time tvrdnja dokazana.

Generalizacija

Poučak je moguće generalizirati s [math]\displaystyle{ (x + y)^n }[/math] na [math]\displaystyle{ (x_1 + x_2 + ... + x_m)^n }[/math]. Zato se taj generalizirani teorem naziva Polinomijalna formula ili ponegdje Multinomni teorem. Kombinatorni dokaz tog teorema sličan je dokazu navedenom u ovom članku.