: نظریه دو جمله ای ها

||V{maketoc}||

^@#16:

!نظریه دو جمله ای ها

!!مثال

ضریب عبارت{TEX()} {x^3y^2} {TEX} را در عبارت{TEX()} {(x+y)^5} {TEX} بیابید.

__حل__

در بسط عبارت

@@{TEX()} {(x+y)^5=(x+y)(x+y)(x+y)(x+y)(x+y)} {TEX}@@

باید از هر یک از 5 عامل {TEX()} {x} {TEX}یا {TEX()} {y} {TEX}را انتخاب کرد و به ازای هر حالتی که از 3 تا از آنها {TEX()} {x} {TEX}و از 2 تای دیگر {TEX()} {y} {TEX}را انتخاب کنیم یک واحد به ضریب{TEX()} {x^3y^2} {TEX} اضافه می شود. حال ما یک تناظر یک به یک بین ضریب{TEX()} {x^3y^2} {TEX} در عبارت{TEX()} {(x+y)^5} {TEX} و تعداد کلمات 5 حرفی که با 3 تا {TEX()} {x} {TEX}و 2 تا {TEX()} {y} {TEX}ساخته می شوند برقرار می کنیم.

به ازای هر راه انتخاب {TEX()} {x} {TEX}یا {TEX()} {y} {TEX}از هر عامل یک کلمه ی 5 حرفی به این شکل می سازیم که اگر از عامل {TEX()} {i} {TEX}ام {TEX()} {(1 \le i \le 5)} {TEX} {TEX()} {x} {TEX}انتخاب شده باشد، حرف {TEX()} {i} {TEX}ام این کلمه را {TEX()} {x} {TEX}و در غیر این صورت {TEX()} {y} {TEX}می گذاریم. به عنوان مثال اگر ما از عامل های اول، دوم، سوم، چهارم و پنجم، به ترتیب{TEX()} {x,x,y,y,x} {TEX}را انتخاب کنیم معادل کلمه ی{TEX()} { xyyxx } {TEX} است. هم چنین کلمه ی{TEX()} { xxxyy } {TEX} ، متناظر با حالتی است که از عامل های اول، دوم، سوم، چهارم و پنجم به ترتیب{TEX()} {y,y,x,x,x} {TEX}را انتخاب کنیم.

واضح است که این یک تناظر یک به یک بین ضریب{TEX()} {x^3y^2} {TEX} در عبارت{TEX()} {(x+y)^5} {TEX} و تعداد کلمات 5 حرفی که با 3 تا {TEX()} {x} {TEX}و 2 تا {TEX()} {y} {TEX}ساخته می شوند برقرار می کند. پس ضریب{TEX()} {x^3y^2} {TEX} در عبارت{TEX()} {(x+y)^5} {TEX} برابر است با {TEX()} {{5\choose 3}={5\choose 2}=\frac{5!}{3!2!}=10} {TEX}.

---

!!مثال

__الف__ ضریب{TEX()} {x^2y^5} {TEX} را در عبارت{TEX()} {(x+y)^7} {TEX} بیابید.

__ب.__ ضریب{TEX()} {x^3y^8} {TEX} را در عبارت{TEX()} {(3x+4y)^{11}} {TEX} بیابید.

__حل__

__الف.__طبق ((قضیه ی دو جمله ای نیوتن)) ضریب{TEX()} {x^2y^5} {TEX} در{TEX()} {(x+y)^7} {TEX} برابر است با{TEX()} {{7\choose 5 }=21} {TEX}.

__ب.__فرض کنید{TEX()} { A = 3x } {TEX} و {TEX()} { B = 4y } {TEX}. تنها جمله ای که شامل{TEX()} {x^3y^8} {TEX} می باشد، جمله ی{TEX()} {A^3B^8} {TEX} در عبارت{TEX()} {(A+B)^{11}} {TEX} است. بنابراین ابتدا ضریب{TEX()} {A^3B^8} {TEX} را به دست می آرویم. می دانیم ضریب{TEX()} {A^3B^8} {TEX} در عبارت{TEX()} {(A+B)^{11}} {TEX} برار است با{TEX()} {{11}\choose 8} {TEX}. بنابراین ضریب{TEX()} {x^3y^8} {TEX} در عبارت{TEX()} {(3x+4y)^{11}} {TEX} برابر است با{TEX()} {{{11}\choose 8 }\times 3^3 \times 4^8} {TEX}.

دقت کنید که چون ضریب {TEX()} {x} {TEX}و {TEX()} {y} {TEX}به ترتیب برابر 3 و 8 بود، ضریب{TEX()} {A^3B^8} {TEX} ضرب در{TEX()} {3^3 \times 4^8} {TEX} شد.

---

!!مثال

تساوی های زیر را ثابت کنید:

__الف.__@@{TEX()} {\sum_{k=0}^n {n\choose k}={n\choose 0}+{n\choose 1}+{n\choose 2}+\cdots +{n\choose n}=2^n} {TEX}@@

__ب.__@@{TEX()} {\sum_{k=0}^n (-1)^k {n\choose k}={n\choose 0}-{n\choose 1}+{n\choose 2}-\cdots +(-1)^n {n\choose n}=0} {TEX}@@

__ج.__ @@ {TEX()} {{n\choose 0}+{n\choose 2}+\cdots +{n\choose{2k}}+\cdots ={n\choose 1}+{n\choose 3}+\cdots +{n\choose{2k+1}}+\cdots =2^{n-1}} {TEX} @@

__حل __

__الف. روش اول__ اگر در قضیه ی دو جمله ای نیوتن قرار دهید{TEX()} { x = y = 1} {TEX}، حکم ثابت می شد.

__روش دوم.__ طرف چپ، تعداد ((زیر مجموعه)) های یک مجموعه ی {TEX()} {n} {TEX}عضوی است زیرا همان طور که می دانیم تعداد زیر مجموعه های {TEX()} {k} {TEX}عضوی{TEX()} {(0 \le k \le n)} {TEX} مجموعه {TEX()} {n} {TEX}عضوی برابر است با{TEX()} {n\choose k} {TEX}. پس تعداد زیر مجموعه های یک مجموعه ی {TEX()} {n} {TEX}عضوی برابر است با{TEX()} {\sum_{k=0}^n {n\choose k}} {TEX}. از طرف دیگر همان طور که در بخش تناظر یک به یک دیدیم تعداد زیر مجموعه های یک ((مجموعه)) ی {TEX()} {n} {TEX}عضوی برابر است با تعداد دنباله های دودویی به طول {TEX()} {n} {TEX}، یعنی برابر است با{TEX()} {2^n} {TEX}. پس حکم ثابت شد.

__ب__. اگر در قضیه ی دوجمله ای نیوتن قرار دهید{TEX()} { x = 1 } {TEX}و{TEX()} { y = -1} {TEX} ، حکم ثابت می شود.

__ج. روش اول__. با استفاده از الف و ب، حکم قسمت ج اثبات می شود.

__روش دوم__. می دانیم{TEX()} {\Bigg( {n\choose 1}+{n\choose 3}+\cdots +{n\choose{2k+1}}+\cdots \Bigg) \quad {n\choose 0}+{n\choose 2}+\cdots {n\choose {2k}}} {TEX} برابر با تعداد زیر مجموعه های زوج عضوی (فرد عضوی) یک مجموعه ی {TEX()} {n} {TEX}عضوی است. حال با تناظر یک به یک برقرار کردن بین تعداد زیر مجموعه های فرد عضوی و زوج عضوی یک مجموعه ی {TEX()} {n} {TEX}عضوی تساوی

@@{TEX()} {{n\choose 0}+{n\choose 2}+\cdots +{n\choose{2k}}+\cdots ={n\choose 1}+{n\choose 3}+\cdots +{n\choose{2k+1}}+\cdots } {TEX}@@

را ثابت می کنیم.

فرض کنید {TEX()} {(O) \ E} {TEX}مجموعه ی تمام زیر مجموعه های زوج عضوی (فرد عضوی) مجموعه ی{TEX()} { S = \{1, 2, \cdots , n \} } {TEX} باشد. همچنین فرض کنید {TEX()} { (B) A } {TEX} مجموعه ی تمام زیر مجموعه های {TEX()} {S} {TEX}باشد که شامل عنصر {TEX()} {n} {TEX}می باشد (نمی باشد). حال ثابت می کنیم یک تناظر یک به یک بین{TEX()} {E\cap B} {TEX} و{TEX()} {O\cap A} {TEX} و همچنین یک تناظر یک به یک بین{TEX()} {o\cap B} {TEX} و{TEX()} {E\cap A} {TEX} وجود دارد.

با اضافه کردن {TEX()} {n} {TEX}به هر یک از اعضای{TEX()} {(O\cap B) E\cap B} {TEX}، به یک عضو از اعضای{TEX()} {(E\cap A)O\cap A} {TEX} می رسیم و بالعکس با حذف {TEX()} {n} {TEX}از هر یک از اعضای{TEX()} {(E\cap A)O\cap A} {TEX}، به یک عضو از اعضای{TEX()} {(O\cap B)E\cap B} {TEX} می رسیم. به راحتی می توان ثابت کرد که رابطه ی فوق یک ((تناظر یک به یک)) است. در نتیجه:

@@{TEX()} {|O\cap A|=|E\cap B| \quad , \quad |O\cap B|=|E\cap A| \ \Rightarrow |O\cap A|+|O\cap B|=|E\cap B|+|E\cap A| \ \Rightarrow |O|=|E| } {TEX}@@

از طرف دیگر می دانیم{TEX()} {|O|+|E|=|P(S)|=2^n} {TEX}، پس{TEX()} {|E|=|O|=2^{n-1}} {TEX}.

---

!!مثال

تساوی های ترکیبیاتی زیر را ثابت کنید:

__الف__ @@{TEX()} {\sum_{k=1}^n k{n\choose k}={n\choose 1}+2{n\choose 2}+\cdots +n {n\choose n}=n2^{n-1}} {TEX}@@

__ب.__ @@ {TEX()} {\sum_{m=k}^n {m\choose k}(n)={k\choose k}{n\choose k}+{{k+1}\choose k}{n\choose {k+1}}+\cdots +{n\choose n}{n\choose n}=2^{n-k}{n\choose k}} {TEX}@@

__حل. __

__الف. روش اول__. با در نظر گرفتن در قضیه ی دو جمله ای نیوتن داریم: {TEX()} { x = 1} {TEX}

@@{TEX()} {(1+y)^n=\sum_{k=0}^n {n\choose k}y^k} {TEX}@@

حال با مشتق گیری از طرفین نسبت به {TEX()} {y} {TEX}به دست می آید:

@@{TEX()} {n(1+y)^{n-1}=\sum_{k=1}^{n} k{n\choose k}y^{k-1}} {TEX}@@

حال با قرار دادن {TEX()} {y=1} {TEX} در تساوی فوق، خواهیم داشت:

@@{TEX()} {\sum_{k=1}^n k{n\choose k}=n2^{n-1}} {TEX}@@

__روش دوم__. می دانیم{TEX()} {k{n\choose k}=n{{n-1}\choose{k-1}}} {TEX}. در نتیجه داریم:

@@{TEX()} {\sum_{k=1}^n k{n\choose k}=\sum_{k=1}^n n{{n-1}\choose {k-1}}=n\sum_{k=1}^n {{n-1}\choose {k-1}}=n\sum_{l=0}^{n-1}{{n-1}\choose l}=n2^{n-1}} {TEX}@@

__ب.__ می دانیم{TEX()} {{m\choose k}{n\choose m}={n\choose k}{{n-k}\choose {m-k}}} {TEX}. در نتیجه داریم:

@@{TEX()} {\sum_{m=k}^n {m\choose k}{n\choose m}=\sum_{m=k}^n {n\choose k}{{n-k}\choose {m-k}}={n\choose k} \sum_{m=k}^n {{n-k}\choose {m-k}}={n\choose k}2^{n-m} {TEX}@@

---

! پیوند های خارجی

[http://Olympiad.roshd.ir/computer/content/pdf/0054.pdf]

!همچنین ببینید

*((نظریه چند جمله ای ها ))

#@^