تاریخچه ی:
ترکیب با تکرار
||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]
---
!همچنین ببینید
*((تناظر بین مسائل و شمارش ))
*((توزیع اشیا ))
*((مثلث خیام پاسکال ))
#@^