ترکیب (قضایا)

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

قضیه

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

n+r1   r1=n+r1      n

اثبات

اگر هر شی را با یک * نشان دهیم، با قرار دادن r-1 خط عمودی به‌صورت (|)  این n شی در r مکان قرار می‌گیرند، پس n+r-1 جا داریم که باید با n ستاره و r-1 خط عمودی آنها را پر کنیم.    

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

بنابراین تعداد حالت‌های ممکن برابر است با تعداد انتخاب‌های r-1 جا از میان n+r-1 جای خالی، یعنی برابر:  

n+r1    r1

یادآوری می‌کنیم که:

nr=    nnr

n+r1    r1=       n+r1n+r1r1=n+r1      n

تمرین

به چند طريق می‌توان 15 سكه يكسان را بين پنج نفر تقسيم كرد، به طوری كه ممكن است به برخی از آنها سكه‌ای داده نشود؟ 

اين مساله معادل با توزيع 15 شی يكسان در پنج مکان متمايز است، با اين امكان كه برخی از مکان‌ها می‌توانند خالی باشد كه مطابق قضيه مطرح شده داريم:

n+r1   r1=15+51    51=194

دریافت مثال

تذکر

تعداد جملات بسط a1+a2++arn برابر است با:

n+r1    r1

می‌دانیم هر جمله این بسط به‌شکل a1r1a2r2...arrr می‌باشد به‌طوری که هر یک از توان های rr  ,  ...  ,  r2  ,  r1 می‌توانند یکی از اعداد r  ,  ...  ,  1  ,  0 اختیار کنند، بنابراین این مسله همان توزیع n شی در r مکان می‌باشد.

این توضیح که ممکن است برخی از توان ها برابر صفر شوند، به مثابه مکان خالی می‌باشند، بنابراین تعداد جملات بسط مذکور برابر است با:

n+r1    r1

دریافت مثال

نکته

تعداد جواب‌های صحیح و نامنفی معادله x1+x2++xr=n   ;  xi0 برابر است با:

n+r1    r1

تمرین

معادله زیر چند جواب صحيح نامنفی دارد؟

x+y+z+t=17

n=17r=4n+r1   r1=17+41   41=203

دریافت مثال

قضیه

تعداد جواب‌های صحیح و نامنفی معادله x1+x2++xr=n با شرط 1ir   ,   xici برابر است با:

nc1c2cr+r1r-1

اثبات

همان‌طور که بیان شد، تعداد جواب‌های صحیح و مثبت xr  ,  ...  ,  x2  ,  x1 از معادله x1+x2+...+xr=n    ;    (I) برابر است با:

n+r1    r1

حال فرض کنیم تعداد جواب‌های صحیح معادله فوق را بخواهیم به‌دست آوریم که در شرایط زیر صدق کند:

xrcr  ,  ...  ,  x2c2   ,   x1c1  xici

cr,...,c2,c1 اعداد ثابت طبیعی هستند، تغییر متغیرهای زیر را انجام می‌دهیم: 

y1=x1c1y2=x2c2         yr=xrcr

اگر این مقادیر را در معادله قرار دهیم:

x1+x2+...+xr=n(y1+c1)+(y2+c2)+...+(yr+cr)=ny1+y2+...+yr=nc1c2...cr    ;    ΙΙ

جواب‌های صحیح و مثبت ΙΙ در تناظر یک‌به‌یک با جواب‌های Ι هستند، پس جواب معادله فوق برابر است با:  

nc1c2cr+r1r-1

دریافت مثال

قضیه

تعداد جواب‌های صحیح و نامنفی نامعادله x1+x2+...+xrn برابر است با:

n+r    r

اثبات

برای یافتن تعداد جواب‌های صحیح و نامنفی نامعادله x1+x2++xrn باید تعداد جواب‌های صحیح و نامنفی هر یک از معادلات زیر را بیابیم:

x1+x2++xr=0x1+x2++xr=1x1+x2++xr=2                   x1+x2++xr=n

چون نامعادله مذکور می‌تواند هر یک از معادلات فوق باشد، لذا تعداد جواب‌های صحیح و نامنفی آن برابر با مجموع تعداد جواب‌های صحیح و نامنفی هر یک از معادلات فوق می‌باشد (طبق اصل جمع) که این تعداد برابر است با:

0+r1   r1+1+r1   r1++n+r1   r1=r1r1+   rr1+r+1r1++n+r1   r1  ;   r1r1=rr=rr+   rr1+r+1r1++n+r1   r1

=rr+   rr1+r+1r1++n+r1   r1   ;   pascal=r+1   r+r+1r1++n+r1   r1=r+1   r+r+1r1++n+r1   r1=r+2   r++n+r1   r1                        =r+n   r

قاعده پاسکال:

n+1   r=nr+  nr1

دریافت مثال

قضیه

تعداد حالت‌های توزیع n شی یکسان در r مکان متمایز به‌طوری‌که در هر مکان حداقل k شی وجود داشته باشد و krn برابر است با:

nkr+r1         r1

اثبات

در حالت کلی بین n شی n-1 مکان وجود دارد، برای آن‌که k شی داشته باشیم، باید از بین n-1 مکان r-1 مکان را انتخاب کنیم که این کار به n1r1 طریق ممکن است. 

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

nkr+r1         r1=n1r+r1         r1=n1r1

دریافت مثال

قضیه

تعداد جواب‌های صحیح و مثبت طبیعی معادله x1++xr=n    ;    xi1 برابر است با:

n1r1

دریافت مثال

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

ترکیب (قضایا)

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

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