Binomiális tétel

A Wikipédiából, a szabad enciklopédiából
A tétel speciális esete n=3-ra, a és b helyett x és y változókkal.

A binomiális tétel egy matematikai (algebrai) tétel, mely a következő képletben foglalható össze:

(a+b)^n = \sum_{k=0}^n {n \choose k} a^{n-k}b^{k}  ;

részletesebben (szummajel használata nélkül):

(a+b)^n = {n \choose 0} a^{n}b^{0} + {n \choose 1} a^{n-1}b^{1} + ... + {n \choose n-1} a^{1}b^{n-1} + {n \choose n} a^{0}b^{n}  ;
A tétel geometriai jelentése / szemléltetése az n=3 kitevőre.

ahol n természetes szám (n∈ℕ), a,b pedig valós vagy komplex számok, vagy általánosabban, egy kommutatív félgyűrű elemei; továbbá a képletben szereplő ún. binomiális együtthatók a következőképp számolhatóak ki:  \mbox{ }_{ {n \choose k} = \frac{n!}{k!(n-k)!} } ; n! pedig az n faktoriálisát jelenti.

Szavakban megfogalmazva a binomiális tétel egy kéttagú összeg tagonkénti hatványra emelésének módja: egy kéttagú összeget úgy is n-edik hatványra emelhetünk, hogy összeadjuk a két tag összes olyan hatványának szorzatát, mely hatványok kitevői összege a kéttagú összeg kitevője (azaz n), megszorozva a Pascal-háromszög n-edik sorának annyiadik elemével, ahányadaik hatványon az első tag áll a szorzatokban (a Pascal-háromszögben a sorok és a sorok elemeinek számozását is a 0-tól kezdve). A binomiális tétel nem elsősorban egy számoláskönnyítő eljárás (amennyiben konkrét/ismert számokra alkalmazzuk, vannak gyorsabb módszerek az összeg hatványainak kiszámolására [1]), inkább elméleti jelentősége van, alapvető összefüggést mond el a polinomok viselkedéséről (ez azonban nem zárja ki teljesen, hogy a gyakorlatban alkalmazható legyen, sőt, éppen alapvetősége miatt minden területen előbukkanhat, ahol előfordulnak a polinomok - azaz a legváltozatosabb helyeken).

Példák[szerkesztés | forrásszöveg szerkesztése]

(x + y)^0 = 1,\,  x + y \neq 0 \,
(x + y)^1 = x^1 + y^1\,
(x + y)^2 = x^2 + 2xy + y^2\,
(x + y)^3 = x^3 + 3x^2y + 3xy^2 + y^3\,
(x + y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4\,
(x + y)^5 = x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5xy^4+y^5\,
(x + y)^6 = x^6 + 6x^5y + 15x^4y^2 + 20x^3y^3 + 15x^2y^4 + 6xy^5 + y^6\,

Története[szerkesztés | forrásszöveg szerkesztése]

A formulát, a Pascal-háromszöggel együtt gyakran Blaise Pascalnak tulajdonítják, aki a XVII. században leírta ezeket, de már a kínai Yang Hui (XIII. sz., sőt a XI. századi perzsiai muzulmán Omar Khajjám, sőt a Kr. e. 3. századi indiai Pingala is utal rájuk. Az arab matematikusok (Al-Karadzsi, ~953-~1029) már meglehetős biztonsággal alkalmazták kisebb n-ekre [2], Kínában és Indiában az 1100-as években (vagy előbb) fedezhették fel.

A formulát általánosabb alakjában Isaac Newton 1665-ben leírta és bizonyította is.

Bizonyítások[szerkesztés | forrásszöveg szerkesztése]

Kombinatorikus jellegű bizonyítás[szerkesztés | forrásszöveg szerkesztése]

Tudvalevőleg

(a+b)^n =  \underbrace{(a+b)(a+b)...(a+b)}
   
         \mbox{ }_{n-szer}

A (félgyűrűkben mindenképp érvényes) disztributivitás („minden tagot minden taggal”) törvénye alapján x1x2…xn alakú szorzatokat kapunk, ahol x1, x2,…, xn ∈{a,b}. Ezeket kell összegezni. Egy ilyen tag úgy is adódhat, hogy kiválasztjuk az első zárójelben lévő a vagy b tag közül az egyiket (tetszőlegeset), aztán a másodikból is az a-t vagy b-t (tetszőlegesen), és így tovább. Tehát így valóban a tagok akbn-k alakúak lesznek (a kitevők összege ugyanis n-et kell, hogy adjon, hiszen összesen n darab a-t vagy b-t választunk ki a zárójelekből és szorzunk össze), ahol 0≤k≤n. Például ha mind az n db. zárójelből az a-t választjuk ki, úgy adódik az anb0 = an tag. A kérdés, rögzített k-ra hány darab darab akbn-k létezik (több is létezhet, például már n=2 esetén is, a kommutativitás miatt, kétféle a1b1 = ab alakú tag áll elő aszerint, hogy az első zárójelből a-t és a másodikból b-t, illetve aszerint, hogy az első zárójelből b-t és a másodikból a-t választjuk).

Elegendő csak az a-k kitevője szerint vizsgálódni, hiszen ha a kitevője a rögzített k, akkor b kitevője már egyértelműen n-k. Annyiféle akbn-k alakú tag lehet tehát, ahányféleképp n db. a szorzót választhatunk az n darab (a+b) zárójelből (a többi szorzó automatikusan b), tehát ahányféleképp az n db. a szorzó közül kiválaszthatunk k db. a szorzót, vagyis ahányféleképp egy n elemű halmazból (az a szorzók halmazából) kiválasztható k db. elem (k darab a szorzó); s ez a szám egy n elemű halmaz k elemű részhalmazainak a számát megadó binomiális együttható,  \mbox{ }_{ {n \choose k} } .

Tehát két tag összegének n-edik hatványa valóban n összegű kitevőjű a- és b alapú hatványok szorzatainak („tagok”) összege, és az egyes tagok együtthatója valóban a képletben szereplő binomiális együttható .

Indukciós bizonyítás[szerkesztés | forrásszöveg szerkesztése]

Teljes indukciót használunk, a „Pascal-képletet” is alkalmazva ( \mbox{ }_{ {m+1 \choose k+1} = {m \choose k+1} + {m \choose k} } ). Ha n = 0, akkor

 (a+b)^0 = 1 és  \sum_{k=0}^0 { 0 \choose k } a^{0-k}b^k = { 0 \choose 0 } a^{0}b^0 = 1·1·1 = 1

valóban igaz, mert bármely valós szám, illetve kommutatív félgyűrűelem nulladik hatványa definíció szerint 1. A példák alatt láthatóan teljesül a tétel egyéb kis n-ekre is.

Indukciós feltevésként legyen igaz a tétel valamely m \ge 0-ra. Akkor n=m+1-re a következőképp látható be:

 (a+b)^{m+1} = (a+b)^{m}(a+b) = a(a+b)^m + b(a+b)^m \,
 = a \sum_{k=0}^m { m \choose k } a^{m-k} b^{k} + b \sum_{j=0}^m { m \choose j } a^{m-j} b^{j} az indukciós feltevés alapján;
 = \sum_{k=0}^m { m \choose k } a^{m-k+1} b^k + \sum_{j=0}^m { m \choose j } a^{m-j} b^{j+1}, elvégezve a kijelölt beszorzásokat a-val, illetve b-vel;
 = \left[ \sum_{k=1}^{m} {m \choose k} a^{m-k+1} b^k + {m \choose 0} a^{m-0+1}b^{0} \right] +  \left[ \sum_{j=0}^{m-1} {m \choose j} a^{m-j} b^{j+1} + {m \choose m} a^{m-m} b^{m+1} \right], az első részösszegből különválasztva a k=0, a másodikból pedig a j=m indexű, összesen két db. tagot; tehát:
 = {m \choose 0} a^{m+1}b^{0}  +  \left[ \sum_{k=1}^{m} {m \choose k} a^{m-k+1} b^k + \sum_{j=0}^{m-1} {m \choose j} a^{m-j}b^{j+1} \right]  +  {m \choose m} a^{0} b^{m+1}; a k futóindex helyébe is j-t írhatunk, figyelembe véve, hogy j 0-tól m-1-ig fut, míg k 1-től m-ig, tehát k=j+1, és így helyettesítve a, b hatványkitevői is a megfelelőképp kell hogy módosuljanak, kapjuk:
 = {m \choose 0} a^{m+1}b^{0}  +  \left[ \sum_{j=0}^{m-1} {m \choose j+1} a^{[m-(j+1)+1]} b^{j+1} + \sum_{j=0}^{m-1} {m \choose j} a^{m-j}b^{j+1} \right]  +  {m \choose m} a^{0} b^{m+1}; azaz:
 = {m \choose 0} a^{m+1}b^{0}  +  \left[ \sum_{j=0}^{m-1} {m \choose j+1} a^{m-j} b^{j+1} + \sum_{j=0}^{m-1} {m \choose j} a^{m-j}b^{j+1} \right]  +  {m \choose m} a^{0} b^{m+1}; azaz:
 = {m \choose 0} a^{m+1}b^{0} + \sum_{j=0}^{m-1} \left[ {m \choose j+1} a^{m-j} b^{j+1} + {m \choose j} a^{m-j}b^{j+1} \right] +  {m \choose m} a^{0} b^{m+1}; azaz:
 = {m \choose 0} a^{m+1}b^{0} + \sum_{j=0}^{m-1} \left[ {m \choose j+1} + {m \choose j} \right] a^{m-j}b^{j+1} +  {m \choose m} a^{0} b^{m+1}; alkalmazva a binomiális együtthatókra vonatkozó (szintén indukcióval bizonyítható) Pascal-képletet, és figyelembe véve, hogy  {m \choose 0} = 1 = {m+1 \choose 0} és  {m \choose m} = 1 = {m+1 \choose m+1} minden m-re:
 = {m+1 \choose 0} a^{m+1}b^{0} + \sum_{j=0}^{m-1} {m+1 \choose j+1} a^{m-j}b^{j+1} + {m+1 \choose m+1} a^{0} b^{m+1}; most j helyébe k=j+1-et írva, s figyelembe véve, hogy j=k-1, j 0-tól m-1-ig fut, és a többi ilyesmit:
 = {m+1 \choose 0} a^{m+1}b^{0} + \sum_{k=1}^{m} {m+1 \choose k} a^{m-(k-1)}b^{k} + {m+1 \choose m+1} a^{0} b^{m+1}; azaz
 = {m+1 \choose 0} a^{m+1}b^{0} + \sum_{k=1}^{m} {m+1 \choose k} a^{m+1-k}b^{k} + {m+1 \choose m+1} a^{0} b^{m+1}; és így
 = \sum_{k=0}^{m+1} {m+1 \choose k} a^{m+1-k}b^{k} ; és mivel m+1=n, így
 = \sum_{k=0}^{n} {n \choose k} a^{n-k}b^{k} ;

és épp ez kellett .

Egyszerű következmények és alkalmazások[szerkesztés | forrásszöveg szerkesztése]

Az n-edrendű binomiális együtthatók összege és váltakozó előjelű összege[szerkesztés | forrásszöveg szerkesztése]

Klasszikus diszkrét matematikai (algebra-kombinatorika) következménye a tételnek az a két azonosság, mely a Pascal-háromszög n-edik sorában álló elemek összegéről, illetve váltakozó előjellel vett összegéről szól:

Ha tekintjük az a=1, illetve b=1 helyettesítést, akkor kapjuk, hogy

\sum_{k=0}^{n} { n \choose k } = 2^n.

Ha tekintjük az a=1, illetve b=-1 helyettesítést, akkor kapjuk, hogy

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

vagyis a binomiális együtthatók váltakozó előjelű összege 0.

Hatványfüggvény deriváltja[szerkesztés | forrásszöveg szerkesztése]

Klasszikus analitikus alkalmazása a tételnek az xc·xn valós vagy komplex hatványfüggvények deriváltját megadó egyszerű képlet, eszerint:

 \left(c \cdot x^n \right)' = \lim_{\Delta x \to 0} \frac{ c \cdot \left( x+ \Delta x \right)^n - c \cdot \left( x \right)^n }{\Delta x} = cnx^{n-1}

Általánosítások[szerkesztés | forrásszöveg szerkesztése]

A polinomiális tétel[szerkesztés | forrásszöveg szerkesztése]

A polinomiális tétel képlettel:

(a_1 + a_2 + ... + a_k)^n = \sum_{i_1 + i_2 + ... + i_k = n} \frac{n!}{i_1! i_2! ... i_k!} \cdot a_1^{i_1} a_2^{i_2} ... a_k^{i_k}

Bizonyítás: ha elvégezzük az (a_1 + a_2 + ... + a_k)^n hatványozását, csupa n-edfokú tagokat fogunk kapni. Az n db zárójeles tényező összeszorzásakor meg fogjuk kapni az összes lehetséges n elemű ismétléses variációt. (Pl. 5 tag esetén néhány: (a_1\cdot a_1\cdot a_2\cdot a_3\cdot a_1 + a_1\cdot a_1\cdot a_1\cdot a_2\cdot a_3 + ... stb. ) . Mindegyiket csak egyszer kapjuk meg. Viszont mivel a szorzás kommutatív, ezért az előbbi példa esetében is látható, hogy mindkét tag ugyanazokat és ugyanannyi db tagot tartalmaz, csak más sorrendben. A végeredményben ezek tehát összevonhatók és valamilyen együtthatót kapnak - attól függően, hogy hány ilyen adott összetételű tagot vontunk össze. Így ahhoz, hogy egy valamilyen adott  a_1^{i_1}\cdot a_2^{i_2}\cdot a_3^{i_3}\cdot ...\cdot a_k^{i_k} tag együtthatóját meg tudjuk mondani, ki kell számítani, hogy hány variáció tartalmaz pontosan i_1 db a_1 -et, i_2 db  a_2 -t, ... , i_k db a_k -t.

Így tulajdonképpen az a kérdés, hogy az n db zárójeles tényezőből hányféleképp választható ki - egy adott formáció esetén - i_1 db  a_1 , i_2 db a_2 , ... , i_k db  a_k , ahol  i_1+i_2+...+i_k=n, hiszen az n db zárójelből pontosan n db kiválasztást kell tenni. Ez a kiválasztás így írható fel: {n \choose i_1}\cdot{n-i_1 \choose i_2}\cdot ... \cdot {n-i_1-i_2-...-i_{k-1} \choose i_k}=\frac {n!}{i_1!(n-i_1)!}\cdot\frac{(n-i_1)!}{i_2!(n-i_1-i_2)!}\cdot ... \cdot\frac{(n-i_1-i_2-...-i_{k-1})!}{i_k!(n-i_1-i_2-...-i_k)!}=
\frac{n!}{i_1!i_2!...i_k!}. Ha tehát kiválasztjuk, hogy mely és hány db tagból hányféle variáció lehetséges, akkor egy ilyen összetételű tagnak \frac{n!}{i_1!i_2!...i_k!} lesz az együtthatója. Ha pedig az egész kifejezés összes tagjára, és azok együtthatóira vagyunk kíváncsiak, akkor ezt "el kell játszani" minden tag esetén, hisz minden tag összetétele más és más. Ezért ezeket összegezni kell: (a_1 + a_2 + ... + a_k)^n = \sum_{i_1 + i_2 + ... + i_k = n} \frac{n!}{i_1! i_2! ... i_k!} \cdot a_1^{i_1} a_2^{i_2} ... a_k^{i_k}, ami épp a kezdeti felírás jobb oldala; ezzel beláttuk a képlet igaz voltát. Nézzünk néhány példát: (a+b)^3 esetén mennyi lesz az a^2b együtthatója? A képlet alapján: \frac{3!}{2!1!}=3, ami ilyen egyszerű esetben minden tag minden taggal való összeszorzásából, vagy a binomiális tételből (ami a polinomiális tétel speciális esete) vagy a Pascal háromszögből szintén meghatározható. De mi a helyzet, ha mondjuk (a+b+c+d+f)^9 esetén az a^3bc^2d^2f tag együtthatóját keressük? A válasz a képlet alapján: \frac{9!}{3!1!2!2!1!}=15120, ami meglepőnek látszik, de a tétel alapján ez a megoldás.

Newton általánosított binomiális tétele[szerkesztés | forrásszöveg szerkesztése]

Isaac Newton első jelentős matematikai felfedezése volt a binomiális tétel általánosítása racionális kitevőkre. Képlete azonban komplex kitevőkre is érvényes:

 (x+y)^r \ = \ \sum_{k=0}^{\infty} {r \choose k} x^k y^{r-k}

ahol r tetszőleges komplex szám, az  \mbox{ }_{ {r \choose k} } általánosított binomiális együtthatók kiszámítása pedig a következő:
 \mbox{ }_{ {r \choose k} \ = \ {1 \over k!} \prod_{n=0}^{k-1}(r-n) \ = \ \frac{r(r-1)(r-2)\cdots(r-(k-1))}{k!} }\, [3]; vagy pedig  \mbox{ }_{ {r \choose k}=\frac{(-1)^k}{k!}(-r)_k };
ahol (...)_k az ún. Pochhammer-szimbólum.


A binomiális tétel a kultúrában[szerkesztés | forrásszöveg szerkesztése]

  • Sir Arthur Conan Doyle Sherlock Holmes-történeteiben az elvetemült Moriarty professzor a szerzője az A Treatise on the Binomial Theorem (Értekezés a binomiális tételről) c. munkának.
  • Legalább három különböző Monty Python-műben (Coal Mine, Happy Valley, Az élet értelme) említődik a tétel.
  • Mihail Bulgakov A Mester és Margarita c. regényében a Fokics nevű büfés azt állítja a sátáni Woland professzornak, hogy a saját halálát senki sem képes előre látni, Woland és szolgái ezt megcáfolják azzal a tényleg beteljesülő jóslattal, miszerint májrákban fog meghalni egy klinikán; bizonyítékként pedig „Newton binomiális tételére” hivatkoznak. A tételre hivatkozás valószínű motivációja, hogy a binomiális tétel alapvető szerepet játszik a klasszikus genetikában, felbukkan pl. a Hardy–Weinberg-törvényben, amely Weinberg révén 1908 óta ismert volt (szerepéről az 1916-ban orvosi diplomát kapó Bulgakov is tudhatott). A valószínűségszámítás és az emberi öröklődés kapcsolatáról Korovjov más hasonló megjegyzéseket is tesz a regényben („egy pakli kártya”).
  • Fernando Pessoa (18881935) portugál költő egy egész, bár rövid költeményt (A Newton féle binomiálisO binomio de Newton) szentelt a tételnek [4], mi szerint: A Newton-féle binomiális ugyanolyan szép, mint a Milói Vénusz. Legfeljebb kevesen vesznek róla tudomást.

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  1. Például a Gyors bináris alapú hatványozás, ami körülbelül 2log(n) szorzást igényel. A két szám, a és b összeadása utáni hatványozásból a binomiális tétel „jobb” oldala alapján n+1 hatványozást igényel, ami nagyságrendileg jóval több, mint 2log(n), és akkor a binomiális együtthatók kiszámításáról és az ezekkel való szorzásról még szó sem esett. A két eljárás számításigény-viszonyának pontos felbecslése nehéz, függ az alkalmazott módszerektől is (például gyors szorzáskor az a és b összegét át kell írni kettes számrendszerre, de ez is csak kb. log2(a+b) db. maradékos osztást követel; a binomiális együtthatók számításigénye függhet attól, hogy rekurzív módon vagy faktoriálisokká kifejtve számolunk-e, de nagyon durva közelítéssel is, a binomiális tétellel való számolás nagy kitevők esetén jóval számításigényesebb.
  2. Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji életrajza a Szent András-Egyetem honlapján (MacTutor Archive).
  3. A k = 0, esetben a képlet „tényezők nélküli szorzat”, így szükségképp 1, a k = 1 esetben pedig r.
  4. A Newton-féle – F. Pessoa verse a Ponticulus Hungaricus c. webhelyen

További információk[szerkesztés | forrásszöveg szerkesztése]

Kapcsolódó szócikkek[szerkesztés | forrásszöveg szerkesztése]