منو
 کاربر Online
692 کاربر online
تاریخچه ی: ترکیب با تکرار

||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
^@#16:
!ترکیب با تکرار
در فصل قبل دیدیم وقتی بخواهیم از بین {TEX()} { n } {TEX} شی، {TEX()} { k } {TEX} شی را با ترتیب انتخاب کنیم (از هر شی حداکثر یکی می توان برداشت)، به {TEX()} {P_k^n} {TEX} طریق می توانیم این کار را بکنیم. همچنین اگر بخواهیم از بین {TEX()} {n} {TEX}شی، {TEX()} {k} {TEX}شی را بدون ترتیب انتخاب کنیم (از هر شی حداکثر یکی را می توان انتخاب کرد)، به {TEX()} {n\choose k} {TEX} طریق می توانیم این کار را بکنیم. همچنین اگر بخواهیم از بین {TEX()} {n} {TEX}نوع شی، {TEX()} {k} {TEX}شی را با ترتیب انتخاب کنیم (از هر نوع شی می توان هر تعدادی انتخاب کرد)، به {TEX()} {n^k} {TEX} طریق می توانیم این کار را انجام دهیم. ولی سوالی که پیش می آید این است که اگر بخواهیم از بین {TEX()} {n} {TEX}نوع شی، {TEX()} {k} {TEX}شی را بدون ترتیب انتخاب کنیم (از هر نوع شی می توان هر تعدادی انتخاب کرد)، به چند راه می توانیم این کار را انجام دهیم.
---
!!مثال
یک مادر به چند طریق می تواند 7 عدد سیب را بین 4 فرزندش تقسیم کند؟ (می تواند به یک یا چند نفر از فرزندان اصلاً سیبی ندهد.)
حل. اگر تعداد سیب هایی را که فرزند اول می گیرد با{TEX()} {x_1} {TEX}، تعداد سیب هایی را که فرزند دوم می گیرد با{TEX()} {x_2} {TEX}، تعداد سیب هایی را که فرزند سوم می گیرد با{TEX()} {x_3} {TEX} و تعداد سیب هایی را که فرزند چهارم می گیرد با{TEX()} {x_4} {TEX} نشان دهیم، جواب مسئله برابر است با تعداد جواب های صحیح نامنفی معادله ی{TEX()} {x_1+x_2+x_3+x_4=7} {TEX}.
::{picture=img/daneshnameh_up/9/93/com0018a.jpg}::
حال بیایید معادله ی بالا را حل کنیم. اگر هر سیب را با {TEX()} {x} {TEX}نشان دهیم و تعداد {TEX()} {x} {TEX}های قبل از خط اول را با{TEX()} {x_1} {TEX}، تعداد {TEX()} {x} {TEX}های بین خط اول و دوم را با خط{TEX()} {x_2} {TEX}، تعداد {TEX()} {x} {TEX}های بین خط دوم و سوم را با{TEX()} {x_3} {TEX} و تعداد {TEX()} {x} {TEX}های بعد از خط سوم را با{TEX()} {x_4} {TEX} نشان دهیم، یک ((تناظر یک به یک)) بین جواب های ((معادله‌))ی{TEX()} {x_1+x_2+x_3+x_4=7} {TEX} و تعداد آرایش هایی که با 7 علامت {TEX()} {x} {TEX}و 3 علامت {TEX()} {|} {TEX} می توان ساخت برقرار می شود. به عنوان مثال{TEX()} { xxxxx|x||x } {TEX} ، نشان دهنده ی جواب {TEX()} {x_1=5,x_2=1,x_3=0,x_4=1} {TEX} است. ولی می دانیم تعداد آرایش هایی که با 7 تا {TEX()} {x} {TEX}و 3 تا {TEX()} {|} {TEX} ساخته می شود برابر است با{TEX()} {{10\choose 3}={10\choose 7}=\frac{10!}{3!7!}} {TEX}. پس مسئله حل شد.
---
!نکته
به طریق مشابه می توانید ثابت کنید تعداد جواب های صحیح نامنفی معادله ی{TEX()} {x_1+x_2+\cdots +x_n=m} {TEX}، برابر است با تعداد آرایش های {TEX()} {m} {TEX}تا {TEX()} {x} {TEX}و{TEX()} { n – 1 } {TEX}تا {TEX()} {|} {TEX}، یعنی برابر است با{TEX()} {{{m+n-1}\choose m }= {{m+n-1}\choose {n-1}}} {TEX}.
---
!!مثال
یک پدر به چند طریق می تواند 10 دلار به 3 فرزندش عیدی دهد، به طوری که به هر فرزندش حداقل یک دلار بدهد؟ (این 10 دلار به صورت اسکناس های یک دلاری هستند.)
__حل.__
باز با کمی فکر می توانید بفهمید که جواب مسئله برابر با تعداد جواب های صحیح معادله ی {TEX()} {x_1+x_2+x_3=10} {TEX} است به شرط این که{TEX()} {x_!,x_2,x_3\ge 1} {TEX} باشد.
حال باید مسئله را به فرم آشنای خودمان تبدیل کنیم. یعنی به صورت{TEX()} {y_1+y_2+y_3=n} {TEX} به طوری که{TEX()} {y_i\ge 0} {TEX} باشد. برای این کار تعریف می کنیم:
@@{TEX()} {y_1=x_1-1,y_2=x_2-1 ,y_3=x_3-1} {TEX}@@
در نتیجه یک تناظر یک به یک بین مسئله ی اصلی و تعداد جواب های معادله ی{TEX()} {y_1+y_2+y_3=7} {TEX} برقرار می شود، پس جواب برابر است با{TEX()} {{9\choose 2} ={9\choose 7}} {TEX}.
---
!!مثال
تعداد دسته جواب های طبیعی معادله ی زیر را بیابید.
@@{TEX()} {(x_1+x_2+x_3)(y_1+y_2+y_3+y_4)=77} {TEX}@@
__حل.__
#@
@#16:
فرض کنید{TEX()} {x_1+x_2+x_3=m} {TEX} و{TEX()} {y_1+y_2+y_3+y_4=n} {TEX} باشد. چون{TEX()} {x_i} {TEX} ها و{TEX()} {y_i} {TEX} ها طبیعی هستند پس {TEX()} {m\ge 3} {TEX} و{TEX()} {n\ge 4} {TEX}. در این صورت معادله ی{TEX()} { mn = 77 } {TEX} تنها دو جواب ({TEX()} { m = 7, n = 11} {TEX} و {TEX()} { m = 11, n = 7} {TEX}) دارد.
•{TEX()} {x_1+x_2+x_3=7} {TEX} و{TEX()} {y_1+y_2+y_3+y_4=11} {TEX}. تعداد جواب های طبیعی{TEX()} {x_1+x_2+x_3=7} {TEX} برابر است با{TEX()} {{6\choose 2}} {TEX} و تعداد جواب های طبیعی{TEX()} {y_1+y_2+y_3+y_4=11} {TEX} برابر است با{TEX()} {{{10}\choose 3} {TEX}. پس طبق ((اصل ضرب ))تعداد جواب های معادله ی مورد نظر در این حالت برابر است با{TEX()} {{6\choose 2}{10\choose 3}} {TEX}.
•{TEX()} {x_1+x_2+x_3=11} {TEX} و{TEX()} {y_1+y_2+y_3+y_4=7} {TEX}. تعداد جواب های طبیعی {TEX()} {x_1+x_2+x_3=11} {TEX} برابر است با{TEX()} {{{10}\choose 2}} {TEX} و تعداد جواب های طبیعی{TEX()} {y_1+y_2+y_3+y_4=7} {TEX} برابر است با{TEX()} {{6\choose 3}} {TEX}. پس طبق اصل ضرب تعداد جواب های معادله ی مورد نظر در این حالت برابر است با{TEX()} {{{10}\choose 2}}{6\choose 3}} {TEX}.
پس طبق ((اصل جمع)) تعداد جواب های معادله ی مورد نظر برابر است با{TEX()} {{6\choose 2}{{10}\choose 3}+{{10}\choose 2}{6\choose 3}} {TEX}
---
!!مثال
تعداد جواب های صحیح نامنفی ((نامعادله)) ی{TEX()} {x_1+x_2+\cdots +x_n\le m} {TEX} را بیابید.
__حل__
باز باید مسئله را به مسئله ای تبدیل کنیم که قابل حل باشد. برای این کار فرض کنید{TEX()} {{\alpha}_1,{\alpha}_2,\cdots ,{\alpha}_n} {TEX} یک جواب نامعادله ی{TEX()} {x_1+x_2+\cdots +x_n\le m} {TEX} و{TEX()} {\beta=m-({\alpha}_1+{\alpha}_2+\cdots +{\alpha}_n)\ge 0} {TEX} باشد. در نتیجه {TEX()} {{\alpha}_1,{\alpha}_2,\cdots ,{\alpha}_n,\beta} {TEX} نیز یک جواب معادله ی{TEX()} {x_1+x_2+\cdots +x_n+y=m} {TEX} با شرط{TEX()} {x_1,x_2,\cdots ,x_n,y\ge 0} {TEX} است و هر جواب معادله ی فوق هم متناظر با یک جواب نامعادله ی مورد نظر است. ولی تعداد جواب های صحیح نامنفی معادله ی{TEX()} {x_1+x_2+\cdots +x_n+y=m} {TEX} برابر است با{TEX()} {{{n+m}\choose m}={{n+m}\choose n}} {TEX}.
!!مثال
سه دختر به نام های مریم، سارا و فرزانه و نه پسر می خواهند در یک ردیف بایستند. این کار به چند طریق امکان دارد اگر بخواهیم که سارا بین مریم و فرزانه باشد و بین مریم و سارا نیز دقیقاً چهار پسر باشد؟
__حل.__
__روش اول.__ ابتدا دخترها را به دو طریق به صف می کنیم. (مریم سمت راست یا چپ سارا) حال جای پسرها را تعیین می کنیم. فرض کنید{TEX()} {x_1} {TEX} تعداد پسرهای قبل دختر اول و{TEX()} {x_2} {TEX} تعداد پسرهای بین دختر اول و دوم و{TEX()} {x_3} {TEX} تعداد پسرهای بین دختر دوم و سوم و{TEX()} {x_4} {TEX} تعداد پسرهای بعد از دختر سوم باشد. اگر ترتیب دختر ها به ترتیب مریم، سارا و فرزانه (فرزانه، سارا و مریم) باشد آن گاه داریم{TEX()} {(x_3=4)x_2=4} {TEX} و{TEX()} {x_1+x_2+x_3+x_4=9} {TEX}. همان طور که می دانید تعداد جواب های صحیح نامنفی معادله ی{TEX()} {x_1+x_2+x_3+x_4=9} {TEX} با شرط{TEX()} {(x_3=4)x_2=4} {TEX} برابر است با{TEX()} {7\choose 2=21} {TEX}. پس جای پسرها به{TEX()} {7\choose 2} {TEX} طریق تعیین می شود. حال خود پسرها هم به {TEX()} {9!} {TEX}طریق می توانند بایستند پس جواب مسئله برابر است با{TEX()} {2\times 9!{7\choose 2}=42\times 9!} {TEX}.
__روش دوم.__ ابتدا پسرهایی که باید بین مریم و سارا قرار بگیرند را به{TEX()} {9\times 4} {TEX} طریق انتخاب می کنیم. ولی خود پسرها نیز به{TEX()} {4!} {TEX}طریق می توانند بین مریم و سارا قرار بگیرند. حال مریم و سارا و این 4 پسر را یک نفر مانند {TEX()} {A} {TEX}در نظر می گیریم. پس ما می خواهیم 7 نفر (5 پسر دیگر و فرزانه و {TEX()} {A} {TEX}) را به صف بایستانیم. این کار را به{TEX()} {7!} {TEX}طریق می توان انجام داد. پس جواب مسئله برابر است با{TEX()} {7!\times 4!{9\choose 4}=42\times 9!} {TEX}. (دقت کنید که اگر {TEX()} {A} {TEX}قبل از فرزانه قرار بگیرد، آن گاه سارا بعد از مریم و در غیر این صورت قبل از مریم قرار می گیرد.)
---
!!مثال
یک سکه را چند بار به هوا پرتاب می کنیم. اگر رو بیاید آن را با {TEX()} {T} {TEX}و اگر پشت بیاید آن را با {TEX()} {H} {TEX}نشان می دهیم. اگر بعد از یک بار رو آمدن، بلافاصله پشت بیاید آن را با {TEX()} {TH} {TEX}و اگر دو بار پشت سرهم پشت بیاید با {TEX()} {HH} {TEX}نمایش می دهیم. برای مثال، اگر 15 بار سکه انداختن را با{TEX()} { HHTTHHHHTHHTTTT } {TEX} نمایش دهیم در آن پنج بار {TEX()} {HH} {TEX}، سه بار {TEX()} { HT } {TEX} ، دو بار{TEX()} { TH } {TEX} و چهار بار{TEX()} { TT } {TEX} آمده است. در چند دنباله از انداختن 15 سکه، دقیقاً دوبار {TEX()} {HH} {TEX}، سه بار {TEX()} {HT} {TEX}، چهار بار {TEX()} {TH} {TEX}و پنج بار {TEX()} {TT} {TEX}می آید؟
__حل.__
چون تعداد {TEX()} {TH} {TEX}ها یک واحد از {TEX()} {HT} {TEX}ها بیش تر است پس اولین بار رو و آخرین بار پشت آمده است. (دقت کنید که هر طور سکه را بیندازیم تعداد {TEX()} {TH} {TEX}ها با تعداد {TEX()} {HT} {TEX}ها حداکثر یک واحد اختلاف دارد.) پس می توانیم فرض کنیم که آمدن سکه ها به شکل زیر باشد.
::{picture=img/daneshnameh_up/9/96/com0018b.jpg}::
یعنی{TEX()} {x_1} {TEX} بار اول {TEX()} {T} {TEX}، بار{TEX()} {x_1+1} {TEX} تا{TEX()} {x_1+y_1} {TEX} ام {TEX()} {H} {TEX}، ... و{TEX()} {y_4} {TEX} تا آخر {TEX()} {H} {TEX}آمده باشد. اگر{TEX()} {x_i} {TEX} ها و{TEX()} {y_i} {TEX} ها{TEX()} {1\le i\le 4} {TEX} طبیعی باشند، واضح است که در این رشته دقیقاً سه بار {TEX()} {HT} {TEX}و چهار {TEX()} {TH} {TEX}آمده است. چون در این رشته دو بار {TEX()} {HH} {TEX}آمده است پس{TEX()} {y_1-1+y_2-1+y_3-1+y_4-1=2} {TEX}، یعنی{TEX()} {G} {TEX}. به طریق مشابه چون در این رشته پنج بار {TEX()} {TT} {TEX}آمده است پس{TEX()} {x_1-1+x_2-1+x_3-1+x_4-1=5} {TEX}، یعنی{TEX()} {x_1+x_2+x_3+x_4=9} {TEX}. تعداد جواب های طبیعی معادله ی{TEX()} {y_1+y_2+y_3+y_4=6} {TEX}، برابر است با{TEX()} {5\choose 3 = 10} {TEX} همچنین تعداد جواب های طبیعی معادله ی{TEX()} {x_1+x_2+x_3+x_4=9} {TEX}، برابر است با{TEX()} {8\choose 3 =56} {TEX}. پس طبق ((اصل ضرب)) جواب نهایی برابر است با{TEX()} {{5\choose 3}{8\choose 3}=560} {TEX}.
---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0026.pdf]
---
!همچنین ببینید
*((تناظر بین مسائل و شمارش ))
*((توزیع اشیا ))
*((مثلث خیام پاسکال ))
#@^

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:00 ]   3   زینب معزی      جاری 
 یکشنبه 19 شهریور 1385 [06:56 ]   2   زینب معزی      v  c  d  s 
 شنبه 11 شهریور 1385 [13:43 ]   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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..