تاریخچه ی:
تعمیم
تفاوت با نگارش: 1
| ||V{maketoc}|| | | ||V{maketoc}|| |
- | ||__~~navy:@#13::: این مطلب از بخش آموزش وبسایت المپیاد یی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وبسایت المپیاد رشد]موجود میباشد. برای مشاهده این موضوعات در وبسایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین میتوانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا)) ، با ویژگیهای بخش آموزش این وبسایت آشنا شوید.:: #@~~__|| |
+ | ||__~~navy:@#13::: این مطلب از بخش آموزش وبسایت المپیاد کمپیو رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وبسایت المپیاد رشد]موجود میباشد. برای مشاهده این موضوعات در وبسایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین میتوانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا)) ، با ویژگیهای بخش آموزش این وبسایت آشنا شوید.:: #@~~__|| |
| ^@#16: | | ^@#16: |
| !رابطه (2) تعمیم اصل شمول و عدم شمول | | !رابطه (2) تعمیم اصل شمول و عدم شمول |
| در قسمت قبل یاد گرفتیم که چگونه از اصل شمول و عدم شمول برای تعیین تعداد اعضای {TEX()} {N(\overline {c_1} \ \overline {c_2} \cdots \overline {c_p} )} {TEX}، یعنی تعداد عنصرهایی از {TEX()} {S} {TEX}که در هیچ یک از{TEX()} { p } {TEX} شرط {TEX()} {c_p , \cdots , c_2,c_1} {TEX}صدق نمی کنند، استفاده کنیم. حال فرض کنید {TEX()} {E_m} {TEX} تعداد عنصرهایی از {TEX()} {S} {TEX}باشد که در دقیقا {TEX()} {m} {TEX}شرط از {TEX()} {p} {TEX}شرط صدق می کنند. می خواهیم فرمولی برای محاسبه {TEX()} {E_m} {TEX} بیابیم. | | در قسمت قبل یاد گرفتیم که چگونه از اصل شمول و عدم شمول برای تعیین تعداد اعضای {TEX()} {N(\overline {c_1} \ \overline {c_2} \cdots \overline {c_p} )} {TEX}، یعنی تعداد عنصرهایی از {TEX()} {S} {TEX}که در هیچ یک از{TEX()} { p } {TEX} شرط {TEX()} {c_p , \cdots , c_2,c_1} {TEX}صدق نمی کنند، استفاده کنیم. حال فرض کنید {TEX()} {E_m} {TEX} تعداد عنصرهایی از {TEX()} {S} {TEX}باشد که در دقیقا {TEX()} {m} {TEX}شرط از {TEX()} {p} {TEX}شرط صدق می کنند. می خواهیم فرمولی برای محاسبه {TEX()} {E_m} {TEX} بیابیم. |
| --- | | --- |
| !قضیه 1 | | !قضیه 1 |
- | فرض کنید {TEX()} {S} {TEX}مجموعه ای از اشیا و {TEX()} {(i \le i \le p)} {TEX} شرایطی روی اعضای {TEX()} {S} {TEX}باشند، {TEX()} {E_m} {TEX} (تعداد عضوهایی از {TEX()} {S} {TEX}که در دقیقا {TEX()} {m} {TEX}تا از این شرایط صدق می کنند.) برابر است با: |
+ | فرض کنید {TEX()} {S} {TEX}((مجموعه)) ای از اشیا و {TEX()} {(i \le i \le p)} {TEX} شرایطی روی اعضای {TEX()} {S} {TEX}باشند، {TEX()} {E_m} {TEX} (تعداد عضوهایی از {TEX()} {S} {TEX}که در دقیقا {TEX()} {m} {TEX}تا از این شرایط صدق می کنند.) برابر است با: |
| @@{TEX()} {E_m=S_m –{{m+1}\choose 1}S_{m+1}+{{m+2}\choose 2}S_{m+2} - \cdots + (-1)^{p-m} {p \choose {p-m}}S_p} {TEX}@@ | | @@{TEX()} {E_m=S_m –{{m+1}\choose 1}S_{m+1}+{{m+2}\choose 2}S_{m+2} - \cdots + (-1)^{p-m} {p \choose {p-m}}S_p} {TEX}@@ |
| __اثبات.__ | | __اثبات.__ |
| فرض کنید {TEX()} {x\in S} {TEX}، سه حالت زیر را در نظر می گیریم: | | فرض کنید {TEX()} {x\in S} {TEX}، سه حالت زیر را در نظر می گیریم: |
| •وقتی که {TEX()} {x} {TEX}در کمتر از {TEX()} {m} {TEX}شرط صدق کند. در این حالت سهم {TEX()} {x} {TEX}در محاسبه هر یک از جملات {TEX()} {S_p , \cdots , S_{m+1},S_m ,E_m} {TEX} برابر 0 است و بنابراین، در هیچ یک از طرفین معادله شمرده نمی شود. | | •وقتی که {TEX()} {x} {TEX}در کمتر از {TEX()} {m} {TEX}شرط صدق کند. در این حالت سهم {TEX()} {x} {TEX}در محاسبه هر یک از جملات {TEX()} {S_p , \cdots , S_{m+1},S_m ,E_m} {TEX} برابر 0 است و بنابراین، در هیچ یک از طرفین معادله شمرده نمی شود. |
| •وقتی که {TEX()} {x} {TEX}در دقیقا {TEX()} {m} {TEX}شرط صدق کند. در این حالت {TEX()} {x} {TEX}یکبار در {TEX()} {E_m} {TEX} و یکبار در {TEX()} {S_m} {TEX} شمرده می شود ولی در جملات {TEX()} {S_p , \cdots , S_{m+2} , S_{m+1}} {TEX} شمرده نمی شود. درنتیجه {TEX()} {x} {TEX}در هر یک از طرفین معادله بالا یکبار شمرده می شود. | | •وقتی که {TEX()} {x} {TEX}در دقیقا {TEX()} {m} {TEX}شرط صدق کند. در این حالت {TEX()} {x} {TEX}یکبار در {TEX()} {E_m} {TEX} و یکبار در {TEX()} {S_m} {TEX} شمرده می شود ولی در جملات {TEX()} {S_p , \cdots , S_{m+2} , S_{m+1}} {TEX} شمرده نمی شود. درنتیجه {TEX()} {x} {TEX}در هر یک از طرفین معادله بالا یکبار شمرده می شود. |
| •وقتی که {TEX()} {x} {TEX}در شرط ({TEX()} {m<q \le p} {TEX}) صدق کند. در این حالت {TEX()} {x} {TEX}در {TEX()} {E_m} {TEX} شمرده نمی شود. ولی {TEX()} {q \choose m } {TEX} بار در {TEX()} {S_m} {TEX}، {TEX()} {{q \choose {m+1}}} {TEX} بار در {TEX()} {S_{m+1}} {TEX}، ... و {TEX()} {q \choose p} {TEX} بار در {TEX()} {S_q} {TEX} شمرده می شود، ولی در هیچ یک از جملات {TEX()} {S_p , \cdots , S_{q+2} , S_{q+1}} {TEX} شمرده نمی شود. پس {TEX()} {x} {TEX}در طرف راست معادله، | | •وقتی که {TEX()} {x} {TEX}در شرط ({TEX()} {m<q \le p} {TEX}) صدق کند. در این حالت {TEX()} {x} {TEX}در {TEX()} {E_m} {TEX} شمرده نمی شود. ولی {TEX()} {q \choose m } {TEX} بار در {TEX()} {S_m} {TEX}، {TEX()} {{q \choose {m+1}}} {TEX} بار در {TEX()} {S_{m+1}} {TEX}، ... و {TEX()} {q \choose p} {TEX} بار در {TEX()} {S_q} {TEX} شمرده می شود، ولی در هیچ یک از جملات {TEX()} {S_p , \cdots , S_{q+2} , S_{q+1}} {TEX} شمرده نمی شود. پس {TEX()} {x} {TEX}در طرف راست معادله، |
| @@{TEX()} {{q \choose m}-{{m+1}\choose 1}{q \choose {m+1}}+{{m+2}\choose 2}{q\choose {m+2}}- \cdots +(-1)^{q-m} {q\choose {q-m}}{q \choose p}} {TEX}@@ | | @@{TEX()} {{q \choose m}-{{m+1}\choose 1}{q \choose {m+1}}+{{m+2}\choose 2}{q\choose {m+2}}- \cdots +(-1)^{q-m} {q\choose {q-m}}{q \choose p}} {TEX}@@ |
| بار به حساب می آید. از طرفی می دانیم | | بار به حساب می آید. از طرفی می دانیم |
| @@{TEX()} {{{m+k}\choose k}{q \choose {m+k}}={q\choose m}{{q-m}\choose k}} {TEX}.@@ | | @@{TEX()} {{{m+k}\choose k}{q \choose {m+k}}={q\choose m}{{q-m}\choose k}} {TEX}.@@ |
| بنابراین {TEX()} {x} {TEX}در طرف راست معادله، | | بنابراین {TEX()} {x} {TEX}در طرف راست معادله، |
| @@{TEX()} {{q\choose m}{{q-m}\choose 0}-{q \choose m}{{q-m}\choose 1}+{q \choose m}{{q-m}\choose 2}- \cdots +(-1)^{q-m}{q \choose m}{{q-m}\choose {q-m}}} {TEX}@@ | | @@{TEX()} {{q\choose m}{{q-m}\choose 0}-{q \choose m}{{q-m}\choose 1}+{q \choose m}{{q-m}\choose 2}- \cdots +(-1)^{q-m}{q \choose m}{{q-m}\choose {q-m}}} {TEX}@@ |
| @@{TEX()} {{={q \choose m}\Big[ {{q-m}\choose 0}-{{q-m} \choose 1}+{{q-m} \choose 2}+\cdots + (-1)^{q-m}{{q-m}\choose {q-m}} \Big]}} {TEX}@@ | | @@{TEX()} {{={q \choose m}\Big[ {{q-m}\choose 0}-{{q-m} \choose 1}+{{q-m} \choose 2}+\cdots + (-1)^{q-m}{{q-m}\choose {q-m}} \Big]}} {TEX}@@ |
| @@{TEX()} {={q\choose m } [1+(-1)]\times (q-m)=0} {TEX}@@ | | @@{TEX()} {={q\choose m } [1+(-1)]\times (q-m)=0} {TEX}@@ |
| بار به حساب آمده است. | | بار به حساب آمده است. |
| پس {TEX()} {x} {TEX}در هر دو طرف تساوی به یک اندازه سهم دارد. درنتیجه حکم ثابت شد. | | پس {TEX()} {x} {TEX}در هر دو طرف تساوی به یک اندازه سهم دارد. درنتیجه حکم ثابت شد. |
| --- | | --- |
| !قضیه 2 | | !قضیه 2 |
| فرض کنید {TEX()} {L_m} {TEX} تعداد عنصرهایی از {TEX()} {S} {TEX}باشد که در حداقل {TEX()} {m} {TEX}شرط از {TEX()} {p} {TEX}شرط مفروض صدق می کنند، در این صورت داریم: | | فرض کنید {TEX()} {L_m} {TEX} تعداد عنصرهایی از {TEX()} {S} {TEX}باشد که در حداقل {TEX()} {m} {TEX}شرط از {TEX()} {p} {TEX}شرط مفروض صدق می کنند، در این صورت داریم: |
| @@{TEX()} {L_m=S_m-{m\choose {m-1}}S_{m+1}+{{m+1}\choose {m-1}}S_{m+2} - \cdots +(-1)^{p-m} {{p-1}\choose {m-1}}S_p} {TEX}@@ | | @@{TEX()} {L_m=S_m-{m\choose {m-1}}S_{m+1}+{{m+1}\choose {m-1}}S_{m+2} - \cdots +(-1)^{p-m} {{p-1}\choose {m-1}}S_p} {TEX}@@ |
| __اثبات__. | | __اثبات__. |
| اثبات به عنوان تمرین به عهده خواننده. | | اثبات به عنوان تمرین به عهده خواننده. |
| --- | | --- |
| !!مثال | | !!مثال |
| تعداد اعضای{TEX()} { S = \{1, 2, \cdots , 1000 \} } {TEX}را بیابید که: | | تعداد اعضای{TEX()} { S = \{1, 2, \cdots , 1000 \} } {TEX}را بیابید که: |
| __الف.__بر هیچ کدام از اعداد 2، 3 و 5 بخش پذیر نباشند. | | __الف.__بر هیچ کدام از اعداد 2، 3 و 5 بخش پذیر نباشند. |
| __ب.__دقیقاً بر یکی از اعداد 2، 3 و 5 بخش پذیر باشند. | | __ب.__دقیقاً بر یکی از اعداد 2، 3 و 5 بخش پذیر باشند. |
| __ج.__ دقیقاً بر دو تا از اعداد 2، 3 و 5 بخش پذیر باشند. | | __ج.__ دقیقاً بر دو تا از اعداد 2، 3 و 5 بخش پذیر باشند. |
| __د. __بر تمام اعداد 2، 3 و 5 بخش پذیر باشند. | | __د. __بر تمام اعداد 2، 3 و 5 بخش پذیر باشند. |
| __حل.__ | | __حل.__ |
| فرض کنید{TEX()} {c_i} {TEX} شرط بخش پذیری اعضای {TEX()} {S} {TEX}بر {TEX()} {(i=2,3,5) ,i} {TEX} باشد. قسمت الف تا د به ترتیب مقدار{TEX()} {E_3,E_2,E_1,E_0} {TEX}را می خواهند. در مثال های قبل دیدیم که | | فرض کنید{TEX()} {c_i} {TEX} شرط بخش پذیری اعضای {TEX()} {S} {TEX}بر {TEX()} {(i=2,3,5) ,i} {TEX} باشد. قسمت الف تا د به ترتیب مقدار{TEX()} {E_3,E_2,E_1,E_0} {TEX}را می خواهند. در مثال های قبل دیدیم که |
| @@{TEX()} {N(c_2)=500 \qquad N(c_3)=333 \qquad N(c_5)=200} {TEX}@@ | | @@{TEX()} {N(c_2)=500 \qquad N(c_3)=333 \qquad N(c_5)=200} {TEX}@@ |
| @@{TEX()} {N(c_2c_3)=166 \quad N(c_2c_5)=100 \quad N(c_3c_5)=66} {TEX}@@ | | @@{TEX()} {N(c_2c_3)=166 \quad N(c_2c_5)=100 \quad N(c_3c_5)=66} {TEX}@@ |
| @@{TEX()} {N(c_2c_3c_5)=33} {TEX}@@ | | @@{TEX()} {N(c_2c_3c_5)=33} {TEX}@@ |
| در نتیجه داریم: | | در نتیجه داریم: |
| @@{TEX()} {s_0=1000} {TEX}@@ | | @@{TEX()} {s_0=1000} {TEX}@@ |
| @@{TEX()} {S_1=500+333+200=1033} {TEX}@@ | | @@{TEX()} {S_1=500+333+200=1033} {TEX}@@ |
| @@{TEX()} {S_2=166+100+66=322} {TEX}@@ | | @@{TEX()} {S_2=166+100+66=322} {TEX}@@ |
| @@{TEX()} {S_3=333} {TEX}@@ | | @@{TEX()} {S_3=333} {TEX}@@ |
| 1.@@{TEX()} {E_0=S_0-S_1+S_2-S_3=266} {TEX}@@ | | 1.@@{TEX()} {E_0=S_0-S_1+S_2-S_3=266} {TEX}@@ |
| 2.@@{TEX()} {E_1=S_1-2S_2+3S_3=468} {TEX}@@ | | 2.@@{TEX()} {E_1=S_1-2S_2+3S_3=468} {TEX}@@ |
| 3.@@{TEX()} {E_2=S_2-{3 \choose 1 }S_3=233} {TEX}@@ | | 3.@@{TEX()} {E_2=S_2-{3 \choose 1 }S_3=233} {TEX}@@ |
| 4.@@{TEX()} {E_3=S_3=33} {TEX}@@ | | 4.@@{TEX()} {E_3=S_3=33} {TEX}@@ |
| --- | | --- |
| !!مثال | | !!مثال |
| یک منشی {TEX()} {n} {TEX}نامه و آدرس های مربوط به هر یک را روی {TEX()} {n} {TEX}پاکت تایپ کرده است و هر نامه را در یک پاکت قرار می دهد. این منشی به چند طریق می تواند هیچ نامه ای را در پاکت مربوط به خودش قرار ندهد؟ | | یک منشی {TEX()} {n} {TEX}نامه و آدرس های مربوط به هر یک را روی {TEX()} {n} {TEX}پاکت تایپ کرده است و هر نامه را در یک پاکت قرار می دهد. این منشی به چند طریق می تواند هیچ نامه ای را در پاکت مربوط به خودش قرار ندهد؟ |
| __حل.__ | | __حل.__ |
- | نامه ها و پاکت های آن ها را به ترتیب با شماره های 1 تا {TEX()} {n} {TEX}شماره گذاری می کنیم. بنابراین نامه ی شماره ی {TEX()} {i} {TEX}مربوط به پاکت شماره ی {TEX()} {i} {TEX}می باشد. فرض کنید در پاکت شماره ی {TEX()} {i} {TEX}، نامه ی شماره ی{TEX()} {P_i} {TEX} قرار بگیرد. پس ما تعداد جایگشت های 1 تا {TEX()} {n} {TEX}را می خواهیم که به ازای هر{TEX()} {P_i \neq i \ , \ 1 \le i \le n} {TEX}،{TEX()} {P_i \neq i} {TEX}. حال می گوییک جایگشت {TEX()} {P} {TEX}دارای شرط{TEX()} {c_i} {TEX} می باشد اگر{TEX()} {P_i=i} {TEX} باشد. واضح است که |
+ | نامه ها و پاکت های آن ها را به ترتیب با شماره های 1 تا {TEX()} {n} {TEX}شماره گذاری می کنیم. بنابراین نامه ی شماره ی {TEX()} {i} {TEX}مربوط به پاکت شماره ی {TEX()} {i} {TEX}می باشد. فرض کنید در پاکت شماره ی {TEX()} {i} {TEX}، نامه ی شماره ی{TEX()} {P_i} {TEX} قرار بگیرد. پس ما تعداد جایگشت های 1 تا {TEX()} {n} {TEX}را می خواهیم که به ازای هر{TEX()} {P_i \neq i \ , \ 1 \le i \le n} {TEX}،{TEX()} {P_i \neq i} {TEX}. حال می گوییک ((جایگشت)) {TEX()} {P} {TEX}دارای شرط{TEX()} {c_i} {TEX} می باشد اگر{TEX()} {P_i=i} {TEX} باشد. واضح است که |
| @@{TEX()} {N(c_i)=(n-1)!} {TEX}@@ | | @@{TEX()} {N(c_i)=(n-1)!} {TEX}@@ |
| @@{TEX()} {N(c_ic_j)=(n-2)!} {TEX}@@ | | @@{TEX()} {N(c_ic_j)=(n-2)!} {TEX}@@ |
| @@{TEX()} {\vdots} {TEX}@@ | | @@{TEX()} {\vdots} {TEX}@@ |
| @@{TEX()} {N(c_{i_1} c_{i_2} \cdots c_{i_k})} {TEX}@@ | | @@{TEX()} {N(c_{i_1} c_{i_2} \cdots c_{i_k})} {TEX}@@ |
| پس | | پس |
| @@{TEX()} {S_0=n! - n \times (n-1)!+ {n \choose 2} (n-2)! -\cdots (-1)^n {n\choose n} } {TEX}@@ | | @@{TEX()} {S_0=n! - n \times (n-1)!+ {n \choose 2} (n-2)! -\cdots (-1)^n {n\choose n} } {TEX}@@ |
| و با فاکتور گیری از{TEX()} { n! } {TEX}داریم: | | و با فاکتور گیری از{TEX()} { n! } {TEX}داریم: |
- | رابطه (2) @@{TEX()} {D_n=n! \Big( 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!} +\cdots (-1)^n \frac{1}{n!} \Big)} {TEX} @@ به هر جایگشت از اعداد 1 تا {TEX()} {n} {TEX}که هیچ عددی در جای خودش قرار نگیرد یک پریش از اعداد 1 تا {TEX()} {n} {TEX}می گوییم. با استفاده از رابطه ی 1 می توانید ثابت کنید به ازای {TEX()} {n} {TEX}های بزرگ: {TEX()} {\frac{D_n}{n!} \cong \frac{1}{e}} {TEX}. |
+ | رابطه (2)@@{TEX()} {D_n=n! \Big( 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!} +\cdots (-1)^n \frac{1}{n!} \Big)} {TEX} @@ به هر ((جایگشت)) از اعداد 1 تا {TEX()} {n} {TEX}که هیچ عددی در جای خودش قرار نگیرد یک پریش از اعداد 1 تا {TEX()} {n} {TEX}می گوییم. با استفاده از رابطه ی 1 می توانید ثابت کنید به ازای {TEX()} {n} {TEX}های بزرگ: {TEX()} {\frac{D_n}{n!} \cong \frac{1}{e}} {TEX}. |
| #@ | | #@ |
| @#16: | | @#16: |
| --- | | --- |
| !!مثال | | !!مثال |
| فرض کنید{TEX()} {B_n= \{1,2,\cdots ,n \}} {TEX} و{TEX()} {B_m=\{1,2, \cdots , m \}} {TEX}. تعداد توابع پوشای{TEX()} {f:B_n \rightarrow B_m} {TEX} را بیابید. | | فرض کنید{TEX()} {B_n= \{1,2,\cdots ,n \}} {TEX} و{TEX()} {B_m=\{1,2, \cdots , m \}} {TEX}. تعداد توابع پوشای{TEX()} {f:B_n \rightarrow B_m} {TEX} را بیابید. |
| __حل__ | | __حل__ |
| می گوییم تابع{TEX()} {f:B_n \rightarrow B_m} {TEX} دارای شرط{TEX()} {c_i} {TEX} است{TEX()} { (i = 1, \cdots , m)} {TEX} اگر برد تابع {TEX()} {f} {TEX}شامل {TEX()} {i} {TEX}نباشد. در این صورت به وضوح داریم: | | می گوییم تابع{TEX()} {f:B_n \rightarrow B_m} {TEX} دارای شرط{TEX()} {c_i} {TEX} است{TEX()} { (i = 1, \cdots , m)} {TEX} اگر برد تابع {TEX()} {f} {TEX}شامل {TEX()} {i} {TEX}نباشد. در این صورت به وضوح داریم: |
| @@{TEX()} {S_k={m \choose k} (m-k)^n} {TEX}@@ | | @@{TEX()} {S_k={m \choose k} (m-k)^n} {TEX}@@ |
- | بنابراین طبق اصل شمول و عدم شمول تعداد توابع پوشا از{TEX()} {B_n} {TEX} به{TEX()} {B_m} {TEX} برابر است با |
+ | بنابراین طبق اصل شمول و عدم شمول تعداد توابع ((پوشا)) از{TEX()} {B_n} {TEX} به{TEX()} {B_m} {TEX} برابر است با |
| @@{TEX()} {\sum_{k=0}^m (-1)^k S_k = \sum_{k=0}^m (-1)^k {m\choose k} (m-k)^n} {TEX}@@ | | @@{TEX()} {\sum_{k=0}^m (-1)^k S_k = \sum_{k=0}^m (-1)^k {m\choose k} (m-k)^n} {TEX}@@ |
| @@{TEX()} {={m\choose 0 }m^n –{m\choose 1}(m-1)^n+{m\choose 2}(m-2)^n - \cdots +(-1)^{m-1} {m\choose {m-1}}} {TEX}@@ | | @@{TEX()} {={m\choose 0 }m^n –{m\choose 1}(m-1)^n+{m\choose 2}(m-2)^n - \cdots +(-1)^{m-1} {m\choose {m-1}}} {TEX}@@ |
| --- | | --- |
| !!مثال | | !!مثال |
| جایگشت{TEX()} {x_1x_2 \cdots x_{2n-1}x_{2n}} {TEX} از مجموعه ی{TEX()} {S=\{1,2,\cdots , 2n-1 ,2n \}} {TEX} را در نظر بگیرید. این جایگشت دارای خاصیت {TEX()} {P} {TEX}است اگر به ازای حداقل یک{TEX()} {1 \le i \le 2n-1} {TEX} داشته باشیم{TEX()} {|x_i-x_{i+1}|=n} {TEX}. ثابت کنید به ازای هر {TEX()} {n} {TEX}، تعداد جایگشت های دارای خاصیت {TEX()} {P} {TEX}از تعداد جایگشت هایی که این خاصیت را ندارند بیشتر است. | | جایگشت{TEX()} {x_1x_2 \cdots x_{2n-1}x_{2n}} {TEX} از مجموعه ی{TEX()} {S=\{1,2,\cdots , 2n-1 ,2n \}} {TEX} را در نظر بگیرید. این جایگشت دارای خاصیت {TEX()} {P} {TEX}است اگر به ازای حداقل یک{TEX()} {1 \le i \le 2n-1} {TEX} داشته باشیم{TEX()} {|x_i-x_{i+1}|=n} {TEX}. ثابت کنید به ازای هر {TEX()} {n} {TEX}، تعداد جایگشت های دارای خاصیت {TEX()} {P} {TEX}از تعداد جایگشت هایی که این خاصیت را ندارند بیشتر است. |
| __حل.__ | | __حل.__ |
- | قبلا، این مساله را با استفاده از تناظر یک به یک حل کردیم. در این فصل قصد داریم با استفاده از اصل شمول و عدم شمول راه حل دیگری برای مساله بیابیم. |
+ | قبلا، این مساله را با استفاده از ((تناظر یک به یک)) حل کردیم. در این فصل قصد داریم با استفاده از اصل شمول و عدم شمول راه حل دیگری برای مساله بیابیم. |
| فرض کنید{TEX()} {(k \in \{1,2,\cdots ,n \} ) \ A_k} {TEX} مجموعه ی همه ی جایگشت های مجموعه ی {TEX()} {S} {TEX}باشد که در آنها زوج متناظر {TEX()} {k} {TEX}و {TEX()} { n + k } {TEX} متوالی هستند. پس{TEX()} {A= \bigcup_{k=1}^n A_k} {TEX}، مجموعه ی همه ی جایگشت های مجموعه {TEX()} {S} {TEX}است که دارای خاصیت {TEX()} {P} {TEX}می باشند. طبق اصل شمول و عدم شمول | | فرض کنید{TEX()} {(k \in \{1,2,\cdots ,n \} ) \ A_k} {TEX} مجموعه ی همه ی جایگشت های مجموعه ی {TEX()} {S} {TEX}باشد که در آنها زوج متناظر {TEX()} {k} {TEX}و {TEX()} { n + k } {TEX} متوالی هستند. پس{TEX()} {A= \bigcup_{k=1}^n A_k} {TEX}، مجموعه ی همه ی جایگشت های مجموعه {TEX()} {S} {TEX}است که دارای خاصیت {TEX()} {P} {TEX}می باشند. طبق اصل شمول و عدم شمول |
| رابطه (2) @@{TEX()} {|A|= \sum_{k=1}^n |A_k|- \sum_{k< l \le n} |A_k \cap A_l|+ \sum_{k< l < m \le n} |A_k \cap A_l \cap A_m|- \cdots } {TEX}@@ | | رابطه (2) @@{TEX()} {|A|= \sum_{k=1}^n |A_k|- \sum_{k< l \le n} |A_k \cap A_l|+ \sum_{k< l < m \le n} |A_k \cap A_l \cap A_m|- \cdots } {TEX}@@ |
- | با توجه به این که این سری یک سری نزولی است، در نتیجه: |
+ | با توجه به این که این سری یک سری ((نزولی)) است، در نتیجه: |
| رابطه (2) @@{TEX()} {|A| \ge \sum_{k=1}^n |A_k|- \sum_{k< l \le n} |A_k \cap A_l| } {TEX}@@ | | رابطه (2) @@{TEX()} {|A| \ge \sum_{k=1}^n |A_k|- \sum_{k< l \le n} |A_k \cap A_l| } {TEX}@@ |
| می دانیم{TEX()} {|A_k|=2 \times (2n-1)!} {TEX} و{TEX()} {|A_k \cap A_l |=2^2 \times (2n-2)!} {TEX}. (چرا؟) در نتیجه | | می دانیم{TEX()} {|A_k|=2 \times (2n-1)!} {TEX} و{TEX()} {|A_k \cap A_l |=2^2 \times (2n-2)!} {TEX}. (چرا؟) در نتیجه |
| @@{TEX()} {|A| \ge 2n(2n-1)!-4 \times {n \choose 2} (2n-2)! \ge 2n^2 (2n-2)! > \frac{(2n)!}{2}} {TEX}@@ | | @@{TEX()} {|A| \ge 2n(2n-1)!-4 \times {n \choose 2} (2n-2)! \ge 2n^2 (2n-2)! > \frac{(2n)!}{2}} {TEX}@@ |
- | پس تعداد جایگشت های دارای خاصیت {TEX()} {P} {TEX}از نصف تعداد کل جایگشت های مجموعه ی {TEX()} {S} {TEX}بیشتر است. در نتیجه تعداد جایگشت های دارای خاصیت {TEX()} {P} {TEX}از تعداد جایگشت های بدون خاصیت {TEX()} {P} {TEX}بیشتر است. با استفاده از کل سری می توانید ثابت کنید به ازای {TEX()} {n} {TEX}های بزرگ،{TEX()} {\frac{|A|}{(2n!)} \cong 1-e^{-1} \cong 0.632} {TEX} |
+ | پس تعداد جایگشت های دارای خاصیت {TEX()} {P} {TEX}از نصف تعداد کل ((جایگشت)) های مجموعه ی {TEX()} {S} {TEX}بیشتر است. در نتیجه تعداد جایگشت های دارای خاصیت {TEX()} {P} {TEX}از تعداد جایگشت های بدون خاصیت {TEX()} {P} {TEX}بیشتر است. با استفاده از کل ((سری)) می توانید ثابت کنید به ازای {TEX()} {n} {TEX}های بزرگ،{TEX()} {\frac{|A|}{(2n!)} \cong 1-e^{-1} \cong 0.632} {TEX} |
| --- | | --- |
| !!مثال | | !!مثال |
| تعداد زیر مجموعه های {TEX()} {k} {TEX}عضوی{TEX()} { \{1, 2, \cdots , n\} } {TEX}را بیابید که شامل هیچ دو عضو متوالی دوری نباشند. (عدد{TEX()} {1 < i < n } {TEX} با اعداد {TEX()} { i – 1} {TEX} و {TEX()} { i + 1 } {TEX} متوالی دوری است. همچنین 1 و {TEX()} {n} {TEX}هم متوالی دوری حساب می شوند.) | | تعداد زیر مجموعه های {TEX()} {k} {TEX}عضوی{TEX()} { \{1, 2, \cdots , n\} } {TEX}را بیابید که شامل هیچ دو عضو متوالی دوری نباشند. (عدد{TEX()} {1 < i < n } {TEX} با اعداد {TEX()} { i – 1} {TEX} و {TEX()} { i + 1 } {TEX} متوالی دوری است. همچنین 1 و {TEX()} {n} {TEX}هم متوالی دوری حساب می شوند.) |
| __حل__ | | __حل__ |
| فرض کنید{TEX()} {{\alpha}_i} {TEX} برابر تعداد زیر مجموعه های مطلوب {TEX()} {k} {TEX}عضوی باشد که شامل {TEX()} {i} {TEX}می باشند. به دلیل تقارن {TEX()} {{\alpha}_1={\alpha}_2 = \cdots = {\alpha}_n} {TEX}. پس{TEX()} {{\alpha}_1} {TEX} را می شماریم. | | فرض کنید{TEX()} {{\alpha}_i} {TEX} برابر تعداد زیر مجموعه های مطلوب {TEX()} {k} {TEX}عضوی باشد که شامل {TEX()} {i} {TEX}می باشند. به دلیل تقارن {TEX()} {{\alpha}_1={\alpha}_2 = \cdots = {\alpha}_n} {TEX}. پس{TEX()} {{\alpha}_1} {TEX} را می شماریم. |
- | اگر {TEX()} {B} {TEX}یک زیر مجموعه ی مطلوب {TEX()} {k} {TEX}عضوی باشد که دارای عنصر”1“ است، طبق فرض مسا له{TEX()} {2,n \notin B} {TEX}. حال باید{TEX()} { k – 1 } {TEX}عضو باقی مانده را بررسی کنیم .می دانیم تعداد این زیر مجموعه ها برابر است با تعداد زیر مجموعه های{TEX()} { k – 1 } {TEX} عضوی یک مجموعه ی{TEX()} { n – k -1 } {TEX}عضوی. در نتیجه |
+ | اگر {TEX()} {B} {TEX}یک زیر مجموعه ی مطلوب {TEX()} {k} {TEX}عضوی باشد که دارای عنصر”1“ است، طبق فرض مسا له{TEX()} {2,n \notin B} {TEX}. حال باید{TEX()} { k – 1 } {TEX}عضو باقی مانده را بررسی کنیم .می دانیم تعداد این ((زیر مجموعه)) ها برابر است با تعداد زیر مجموعه های{TEX()} { k – 1 } {TEX} عضوی یک مجموعه ی{TEX()} { n – k -1 } {TEX}عضوی. در نتیجه |
| @@{TEX()} {{\alpha}_1 = {{n-k-1}\choose {k-1}}} {TEX}.@@ | | @@{TEX()} {{\alpha}_1 = {{n-k-1}\choose {k-1}}} {TEX}.@@ |
| در نتیجه تعداد مجموعه های مطلوب {TEX()} {k} {TEX}عضوی برابر است با: | | در نتیجه تعداد مجموعه های مطلوب {TEX()} {k} {TEX}عضوی برابر است با: |
| @@{TEX()} {A_k=\frac{1}{k} \sum_{i=1}^n {\alpha}_i = \frac{n}{k} {\alpha}_1 =\frac{n}{k} {{n-k-1}\choose {k-1}}} {TEX}@@ | | @@{TEX()} {A_k=\frac{1}{k} \sum_{i=1}^n {\alpha}_i = \frac{n}{k} {\alpha}_1 =\frac{n}{k} {{n-k-1}\choose {k-1}}} {TEX}@@ |
| دقت کنید که چون هر مجموعه {TEX()} {k} {TEX}بار در عبارت{TEX()} {\sum_{i=1}^n {\alpha}_i} {TEX} شمرده شده است{TEX()} {A_k = \frac{1}{k} \sum_{i=1}^n {\alpha}_i} {TEX}. | | دقت کنید که چون هر مجموعه {TEX()} {k} {TEX}بار در عبارت{TEX()} {\sum_{i=1}^n {\alpha}_i} {TEX} شمرده شده است{TEX()} {A_k = \frac{1}{k} \sum_{i=1}^n {\alpha}_i} {TEX}. |
| --- | | --- |
| !!مثال | | !!مثال |
| به چند طریق {TEX()} {n} {TEX}زوج {TEX()} {(n > 1) } {TEX} می توانند دور یک میز گرد بنشینند به طوری که زن ها و مردها یک در میان بنشینند و هیچ مردی کنار همسر خود ننشسته باشد؟ | | به چند طریق {TEX()} {n} {TEX}زوج {TEX()} {(n > 1) } {TEX} می توانند دور یک میز گرد بنشینند به طوری که زن ها و مردها یک در میان بنشینند و هیچ مردی کنار همسر خود ننشسته باشد؟ |
| __حل.__ | | __حل.__ |
| فرض کنید زن زوج {TEX()} {i} {TEX}ام{TEX()} {W_i} {TEX} و همسر وی{TEX()} {M_i} {TEX} باشد. ابتدا زن ها به{TEX()} { (n – 1)!} {TEX} طریق دور میز می نشینند. فرض کنید زن ها به ترتیب{TEX()} {W_1,W_2,\cdots ,W_n} {TEX} نشسته باشند. حال ویژگی های{TEX()} {P_1,P_2,\cdots ,P_{2n}} {TEX} را به این صورت تعریف می کنیم. یک حالت نشستن | | فرض کنید زن زوج {TEX()} {i} {TEX}ام{TEX()} {W_i} {TEX} و همسر وی{TEX()} {M_i} {TEX} باشد. ابتدا زن ها به{TEX()} { (n – 1)!} {TEX} طریق دور میز می نشینند. فرض کنید زن ها به ترتیب{TEX()} {W_1,W_2,\cdots ,W_n} {TEX} نشسته باشند. حال ویژگی های{TEX()} {P_1,P_2,\cdots ,P_{2n}} {TEX} را به این صورت تعریف می کنیم. یک حالت نشستن |
| •دارای ویژگی{TEX()} {P_{2i-1}} {TEX} است{TEX()} {M_i \ \Leftrightarrow } {TEX} سمت راست{TEX()} {W_i} {TEX} نشسته باشد. | | •دارای ویژگی{TEX()} {P_{2i-1}} {TEX} است{TEX()} {M_i \ \Leftrightarrow } {TEX} سمت راست{TEX()} {W_i} {TEX} نشسته باشد. |
| •دارای ویژگی{TEX()} {P_{2i}} {TEX} است{TEX()} { M_i \ \Leftrightarrow } {TEX} سمت چپ{TEX()} {W_i} {TEX} نشسته باشد. | | •دارای ویژگی{TEX()} {P_{2i}} {TEX} است{TEX()} { M_i \ \Leftrightarrow } {TEX} سمت چپ{TEX()} {W_i} {TEX} نشسته باشد. |
| واضح است که ویژگی{TEX()} {P_i} {TEX} و{TEX()} {P_{i+1}} {TEX} نمی توانند هم زمان اتفاق افتاده باشند، پس اگر تعریف کنیم: {TEX()} {P_{2n+1}=P_1} {TEX} داریم: {TEX()} { ( i=1,2,\cdots , 2n ) \ N(P_iP_{i+1})=0} {TEX}. همچنین اگر{TEX()} {N(P_{i_1} P_{i_2} \cdots P_{i_k} )=0} {TEX} باشد، آنگاه زیر مجموعه ی {TEX()} {\{ i_1 , i_2 , \cdots , i_k \}} {TEX} شامل دو عضو متوالی دور دایره است. همچنین | | واضح است که ویژگی{TEX()} {P_i} {TEX} و{TEX()} {P_{i+1}} {TEX} نمی توانند هم زمان اتفاق افتاده باشند، پس اگر تعریف کنیم: {TEX()} {P_{2n+1}=P_1} {TEX} داریم: {TEX()} { ( i=1,2,\cdots , 2n ) \ N(P_iP_{i+1})=0} {TEX}. همچنین اگر{TEX()} {N(P_{i_1} P_{i_2} \cdots P_{i_k} )=0} {TEX} باشد، آنگاه زیر مجموعه ی {TEX()} {\{ i_1 , i_2 , \cdots , i_k \}} {TEX} شامل دو عضو متوالی دور دایره است. همچنین |
| •به ازای هر عدد طبیعی {TEX()} {(n < k \le 2n ) \ k} {TEX}، | | •به ازای هر عدد طبیعی {TEX()} {(n < k \le 2n ) \ k} {TEX}، |
| @@{TEX()} {N(cP_{i_1} cP_{i_2} \cdots cP_{i_k} )=0 \ \Rightarrow \ S_k=0} {TEX}@@ | | @@{TEX()} {N(cP_{i_1} cP_{i_2} \cdots cP_{i_k} )=0 \ \Rightarrow \ S_k=0} {TEX}@@ |
| •به ازای هر عدد طبیعی {TEX()} {1 \le k \le n \ , \ k} {TEX} داریم | | •به ازای هر عدد طبیعی {TEX()} {1 \le k \le n \ , \ k} {TEX} داریم |
| {TEX()} {S_k = \sum N(cP_{i_1} cP_{i_2} \cdots cP_{i_k}) =\frac{2n}{k} {{2n-k-1}\choose {k-1}}\times (n-k)!} {TEX} | | {TEX()} {S_k = \sum N(cP_{i_1} cP_{i_2} \cdots cP_{i_k}) =\frac{2n}{k} {{2n-k-1}\choose {k-1}}\times (n-k)!} {TEX} |
| زیرا هر مردی می تواند سمت راست یا چپ همسر خود بنشیند. بنابراین {TEX()} {2n} {TEX}جا داریم که باید {TEX()} {k} {TEX}جای آنها را برای {TEX()} {k} {TEX}مردی که کنار همسران خود می نشینند انتخاب کنیم به طوری که هیچ دو جایی متوالی دوری نباشند. طبق مساله ی قبل این کار را به{TEX()} {\frac{2n}{k} {{2n-k-1}\choose {k-1}}} {TEX} طریق می توانیم انجام دهیم. حال با انتخاب {TEX()} {k} {TEX}جا، مردهایی هم که باید در این جاها بنشینند به صورت یکتا تعیین می شوند و بقیه ی مردها هم به{TEX()} { (n – k)! } {TEX}طریق در جاهای باقی مانده می توانند بنشینند. | | زیرا هر مردی می تواند سمت راست یا چپ همسر خود بنشیند. بنابراین {TEX()} {2n} {TEX}جا داریم که باید {TEX()} {k} {TEX}جای آنها را برای {TEX()} {k} {TEX}مردی که کنار همسران خود می نشینند انتخاب کنیم به طوری که هیچ دو جایی متوالی دوری نباشند. طبق مساله ی قبل این کار را به{TEX()} {\frac{2n}{k} {{2n-k-1}\choose {k-1}}} {TEX} طریق می توانیم انجام دهیم. حال با انتخاب {TEX()} {k} {TEX}جا، مردهایی هم که باید در این جاها بنشینند به صورت یکتا تعیین می شوند و بقیه ی مردها هم به{TEX()} { (n – k)! } {TEX}طریق در جاهای باقی مانده می توانند بنشینند. |
| بنابراین | | بنابراین |
| @@{TEX()} {E_0= \sum_{k=0}^n \frac{2n}{k} {{2n-k-1}\choose {k-1}}(n-k)!} {TEX}@@ | | @@{TEX()} {E_0= \sum_{k=0}^n \frac{2n}{k} {{2n-k-1}\choose {k-1}}(n-k)!} {TEX}@@ |
| @@{TEX()} {E_0 = \sum_{k=0}^n (-1)^k \frac{2n}{2n-k} {{2n-k}\choose k} (n-k)!} {TEX}@@ | | @@{TEX()} {E_0 = \sum_{k=0}^n (-1)^k \frac{2n}{2n-k} {{2n-k}\choose k} (n-k)!} {TEX}@@ |
| --- | | --- |
| ! پیوند های خارجی | | ! پیوند های خارجی |
| [http://Olympiad.roshd.ir/computer/content/pdf/0037.pdf] | | [http://Olympiad.roshd.ir/computer/content/pdf/0037.pdf] |
- | |
+ | --- !همچنین ببینید *((اصل شمول و طرد )) *((اصل لانه کبوتری )) |
| #@^ | | #@^ |