افراز

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

در بسیاری از موارد با مسائلی مواجه می‌شویم که می‌خواهیم یک مجموعه n عضوی را به r زیرمجموعه به‌گونه‌ای تقسیم کنیم که:

  • اجتماع آنها برابر مجموعه مفروض باشد.
  • اشتراک دوبه‌دوی آنها تهی باشد و هیچ‌کدام از زیر مجموعه‌ها، تهی نباشد.

تمرین

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

A=1,2,3,4,5

1,2,3,4,51,2,3,5,41,2,4,5,31,3,4,5,22,3,4,5,1

 در تمرین فوق:

به مجموعه 1,2,3,4,5 یک گردایه و به 5 یک حجره می‌گویند.

همان‌طور که ملاحظه می‌کنید، تعداد حالت‌های مختلفی که یک مجموعه 5 عضوی را به دو گروه می‌توان تبدیل نمود برابر با 5 است و چون ترتیب قرار گرفتن عضوهای هر مجموعه در داخل مجموعه مهم نیست، بنابراین می‌توان گفت که تعداد حالت‌های مختلفی که یک مجموعه 5 عضوی را می‌توان، به دو گروه تقسیم نمود که در یک گروه یک عضو و در گروه دیگر چهار عضو باشد، برابر است با تعداد تبدیل های 5 شی که 4 شی آن از یک نوع و یک شی دیگر از نوع دوم باشد، به‌عبارت دیگر این تعداد برابر است با: 

  54,1=5!4!  1!=5

قضیه

تعداد طریقی که می‌توان یک مجموعه n عضوی را به r دسته تقسیم کرد به‌طوری که در دسته اول n1 عضو و در دسته دوم n2 عضو و .... و در دسته rام، nr عضو قرار گیرند، برابر است با:      

nn1,n2,...,nr=n!n1!n2!...nr!    ; n   1+n2++nr=n

اثبات

افراز مرتب مختلف از مجموعه S به‌صورت A1,A2,...,Ar وجود دارد که در آن A1 شامل n1 عضو و .... و Ar شامل nr عضو است. 

برای تعیین A1 به تعداد nn1 راه موجود است.   

برای تعیین A2 به تعداد n-n1n2 راه موجود است.   

برای تعیین A3 به تعداد n-n1-n2n3 راه موجود است.   

به همین ترتیب:

nn1n-n1    n2n-n1-n2       n3=n!n1!nn1!   nn1!n2!nn1n2!×nn1n2!n3!nn1n2n3!=n!n1!n2!nr!=      nn1,n2,...,nr

تمرین

در یک کلاس، دوازده دانشجو وجود دارند، تعداد راه‌هایی را به‌دست آورید که بتوان سه آزمون متفاوت از این دوازده دانشجو گرفت به‌طوری‌که از هر چهار دانشجو یک آزمون به عمل آید.

روش اول-

تعداد افرازهای مرتبی از دوازده دانشجو را جستجو می‌کنیم که هر زیر مجموعه شامل چهار دانشجو است:

   124,4,4=12!4!4!4!


روش دوم_

1248444

تعداد راه‌هایی را به‌دست آورید که نه اسباب بازی را می‌توان به‌صورت برابر بین سه بچه افراز کرد.

     93,3,3=9!3!3!3!

تعداد راه هایی را به‌دست آورید که نه دانشجو را به سه تیم به ترتیب با چهار، سه و دو دانشجو افراز شوند.

   94,3,2=9!4!3!2!=1260

قضیه

قضیه بازگشتی Sn,r

فرض کنید n>0 و 1rn باشد، تعداد افرازهای r مجموعه ای یک مجموعه n عضوی را با Sn,r نمایش می‌دهیم.  

1- همواره S(n,1)=S(n,n)=1

2- اگر   n,rNو   n3و  2rn1 باشد، آن‌گاه:  

S(n,r)=S(n1,r1)+rS(n1,r)

اثبات

1- افرازهای یک مجموعه ای A عبارت است از A و افرازهای n مجموعه ای A عبارت است از مجموعه های تک عضوی A ، بنابراین:  

S(n,1)=S(n,n)=1

2- ابتدا فرض کنید یک عضو دل‌خواه aA را بر داریم، مجموعه باقیمانده را B می‌نامیم و B دارای n-1 عضو است.

افرازهای r-1 مجموعه ای وC این مجموعه را می نویسیم. 

اکنون به هر یک از افرازهای r-1 مجموعه ای B مجموعه a را می افزائیم که حاصل، یک افراز  r مجموعه ای A خواهد شد.   

از این طریق به تعداد Sn-1,r-1 افراز r مجموعه ای برای A از این طریق حاصل می‌شود بنابراین:   

S(n,r)=S(n1,r1)+rS(n1,r)

نکته

عدد Sn,r به عدد استرلینگ نوع دوم معروف است و ثابت می‌شود که علاوه بر فرمول بازگشتی بیان شده در قضیه فوق، فرمول زیر برای محاسبه آن وجود دارد:  

S(n,r)=1r!i=1r(1)iri(ri)n

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