منو
 صفحه های تصادفی
bursitis
مراحل ظهور فیلم
انواع روشهای مبارزه با استرس
اطلاعات بیشتر
مراحل رشد کودک
تاریخ ایلام
چین خوردگی
آزمایش تشدید آونگ ها-2
الکترونگاتیوی
تیره زراوند
 کاربر Online
935 کاربر online
تاریخچه ی: تعمیم

تفاوت با نگارش: 1

Lines: 1-122Lines: 1-125
 ||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]
- +---
!همچنین ببینید
*((اصل شمول و طرد ))
*((اصل لانه کبوتری ))
 #@^ #@^

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:08 ]   4   زینب معزی      جاری 
 یکشنبه 19 شهریور 1385 [08:00 ]   3   زینب معزی      v  c  d  s 
 یکشنبه 19 شهریور 1385 [07:59 ]   2   زینب معزی      v  c  d  s 
 سه شنبه 14 شهریور 1385 [11:08 ]   1   زینب معزی      v  c  d  s 


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..