تاریخچه ی:
تعمیم
||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وبسایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وبسایت المپیاد رشد]موجود میباشد. برای مشاهده این موضوعات در وبسایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین میتوانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا)) ، با ویژگیهای بخش آموزش این وبسایت آشنا شوید.:: #@~~__||
^@#16:
!رابطه (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} بیابیم.
---
!قضیه 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()} {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} {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<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()} {{{m+k}\choose k}{q \choose {m+k}}={q\choose m}{{q-m}\choose k}} {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}\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()} {x} {TEX}در هر دو طرف تساوی به یک اندازه سهم دارد. درنتیجه حکم ثابت شد.
---
!قضیه 2
فرض کنید {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()} { S = \{1, 2, \cdots , 1000 \} } {TEX}را بیابید که:
__الف.__بر هیچ کدام از اعداد 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()} {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_3c_5)=33} {TEX}@@
در نتیجه داریم:
@@{TEX()} {s_0=1000} {TEX}@@
@@{TEX()} {S_1=500+333+200=1033} {TEX}@@
@@{TEX()} {S_2=166+100+66=322} {TEX}@@
@@{TEX()} {S_3=333} {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}@@
3.@@{TEX()} {E_2=S_2-{3 \choose 1 }S_3=233} {TEX}@@
4.@@{TEX()} {E_3=S_3=33} {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} باشد. واضح است که
@@{TEX()} {N(c_i)=(n-1)!} {TEX}@@
@@{TEX()} {N(c_ic_j)=(n-2)!} {TEX}@@
@@{TEX()} {\vdots} {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()} { 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}.
#@
@#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()} {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()} {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()} {={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()} {(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| \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| \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()} {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()} {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()} {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()} {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()} {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}} {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()} {(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()} {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()} {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 (-1)^k \frac{2n}{2n-k} {{2n-k}\choose k} (n-k)!} {TEX}@@
---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0037.pdf]
---
!همچنین ببینید
*((اصل شمول و طرد ))
*((اصل لانه کبوتری ))
#@^