منو
 کاربر Online
883 کاربر online
تاریخچه ی: دوگونه شمردن I

||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
^@#16:
!دو گونه شمردن
در این قسمت قصد داریم یکی از زیباترین و در عین حال پراستفاده ترین، روش های مورد استفاده در ترکیبات، به نام دوگونه شمردن یا{TEX()} { Double \ counting } {TEX} را بررسی کنیم. قبل از هر چیز، لازم است اندکی به خود این روش اشاره کنیم تا آمادگی بیشتری برای درک مسایل حاصل شود؛ همان گونه که از نام این روش پیدا است، ما قرار است که یک کمیت ترکیباتی را از دو روش متفاوت بشماریم و چون این دو روش، یک چیز را می شمارند، طبیعتا با هم برابرند. در وهله اول، شاید این روش، بسیار بدیهی و ساده به نظر آید؛ اما این گونه نیست و بسیاری از مسایل ترکیباتی با استفاده از این روش حل می شوند؛ همان گونه که اصل لانه کبوتری - با صورت بسیار ساده اش – در حل بسیاری از مسایل به کار می آید؛ در این روش هم – دقیقا مثل اصل لانه کبوتری – فقط از اصل برابری دو مقدار به دست آمده استفاده می کنیم. این روش، در اصل، شامل دو قسمت است که ما در این فصل تا حد امکان به هر دو قسمت که یکی استفاده از این روش در به دست آوردن مقدار یک کمیت و دیگری استفاده از آن در اثبات های ترکیباتی می باشد، اشاره می کنیم. در این فصل، به فراخور موضوع از مثال ها و سوالات المپیادهای گذشته ریاضی و کامپیوتر استفاده نموده به منابع بعضی از موضوعات هم اشاره خواهیم کرد. حال بهتر است که قدم در راه گذشته، با این روش، بیشتر آشنا شویم.
---
!!مثال
به ازای هر{TEX()} {1\le k <n} {TEX} ثابت کنید:
@@{TEX()} {{n\choose k}={{n-1}\choose k}+{{n-1}\choose {k-1}}} {TEX}@@
__حل.__
طرف چپ تعداد انتخاب های زیر مجموعه های {TEX()} {k} {TEX}عضوی مجموعه ی {TEX()} {A=\{1,2,\cdots , n\}} {TEX}را به ما می دهد، ولی طرف راست چطور؟ مسلماً طرف دوم باید همین مقدار را به ما بدهد، اما چگونه؟
زیر مجموعه های {TEX()} {k} {TEX}عضوی {TEX()} {A} {TEX}را به دو قسمت تقسیم می کنیم:
•زیر مجموعه هایی که شامل {TEX()} {n} {TEX}هستند.
تعداد این زیر مجموعه ها برابر است با تعداد زیر مجموعه های{TEX()} { k – 1} {TEX} عضوی مجموعه ی{TEX()} {A^\prime =A_\{n \}} {TEX}. زیرا با اضافه کردن {TEX()} {n} {TEX}به هر یک از زیر مجموعه های{TEX()} { k – 1} {TEX} عضوی مجموعه ی{TEX()} {A^\prime} {TEX}، یک زیر مجموعه ی {TEX()} {k} {TEX}عضوی مجموعه ی {TEX()} {A} {TEX}به دست می آید که شامل {TEX()} {n} {TEX}است و برعکس. طبق تعریف تعداد زیر مجموعه های {TEX()} {k-1} {TEX}عضوی مجموعه ی{TEX()} {A^\prime} {TEX} برابر است با{TEX()} {{{n-1}\choose{k-1}}} {TEX}.
#@
@#16:
•زیر مجموعه هایی که شامل {TEX()} {n} {TEX}نیستند.
تعداد این زیر مجموعه ها برابر است با تعداد زیر مجموعه های {TEX()} {k} {TEX}عضوی مجموعه{TEX()} {A^\prime =A_\{n \}} {TEX}. طبق تعریف نیز تعداد زیر مجموعه های {TEX()} {k} {TEX}عضوی مجموعه‌ی{TEX()} {A^\prime} {TEX} برابر است با{TEX()} {{n-1}\choose k} {TEX}.
بنابراین طبق اصل جمع تعداد زیر مجموعه های {TEX()} {k} {TEX}عضوی مجموعه ی {TEX()} {A} {TEX}برابر است با{TEX()} {{{n-1}\choose {k-1}}+{{n-1}\choose k}} {TEX} و چون دو طرف تساوی یک کمیت را می شمارند؛ پس با یکدیگر برابرند.
---
!!مثال
تساوی های ترکیبیاتی زیر را ثابت کنید:
__الف__ @@{TEX()} {P_k^n=n\times P_{k-1}^{n-1}} {TEX} @@
__ب__ @@ {TEX()} {P_k^n=(n-k+1)P_{k-1}^n} {TEX}@@
__ ج__ @@{TEX()} {P_n^k=\frac{n}{n-k} P_k^{n-1}} {TEX}@@
__حل.__
__ الف.__ سمت چپ، تعداد راه های انتخاب {TEX()} {k} {TEX}نفر از بین {TEX()} {n} {TEX}نفر است که ترتیب انتخاب افراد مهم است. سعی می کنیم طرف راست را هم به همین مقدار سوق دهیم تا اتحاد ثابت شود. برای انتخاب {TEX()} {k} {TEX}نفر از بین {TEX()} {n} {TEX}نفر، ابتدا می توان نفر اول را به {TEX()} {n} {TEX}طریق انتخاب کرد و سپس نفرات دوم تا {TEX()} {k} {TEX}ام ({TEX()} { k – 1 } {TEX} نفر) را از بین{TEX()} { n – 1 } {TEX}نفر باقی مانده به{TEX()} {P_{k-1}^{n-1}} {TEX} طریق انتخاب کرد. پس طبق اصل ضرب حاصل برابر است با{TEX()} {nP_{k-1}^{n-1}} {TEX}.
__ب.__ سمت چپ، تعداد راه های انتخاب {TEX()} {k} {TEX}نفر از بین {TEX()} {n} {TEX}است که ترتیب انتخاب افراد مهم است. سعی می کنیم طرف راست را هم به همین مقدار سوق دهیم تا اتحاد ثابت شود. برای انتخاب {TEX()} {k} {TEX}نفر از بین {TEX()} {n} {TEX}نفر، ابتدا نفر اول تا {TEX()} { k – 1} {TEX} ام ({TEX()} { k – 1} {TEX} نفر) را به{TEX()} {P_{k-1}^n} {TEX} طریق انتخاب کرد و سپس نفر آخر را به{TEX()} { (n – k + 1) } {TEX} طریق انتخاب کرد. پس طبق اصل ضرب حاصل برابر است با{TEX()} {(n-k+1)P_{k-1}^n} {TEX}.
__ج.__ سمت چپ، تعداد راه های انتخاب {TEX()} {k} {TEX}نفر از بین {TEX()} {n} {TEX}است که ترتیب انتخاب افراد مهم است. سعی می کنیم طرف راست را هم به همین مقدار سوق دهیم تا اتحاد ثابت شود. برای انتخاب {TEX()} {k} {TEX}نفر از بین {TEX()} {n} {TEX}نفر، ابتدا می توان یک نفر از افرادی که قرار نیست انتخاب شود (شخص {TEX()} {A} {TEX}) را به {TEX()} {n} {TEX}طریق انتخاب کرد و سپس از بین {TEX()} {n-1} {TEX}نفر باقی مانده {TEX()} {k} {TEX}نفر را انتخاب کرد. این کار را به{TEX()} {nP_k^{n-1}} {TEX} طریق می توان انجام داد ولی شخص {TEX()} {A} {TEX}هر یک از{TEX()} { n – k } {TEX} نفری که انتخاب نشده اند می توانست باشد، پس هر حالتی را{TEX()} { n – k } {TEX} بار شمرده ایم. در نتیجه جواب مسئله برابر است با{TEX()} {\frac{n}{n-k}P_k^{n-1}} {TEX}.
دقت کنید که از مثال های فوق در می یابیم که در اثبات های ترکیبیاتی تساوی ها، هر کجا جمع دیدیم باید از اصل جمع و هر کجا ضرب دیدیم باید از اصل ضرب و هر کجا تقسیم دیدیم باید از روش تقسیم یک کمیت بر تعداد بارهای تکرار هر حالت استفاده کنیم. اگر این روش را در پیش بگیرید اثبات تساوی هایترکیبیاتی آسان می شود.
---
#@
@#16:
!!مثال
تساوی های ترکیبیاتی زیر را ثابت کنید:
__الف.__ @@{TEX()} {k{n\choose k}=n{{n-1}\choose {k-1}}} {TEX} @@
__ب.__ @@{TEX()} {{m\choose k}{n\choose m}={n\choose k}{{n-k}\choose {m-k}}} {TEX}@@
__حل__
__الف__ فرض کنید که می خواهیم یک تیم {TEX()} {k} {TEX}عضوی انتخاب نموده، سپس یک عضو را به عنوان کاپیتان تیم انتخاب نماییم. از یک طرف، می توان {TEX()} {k} {TEX}نفر عضو تیم را انتخاب نمود و بعد کاپیتان تیم را که حاصل سمت چپ تساوی خواهد بود. و از طرفی، می توان ابتداف کاپیتان تیم را به {TEX()} {n} {TEX}طریق انتخاب نمود و سپس{TEX()} { k – 1 } {TEX}عضو دیگر تیم را، که حاصل طرف راست تساوی خواهد شد.
__ب.__ فرض کنید که می خواهیم از بین {TEX()} {n} {TEX}نفر {TEX()} {m} {TEX}کارگر انتخاب نموده و سپس از بین کارگرها {TEX()} {k} {TEX}سرکارگر انتخاب نماییم. از یک طرف، می توان {TEX()} {m} {TEX}کارگر را انتخاب نمود و بعد سرکارگرها را که حاصل سمت چپ تساوی خواهد بود. و از طرفی، می توان ابتدا، سرکارگرها را به{TEX()} {n\choose k} {TEX} طریق انتخاب نمود و سپس{TEX()} { m – k } {TEX} کارگر ساده را، که حاصل سمت راست تساوی خواهد شد.
شاید به نظرتان آید که مثال های قبلی را به آسانی می توان با بسط دادن (روش جبری) اثبات کرد. حال، سعی کنید مثال های بعدی را هم با بسط دادن به دست آورید. (اگر توانستید!!)
---
!!مثال
تساوی های ترکیبیاتی زیر را ثابت کنید:
__الف. رابطه ی واندرموند__ @@ {TEX()} {\sum_{k=0}^p {m\choose k}{n\choose {p-k}}={{m+n}\choose p}} {TEX}@@
__ب__ @@ {TEX()} {\sum_{k=0}^n {n\choose k}^2 ={{2n}\choose n}} {TEX}@@
__حل__
__ الف__ طرف راست، تعداد راه های انتخاب یک زیر مجموعه ی {TEX()} {p} {TEX}عضوی از یک مجموعه ی {TEX()} { m + n } {TEX} عضوی می باشد. سعی می کنیم طرف چپ را هم به همین مقدار سوق دهیم تا اتحاد ثابت شود. می توان {TEX()} { m + n } {TEX} عضو را به دو مجموعه یکی {TEX()} {m} {TEX}عضوی و دیگری {TEX()} {n} {TEX}عضوی افراز کرد. حال، هر زیر مجموعه {TEX()} {p} {TEX}عضوی از این مجموعه ی {TEX()} { m + n } {TEX} عضوی،{TEX()} {(0\le k \le p)k} {TEX} عضو از مجموعه ی اول و{TEX()} { p – k } {TEX} عضو از مجموعه ی دوم دارد؛ یعنی در حالتی که از مجموعه ی اول {TEX()} {k} {TEX}عضو را انتخاب کنیم زیر مجموعه ی {TEX()} {p} {TEX}عضوی را به {TEX()} {{m\choose k}{n\choose{p-k}}} {TEX} طریق می توان ساخت. حال {TEX()} {k} {TEX}هر یک از مقادیر بین0 تا {TEX()} {p} {TEX}را می تواند بگیرد پس طبق اصل جمع تعداد زیر مجموعه های مورد نظر برابر است با{TEX()} {\sum_{k=0}^p {m\choose k}{n\choose{p-k}}} {TEX} که این مقدار سمت چپ تساوی است. به این ترتیب حکم اثبات شد.
__ب__ این مسئله حالت خاصی از قسمت الف است، کافی است به جای {TEX()} {m} {TEX}و {TEX()} {p} {TEX}قرار دهید {TEX()} {n} {TEX}و سپس از رابطه ی {TEX()} {{n\choose {n-k}}={n\choose k}} {TEX} استفاده کنید.
---
#@
@#16:
!!مثال
تساوی های ترکیبیاتی زیر را ثابت کنید:
__الف. رابطه ی چوشی- چی__@@ {TEX()} {{k\choose k}+{{k+1}\choose k}+\cdots +{n\choose k}={{n+1}\choose {k+1}} \qquad (n \ge k)} {TEX}@@
__ب. __ @@ {TEX()} {{m\choose 0}+{{m+1}\choose 1}+\cdots +{{m+l}\choose l}={{m+l+1}\choose l}} {TEX}@@
__حل__
روابط بالا که به روابط «چوشی- چی» معروف هستند، هم ارز می باشند. زیرا می توان زابطه‌ی ب را با توجه به این که{TEX()} {{n\choose k}{n\choose{n-k}}} {TEX}، به شکل
@@{TEX()} {{m\choose m}+{{m+1}\choose m}+\cdots +{{m+l}\choose m}={{m+l+1}\choose l}} {TEX}@@
نوشت. حال اگر در رابطه ی بالا، قرار دهید{TEX()} { m+l=n } {TEX} و{TEX()} {l=k} {TEX}، به رابطه ی الف می رسیم. پس تنها رابطه ی الف را اثبات می کنیم.
می دانیم سمت راست رابطه ی الف برابر است با تعداد زیر مجموعه های{TEX()} { k + 1 } {TEX} عضوی مجموعه ی{TEX()} { S = \{1, 2, \cdots , n + 1 \}} {TEX} . حال سعی می کنیم تعداد این زیر مجموعه ها را به طریق دیگری بشماریم که به سمت چپ رابطه ی الف برسیم. برای این کار زیر مجموعه های{TEX()} { k + 1 } {TEX}عضوی {TEX()} {S} {TEX}را بر اساس بزرگترین عنصر موجود در آن به دسته های زیر تقسیم می کنیم:
•بزرگ ترین عنصر آن{TEX()} { n + 1 } {TEX} باشد، که تعداد این زیر مجموعه ها برابر است با {TEX()} {n\choose k} {TEX}.
•بزرگ ترین عنصر آن {TEX()} {n} {TEX}باشد، که تعداد این زیر مجموعه ها برابر است با {TEX()} {{{n-1}\choose k}} {TEX}.
•بزرگ ترین عنصر آن{TEX()} { n - 1 } {TEX}باشد، که تعداد این زیر مجموعه ها برابر است با {TEX()} {{{n-2}\choose k}} {TEX}.
•بزرگ ترین عنصر آن{TEX()} { k + 1} {TEX} باشد، که تعداد این زیر مجموعه ها برابر است با {TEX()} {k \choose k} {TEX}.
به طور کلی تعداد زیر مجموعه های{TEX()} { k + 1 } {TEX} عضوی {TEX()} {S} {TEX}که بزرگ ترین عنصر آن {TEX()} {p} {TEX}باشد برابر است با{TEX()} {{{p-1}\choose k}} {TEX}. زیرا با حذف {TEX()} {p} {TEX}از این مجموعه ها یک زیر مجموعه ی {TEX()} {k} {TEX}عضوی مجموعه ی {TEX()} { \{1, 2, \cdots , p - 1 \} } {TEX}حاصل می شود و با اضافه کردن {TEX()} {p} {TEX}به هر یک از زیر مجموعه های {TEX()} {k} {TEX}عضوی مجموعه‌ی{TEX()} {\{1, 2, \cdots , p - 1 \} } {TEX}، یک زیر مجموعه ی{TEX()} { k + 1} {TEX} عضوی {TEX()} {S} {TEX}به دست می آید که بزرگ ترین عنصر آن {TEX()} {p} {TEX}است. حال چون{TEX()} {k+1 \le p \le n+1} {TEX}، در نتیجه داریم:
@@{TEX()} {\sum_{p=k+1}^{n+1} {{p-1}\choose k}= \sum_{l=k}^n {l\choose k}={{n+1}\choose {k+1}}} {TEX}@@
به این ترتیب حکم ثابت شد.
---
!!مثال
#@
@#16:
{TEX()} {n} {TEX}نفر برای یک اردوی تفریحی به خارج از شهر رفته اند. در طی {TEX()} {b} {TEX}روز، هر روز {TEX()} {k} {TEX}نفر برای خرید مایحتاج اردو به شهر می روند{TEX()} {(k \le n)} {TEX}. در ضمن می دانیم که هر دو نفری دقیقاً در{TEX()} {\lambda} {TEX} روز به شهر رفته اند و هر نفر دقیقاً در {TEX()} {r} {TEX}روز به شهر رفته است. روابط زیر را ثابت کنید:
__الف__ @@{TEX()} {\lambda (n-1)=r(k-1)} {TEX} @@
__ ب__ @@{TEX()} { bk = nr } {TEX}@@
__ ج__ @@{TEX()} {b{k\choose 2}= \lambda {n\choose 2}} {TEX}@@
__اثبات__
__ الف.__ فرد دلخواهی مانند {TEX()} {A} {TEX}را در نظر بگیرید. این فرد، در {TEX()} {r} {TEX}روز به شهر رفته است. در هر روز، {TEX()} { k – 1 } {TEX} نفر با وی به شهر رفته اند؛ بنابراین در مجموع، {TEX()} {A} {TEX}با{TEX()} { r(k – 1)} {TEX} نفر به شهر رفته است. از طرف دیگر این فرد، با هر یک از افراد دیگر، در{TEX()} {\lambda} {TEX} روز به شهر رفته است. بنابراین در مجموع این فرد با{TEX()} {\lambda (n-1)} {TEX} نفر به شهر رفته است. پس ثابت کردیم که{TEX()} { \lambda (n-1)=r(k-1)} {TEX}.
__ب.__ می دانیم که هر فرد {TEX()} {r} {TEX}روز به شهر رفته است بنابراین مجموعاً {TEX()} {nr} {TEX}نفر به شهر رفته اند. از طرف دیگر، در هر روز {TEX()} {k} {TEX}نفر به شهر رفته اند، بنابراین {TEX()} {bk} {TEX}نفر به شهر رفته اند. پس{TEX()} { nr = bk.} {TEX}
__ج.__ تعداد کل جفت هایی که در کل به شهر رفته اند را می شماریم. از یک طرف در هر روز {TEX()} {k} {TEX}نفر یعنی{TEX()} {k \choose 2} {TEX} جفت نفر به شهر رفته اند. پس مجموعاً{TEX()} {b {k\choose 2}} {TEX} جفت نفر به شهر رفته اند. از طرف دیگر هر دو نفری با هم دقیقاً{TEX()} {\lambda} {TEX} بار به شهر رفته اند، پس{TEX()} { \lambda {n\choose 2}} {TEX} جفت با هم به شهر رفته اند. در نتیجه{TEX()} {b {k\choose 2}= \lambda{n \choose 2}} {TEX}.
مسئله بالا، اساس یک بخش زیبا در ریاضیات به نام «طرح های ترکیبیاتی» می باشد که روی این گونه موارد و نیز طرز ساختن آنها بحث می ند و کاربردهای زیادی هم دارد.
---
#@
@#16:
!به دست آوردن مقدار یک کمیت ترکیباتی
در این روش، ما بیشتر مسایل را از طریق دوگان آنها، حل می کنیم. منظور از دوگان یک مساله، آن است که به جای پرداختن به شمردن خود کمیت، به شمردن مقداری که متناظر با آن کمیت است، بپردازیم و بدین گونه، سختی مساله را هموار نماییم. با یک مساله ساده شروع می کنیم.
---
!!مثال
آیا می توان ماتریسی به ابعاد {TEX()} {m\times n} {TEX}ساخت به طوری که مجموع درایه های هر سطر آن مثبت و مجموع درایه های هر ستون آن منفی شود؟
__حل__
شاید این مسئله در نگاه اول، مشکل به نظر آید؛ ولی با اندکی توجه، به سادگی حل می شود. ایده ی اصلی حل، این است که مجموع اعداد همه ی سطرها و مجموع اعداد همه ی ستون ها، هر دو یک کمیت را می شمارند و آن، مجموع تمام اعضای ماتریس است و مسلماً این مقدار نمی تواند هم مثبت و هم منفی باشد؛ یعنی این کار، امکان پذیر نیست.
---
!!مثال
مجموع تعداد عناصر تمام زیر مجموعه های یک مجموعه ی {TEX()} {n} {TEX}عضوی چقدر است؟
__حل__
__ روش اول__ بیایید این مسئله را به صورت ماتریسی بیان کنیم و از ایده ی مسئله ی قبل، کمک بگیریم. یک ماتریس{TEX()} {2^n \times n} {TEX} را به این روش می سازیم که برای هر کدام از {TEX()} {n} {TEX}عدد، یک ستون و برای هر کدام از{TEX()} {2^n} {TEX} زیر مجموعه، یک سطر در نظر می گیریم و درایه ی{TEX()} { (i, j) } {TEX}ماتریس را برابر یک قرار می دهیم، اگر و فقط اگر عضو {TEX()} {j} {TEX}ام مجموعه ی {TEX()} {S} {TEX}به زیر مجموعه ی {TEX()} {i} {TEX}ام تعلق داشته باشد، صورت مسئله تبدیل به شمردن تعداد یک های موجود در این ماتریس می شود. (چرا؟)
اگر کمی دقت کنید، متوجه می شوید که صورت مسئله از ما، شمردن تعداد یک ها را- از طریق شمردن تعداد یک های هر سطر و جمع زدن عددهای به دست آمده- می خواهد. حال مجموع اعضای ماتریس مورد نظر را از طریق شمردن تعداد یک های هر ستون، به دست می آوریم. کافی است که ببینیم در هر ستون چند تا یک وجود دارد؛ و یا به بیان دیگر ببینیم تعداد زیر مجموعه هایی که یک عضو خاص به آن ها تعلق دارد، چقدر است؟ به راحتی می توان ثابت کرد که هر عضو در{TEX()} {2^{n-1}} {TEX} زیر مجموعه آمده است. چرا؟
حال، چون {TEX()} {n} {TEX}عضو داریم و هر عضو در{TEX()} {2^{n-1}} {TEX} زیر مجموعه آمده است، تعداد یک های ماتریس{TEX()} {n \times 2^{n-1}} {TEX} تاست که این همان مقدار خواسته شده است.
__روش دوم__ می دانیم تعداد زیر مجموعه های {TEX()} {k} {TEX}عضوی یک مجموعه ی {TEX()} {n} {TEX}عضوی برابر است با{TEX()} {n\choose k} {TEX}، بنابراین مسئله مقدار{TEX()} {\sum_{k=0}^n k{n\choose k}} {TEX} را می خواهد. با توجه به این که{TEX()} {k{n\choose k}=n{{n-1}\choose {k-1}}} {TEX}، داریم:
{TEX()} {\sum_{k=0}^n k{n\choose k}= \sum_{k=1}^n n{{n-1}\choose {k-1}}=n2^{n-1}} {TEX}
زیرا{TEX()} {\sum_{k=0}^n {n\choose k}=2^n} {TEX}. (چرا؟)
---
!!مثال
#@
@#16:
تعداد دنباله های{TEX()} {A_1,A_2,\cdots ,A_k} {TEX} را که در شرایط زیر صدق می کنند، به دست آورید.
@@{TEX()} {A_i \subseteq \{1,2,\cdots , n \} \qquad 1 \le i \le k} {TEX}@@
@@{TEX()} {A_1 \cup A_2 \cup \cdots \cup A_k= \{1,2,\cdots , n \}} {TEX}@@
__حل__
برای اثبات، مانند مسئله ی قبل عمل می کنیم؛ بدین ترتیب که برای هر دنباله، ماتریس{TEX()} {k\times n} {TEX} می سازیم که در آن سطرها، نمایشگر زیر مجموعه ها و ستون ها نمایشگر اعضا هستند و اگر عضو {TEX()} {i} {TEX}ام، به زیر مجموعه ی {TEX()} {i} {TEX}ام تعلق داشته باشد، درایه های{TEX()} { (i, j)} {TEX} را برابر یک و در غیر این صورت، برابر صفر قرار می دهیم. اکنون، حل مسئله معادل می شود با این که تعداد ماتریس هایی را که متناظر با این دنباله ها هستند، بشماریم. ابتدا، ببینیم که این ماتریس دارای چه خاصیتی است؛ تنها خاصیت این ماتریس این است که در هر ستون حداقل یک بار، عدد یک آمده است. حال، با توجه به این نکته، مسئله به راحتی قابل حل می باشد؛ زیرا {TEX()} {n} {TEX}ستون داریم و هر ستون {TEX()} {2^k-1} {TEX} حالت مختلف می تواند داشته باشد. (چرا؟) بنابراین تعداد این ماتریس ها- که متناظر با تعداد دنباله ها است- برابر{TEX()} {(2^k-1)^n} {TEX} می باشد.
---
!!مثال
مجموعه{TEX()} { A = \{1, 2, \cdots , k \}} {TEX} را در نظر بگیرید. دنباله ی{TEX()} {T_1,T_2,\cdots , T_n} {TEX} یک زنجیره به طول {TEX()} {n} {TEX}خوانده می شود، اگر هر یک از{TEX()} {T_i } {TEX} ها، یک زیر مجموعه از مجموعه ی {TEX()} {A} {TEX}باشد و برای هر{TEX()} {1 \le i \le n-1} {TEX}، داشته باشیم {TEX()} {T_i \subseteq T_{i+1}} {TEX}، تعداد زنجیره های به طول {TEX()} {n} {TEX}را محاسبه کرده و ادعای خود را ثابت کنید.
__حل__
در وهله ی اول، چنانچه به صورت ساده ی مسئله بنگرید و حتی اگر قصد داشته باشید فرمول بازگشتی برای آن پیدا کنید، شاید نتوانید آن را حل کنید.
پس بیایید به مسایل قبل برگردیم و از آنها مدد جوییم. باز هم، فرم ماتریسی مسئله را در نظر می گیریم که {TEX()} {k} {TEX}ستون برای اعضای 1 تا {TEX()} {k} {TEX}و {TEX()} {n} {TEX}سطر به ترتیب برای هر{TEX()} {(1 \le i \le n) T_i} {TEX} دارد. اگر عضو {TEX()} {j} {TEX}متعلق به زیر مجموعه ی{TEX()} {T_i } {TEX} باشد درایه ی{TEX()} { (i, j) } {TEX} را برابر یک و در غیر این صورت برابر صفر قرار می دهیم. حال، باز هم باید به خاصیت جادویی این ماتریس ها پی ببریم. تنها خاصیت این ماتریس ها، این است که در هر ستون، یک ظاهر نمی شود یا اگر ظاهر شود بعد از اولین ظهور، مکرراً تا سطر {TEX()} {n} {TEX}ام ظاهر می شود. حال، چون {TEX()} {k} {TEX}ستون و برای هر ستون{TEX()} { n + 1 } {TEX}حالت مختلف داریم. بنابراین، تعداد این ماتریس ها و طبعاً تعداد زنجیره های مورد نظر برابر است با{TEX()} {(n+1)^k} {TEX}.

---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0142.pdf]

#@^

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