منو
 صفحه های تصادفی
آرایش الکترونی کاتیون ها و آنیون ها
خودبیمارانگاری
کشف‎ کوچک‎ ترین‎‎‎‎ قرآن جهان در چین
اثر مایسنر
آزمایش رنگین کمان
سرپرست دوبلاژ
سیاره‌های خارجی و حیات
تاریخچه تهیه مس
بشارت به حکومت حضرت مهدی « ع » در قرآن - توبه : 33
حاکميت اسلام بر دلها
 کاربر Online
717 کاربر online
تاریخچه ی: تعمیم

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

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..