اصل شمول و عدم شمول (كاربردها)

تاریخ انتشار: 15 آذر 1399
آخرین ویرایش: 30 شهریور 1400
دسته‌بندی: ترکیبیات (ابزارهای شمارشی)
امتیاز:
بازدید: 39 مرتبه

تابع حسابی اویلر

در نظریه اعداد دیدیم که تعداد اعداد طبیعی کوچک‌تر از عدد طبیعی n که نسبت به آن اول می‌باشند، توسط تابع حسابی اویلر که با نماد αn نمایش داده می‌شود، محاسبه می‌گردد.

قضیه زیر را که در نظریه اعداد بدون اثبات پذیرفتیم با استفاده از اصل شمول و عدم شمول ثابت می‌کنیم: 

قضیه

برای عدد طبیعی n>1 که تجزیه استانداردی به‌صورت n=p1α1.p2α2pkαk دارد، تابع حسابی اویلر به‌صورت زیر محاسبه می‌شود:  

αn=n11p111p211pk

اثبات

مجموعه S که شامل اعداد طبیعی 1 تا n می‌باشد را در نظر می‌گیریم:

در این‎‌صورت S=n می‌باشد.

مجموعه‌های Ai¯ را به‌صورت زیر تعریف می‌کنیم:

Ai¯=m   ;   1mn  ,  pi|m    ;    i=1,2,...,k

چون مجموعه‌های Ai شامل اعدادی می‌باشند که نسبت به n اول نیستند، داریم: 

Ai=pi   ,   2pi   ,  3pi   ,   ...   ,  npipi

یعنی داریم:

A1=p1   ,  2p1   ,   ...   ,  np1p1

و به‌همین ترتیب در مورد Ak   ,  ....  ,   A3   ,  A2

به‌عبارت دیگر A1 شامل اعداد طبیعی کوچک‌تر از n می‌باشد که بر p1 بخش پذیرند و  A2 شامل اعداد طبیعی کوچک‌تر از n می‌باشد که بر p2 بخش پذیرند و به‌همین ترتیب:    

در نتیجه:

Ai=npi

می‌دانیم که AiAj در صورتی‌که ij مجموعه اعداد طبیعی کوچک‌تر از n می‌باشند که هم بر pi و هم بر pj بخش پذیرند، بنابراین:    

AiAj=npipj

به‌همین ترتیب، داریم:

A1A2Ak=np1p2pk

چون تعداد اعداد طبیعی کوچک‌تر از n که نسبت به آن اول باشند، همان تعداد اعضای A¯1A¯2A¯k می‌باشد، داریم:

αn=A¯1A¯k=A1Ak¯=SA1A2Ak

=SA1+A2++Ak+A1A2+A1A3++Ak1Ak           A1A2A3++Ak2Ak1Ak+....-1k+A1A2Ak

=nnp1+np2++npk+np1p2+np1p3++npk1pk       np1p2p3+np2p3p4++npk2pk1pk...+-1knp1p2pk=n11p1.11p211pk

دریافت مثال

تعداد توابع پوشا

تابع f:ABy=f(x) را پوشا گویند، هرگاه برد تابع یعنی Rf با مجموعه انجام یعنی B برابر باشد.

دریافت مثال

قضیه

تعداد توابع پوشا از یک مجموعه n عضوی به یک مجموعه m عضوی که nm برابر است با:

mnm1m1n+m2m2n+m3m3n++1m1   mm11n

اثبات

مجموعه A=a1,a2,...,an و مجموعه B=b1,...,bm را در نظر می گیریم و mn باشد، اگر S مجموع تمام توابع از A به B باشد، آن‌گاه

S=mn

مجموعه Ai مجموعه توابعی از A به B است که هیچ عضوی از A را به bi نسبت نمی‌دهد.  

واضح است که 1im بنابراین Ai=m1n.

به این ترتیب به‌ازای ij مجموعه AiAj مجموعه توابعی از A به B می‌باشد که هیچ عضوی از A را به bi و bj نسبت نمی‌دهد لذا ,,AiAj=m2n در نتیجه A1A2Am=0

اما می‌دانیم مجموعه A¯1A¯2A¯m مجموعه کلیه توابع پوشا از A به B می‌باشد، لذا طبق اصل شمول و عدم شمول داریم:  

A¯1A¯m=A1Am¯=SA1Am=SA1+...+Am+A1A2++Am1AmA1A2A3++Am2Am1Am+  ...+1m1A1A2Am1++1mA1A2Am0

تعداد جملات پرانتز سطر اول m1 است، تعداد جملات پرانتز سطر دوم m2 و .....و تعداد جملات پرانتز سطر یکی مانده به آخر mm-1 می‌باشد، بنابراین:   

تعداد توابع پوشا از مجموعه n عضوی A به مجموعه m عضوی B برابر است با:

mnm1m1n+m2m2n+m3m3n++1m1   mm1

نکته

1- تعداد توابع پوشا از یک مجموعه n عضوی به یک مجموعه n عضوی دیگر برابر n! است.

2- تعداد توابع پوشا و یک‌به‌یک از یک مجموعه n عضوی به یک مجموعه n عضوی دیگر برابر n! است.

3- تعداد توابع پوشا از یک مجموعه n عضوی به یک مجموعه m عضوی که n<m باشد، صفر است.

4- تعداد توابع پوشا و یک‌به‌یک از یک مجموعه n عضوی به یک مجموعه m عضوی nm صفر است.

دریافت مثال

مساله عدم تطبیق

در جایگشت n شی an,...,a2,a1 در n مکان ، فرض می‌کنیم:

مکان 1 متناظر با شی a1 

مکان 2 متناظر با شی a2  

مکان n متناظر با شی an باشد.  

حالت‌هایی از این جایگشت که هیچ کدام از n شی مذکور در مکان متناظر خودشان نباشند، مساله عدم تطبیق نامیده می‌شود.

قضیه

تعداد حالت‌هایی از جایگشت n شی که مساله عدم تطبیق را به‌وجود می‌آورند، برابر است با:

n!111!+12!13!++1n1n!=n!i=0n1n1i!

اثبات

n شی an,...,a2,a1 را در نظر می‌گیریم. اگر S را مجموعه تمام جایگشت های این n شی در نظر بگیریم، آن‌گاه S=n!.    

از طرفی دیگر Ai را مجموعه‌ای در نظر می‌گیریم که شامل جایگشت n شی مذکور باشد، به‌طوری‌که شی ai در مکان متناظر iام قرار دارد.

چون جای ai مشخص است، لذا تعداد حالت‌های ممکن Ai برابر n-1! می‌باشد.1in       

AiAj به‌ازای ij شامل جایگشت هایی از این n شی خواهد بود که شی ai و شی aj در مکان متناظر خود قرار گرفته‌اند، سپس AiAj=n2! به‌همین ترتیب:    

A1An1=1!A1A2An=0!=1

اما می‌دانیم اعضای A¯1...A¯n هیچ‌کدام در مکان متناظر خود قرار ندارند، لذا طبق اصل شمول و عدم شمول، داریم:

A¯1A¯n=A1An¯=SA1A2An=SA1+A2++An+A1A2++An1An           A1A2A3++An2An1An+...          +1nA1A2An

=n!n1n1!+n2n2!++nn1n×1=n!n!1!+n!2!++1nn!n!=n!111!+12!++1nn!

نکته

تعداد جایگشت های n شی متمایز که حداقل یک شی در مکان متناظر خود باشد، برابر است با:

n!n!111!+12!++1nn!

قضیه

تعداد جایگشت های n شی متمایز به‌طوری‌که k عدد اول در مکان متناظر خودشان قرار نگیرد (بقیه اهمیت ندارند) برابر است با:

n!k1n1!+k2n2!++1kkknk!

اثبات

اگر S را مجموعه تمام جایگشت های این n عدد طبیعی بنامیم، در این‌صورت S=n! 

Ai مجموعه تمام جایگشت های این n عدد طبیعی است، به‌طوری‌که عدد i با شرط 1ik در مکان طبیعی (متناظر) خودش قرار دارد، بنابراین چون جای i قبلا مشخص شده است، لذا:  

Ai=n1!

ضمنا AiAj در جای طبیعی خود قرار گرفته اند، بنابراین AiAj=n2!.

و به‌همین ترتیب A1A2Ak شامل تمام جایگشت های این n عدد طبیعی می‌باشد که k عدد اول (اعداد 1 تا k) درجای طبیعی خود قرار گرفته اند، در نتیجه:

A1Ak=nk!

لذا چون A¯1A¯1A¯k که شامل تمام جایگشت های این n عدد طبیعی می‌باشد که k عدد اول در جای طبیعی خود قرار ندارند، با استفاده از اصل شمول و عدم شمول داریم:   

A¯1A¯2A¯k=A1A2Ak¯=SA1A2Ak

=SA1+A2++Ak+A1A2+A2A3++Ak1Ak             A1A2A3++Ak2Ak1Ak                                                   +1kA1A2Ak=n!k1n1!+k2n2!++1kkknk!

تمرین

اعداد طبیعی 1 تا n را مرتب می‌کنیم، فرض کنید dn تعداد حالت‌هایی باشد که هیچ عددی در مکان خود نیست، یعنی 1 در مکان اول نیست، 2 در مکان دوم نیست و غیره.

نشان دهید که dn در رابطه بازگشتی زیر صدق می‌کند:     

dn=n1dn1+dn2    ;    d1=0  ,  d2=1

اگر کلیه جایگشت های اعداد 1,2,...,n را اختیار کنیم، در میان این جایگشت ها آنهایی را (پریش) گویند که هیچ‌یک از n عدد طبیعی در مکان واقعی خود ظاهر نشود.


تعداد پریش‌های این n عدد طبیعی را با dn نشان می‌دهند، با استفاده از تعمیم اصل شمول و عدم شمول ثابت می‌شود که:

dn=n!n!1!n1!   n1!+n!2!n2!   n2!+...+1nn!n!0!0!dn=n!111!+12!13!+...+1n1n!


اکنون نشان می‌دهیم که به ازای dnn  dn1=1n    ;    n2 زیرا می‌توانیم بنویسیم:

dnn  dn1=n!111!+...+1nn!nn1!111!+...+1n1n1!


بعد از عمل تفریق تنها جمله‌ای که باقی می‌ماند جمله n!1nn! است، بنابراین:

dnn  dn1=1n


حال به دستگاه زیر توجه کنید:

dnn  dn1=1ndn1n1dn2=1n1


با جمع دو رابطه داریم:

dnn1dn1n1dn2=1n+1n1dnn1dn1+dn2=0dn=n1dn1+dn2

مثال‌ها و جواب‌ها

اصل شمول و عدم شمول (كاربردها)

1,500تومان
خرید فایل PDF مثال ها و جواب ها

برای ارسال نظر وارد سایت شوید