منو
 صفحه های تصادفی
اروپا در جنگ جهانی دوم
تعیین سن نسبی طبقات
بی‌تفاوتی سیاسی
انواع تابع
عینک فتوکرومیک
طایفه استاجلو
چگونه نیروی خود را در ورزش تنیس به بالاترین حد برسانیم؟
انرژِی فوزیون هسته‌ای
عزاداری بنی هاشم و اصحاب پیامبر درمدینه پس از شهادت امام علیه السلام
هندوانه و خربزه خطرناک
 کاربر Online
794 کاربر online
تاریخچه ی: دوگونه شمردن I

تفاوت با نگارش: 2

Lines: 1-125Lines: 1-125
 ||V{maketoc}|| ||V{maketoc}||
-||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد یی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__|| +||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد کمپیو رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
 ^@#16: ^@#16:
 !دو گونه شمردن !دو گونه شمردن
 در این قسمت قصد داریم یکی از زیباترین و در عین حال پراستفاده ترین، روش های مورد استفاده در ترکیبات، به نام دوگونه شمردن یا{TEX()} { Double \ counting } {TEX} را بررسی کنیم. قبل از هر چیز، لازم است اندکی به خود این روش اشاره کنیم تا آمادگی بیشتری برای درک مسایل حاصل شود؛ همان گونه که از نام این روش پیدا است، ما قرار است که یک کمیت ترکیباتی را از دو روش متفاوت بشماریم و چون این دو روش، یک چیز را می شمارند، طبیعتا با هم برابرند. در وهله اول، شاید این روش، بسیار بدیهی و ساده به نظر آید؛ اما این گونه نیست و بسیاری از مسایل ترکیباتی با استفاده از این روش حل می شوند؛ همان گونه که ((اصل لانه کبوتری)) - با صورت بسیار ساده اش – در حل بسیاری از مسایل به کار می آید؛ در این روش هم – دقیقا مثل اصل لانه کبوتری – فقط از اصل برابری دو مقدار به دست آمده استفاده می کنیم. این روش، در اصل، شامل دو قسمت است که ما در این فصل تا حد امکان به هر دو قسمت که یکی استفاده از این روش در به دست آوردن مقدار یک کمیت و دیگری استفاده از آن در اثبات های ترکیباتی می باشد، اشاره می کنیم. در این فصل، به فراخور موضوع از مثال ها و سوالات المپیادهای گذشته ریاضی و کامپیوتر استفاده نموده به منابع بعضی از موضوعات هم اشاره خواهیم کرد. حال بهتر است که قدم در راه گذشته، با این روش، بیشتر آشنا شویم.  در این قسمت قصد داریم یکی از زیباترین و در عین حال پراستفاده ترین، روش های مورد استفاده در ترکیبات، به نام دوگونه شمردن یا{TEX()} { Double \ counting } {TEX} را بررسی کنیم. قبل از هر چیز، لازم است اندکی به خود این روش اشاره کنیم تا آمادگی بیشتری برای درک مسایل حاصل شود؛ همان گونه که از نام این روش پیدا است، ما قرار است که یک کمیت ترکیباتی را از دو روش متفاوت بشماریم و چون این دو روش، یک چیز را می شمارند، طبیعتا با هم برابرند. در وهله اول، شاید این روش، بسیار بدیهی و ساده به نظر آید؛ اما این گونه نیست و بسیاری از مسایل ترکیباتی با استفاده از این روش حل می شوند؛ همان گونه که ((اصل لانه کبوتری)) - با صورت بسیار ساده اش – در حل بسیاری از مسایل به کار می آید؛ در این روش هم – دقیقا مثل اصل لانه کبوتری – فقط از اصل برابری دو مقدار به دست آمده استفاده می کنیم. این روش، در اصل، شامل دو قسمت است که ما در این فصل تا حد امکان به هر دو قسمت که یکی استفاده از این روش در به دست آوردن مقدار یک کمیت و دیگری استفاده از آن در اثبات های ترکیباتی می باشد، اشاره می کنیم. در این فصل، به فراخور موضوع از مثال ها و سوالات المپیادهای گذشته ریاضی و کامپیوتر استفاده نموده به منابع بعضی از موضوعات هم اشاره خواهیم کرد. حال بهتر است که قدم در راه گذشته، با این روش، بیشتر آشنا شویم.
 --- ---
 !!مثال !!مثال
  به ازای هر{TEX()} {1\le k <n} {TEX} ثابت کنید:  به ازای هر{TEX()} {1\le k <n} {TEX} ثابت کنید:
 @@{TEX()} {{n\choose k}={{n-1}\choose k}+{{n-1}\choose {k-1}}} {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=\{1,2,\cdots , n\}} {TEX}را به ما می دهد، ولی طرف راست چطور؟ مسلماً طرف دوم باید همین مقدار را به ما بدهد، اما چگونه؟
 زیر مجموعه های {TEX()} {k} {TEX}عضوی {TEX()} {A} {TEX}را به دو قسمت تقسیم می کنیم: زیر مجموعه های {TEX()} {k} {TEX}عضوی {TEX()} {A} {TEX}را به دو قسمت تقسیم می کنیم:
 •زیر مجموعه هایی که شامل {TEX()} {n} {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}. تعداد این زیر مجموعه ها برابر است با تعداد زیر مجموعه های{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: @#16:
 •زیر مجموعه هایی که شامل {TEX()} {n} {TEX}نیستند. •زیر مجموعه هایی که شامل {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^\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()} {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\times P_{k-1}^{n-1}} {TEX} @@
  __ب__ @@ {TEX()} {P_k^n=(n-k+1)P_{k-1}^n} {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()} {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()} {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()} { 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}. __ج.__ سمت چپ، تعداد راه های انتخاب {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: @#16:
 !!مثال !!مثال
 تساوی های ترکیبیاتی زیر را ثابت کنید: تساوی های ترکیبیاتی زیر را ثابت کنید:
 __الف.__ @@{TEX()} {k{n\choose k}=n{{n-1}\choose {k-1}}} {TEX} @@ __الف.__ @@{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()} {{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()} {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()} {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}^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()} {\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()} {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} استفاده کنید. __ب__ این مسئله حالت خاصی از قسمت الف است، کافی است به جای {TEX()} {m} {TEX}و {TEX()} {p} {TEX}قرار دهید {TEX()} {n} {TEX}و سپس از رابطه ی {TEX()} {{n\choose {n-k}}={n\choose k}} {TEX} استفاده کنید.
 --- ---
 #@ #@
 @#16: @#16:
 !!مثال !!مثال
  تساوی های ترکیبیاتی زیر را ثابت کنید:  تساوی های ترکیبیاتی زیر را ثابت کنید:
 __الف. رابطه ی چوشی- چی__@@ {TEX()} {{k\choose k}+{{k+1}\choose k}+\cdots +{n\choose k}={{n+1}\choose {k+1}} \qquad (n \ge k)} {TEX}@@ __الف. رابطه ی چوشی- چی__@@ {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()} {{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()} {{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\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()} { 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()} { 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 + 1 } {TEX} باشد، که تعداد این زیر مجموعه ها برابر است با {TEX()} {n\choose k} {TEX}.
 •بزرگ ترین عنصر آن {TEX()} {n} {TEX}باشد، که تعداد این زیر مجموعه ها برابر است با {TEX()} {{{n-1}\choose k}} {TEX}. •بزرگ ترین عنصر آن {TEX()} {n} {TEX}باشد، که تعداد این زیر مجموعه ها برابر است با {TEX()} {{{n-1}\choose k}} {TEX}.
 •بزرگ ترین عنصر آن{TEX()} { n - 1 } {TEX}باشد، که تعداد این ((زیر مجموعه)) ها برابر است با {TEX()} {{{n-2}\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()} {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()} { 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}@@ @@{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: @#16:
  {TEX()} {n} {TEX}نفر برای یک اردوی تفریحی به خارج از شهر رفته اند. در طی {TEX()} {b} {TEX}روز، هر روز {TEX()} {k} {TEX}نفر برای خرید مایحتاج اردو به شهر می روند{TEX()} {(k \le n)} {TEX}. در ضمن می دانیم که هر دو نفری دقیقاً در{TEX()} {\lambda} {TEX} روز به شهر رفته اند و هر نفر دقیقاً در {TEX()} {r} {TEX}روز به شهر رفته است. روابط زیر را ثابت کنید:  {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()} {\lambda (n-1)=r(k-1)} {TEX} @@
  __ ب__ @@{TEX()} { bk = nr } {TEX}@@   __ ب__ @@{TEX()} { bk = nr } {TEX}@@
 __ ج__ @@{TEX()} {b{k\choose 2}= \lambda {n\choose 2}} {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()} {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()} {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}. __ج.__ تعداد کل جفت هایی که در کل به شهر رفته اند را می شماریم. از یک طرف در هر روز {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: @#16:
 !به دست آوردن مقدار یک کمیت ترکیباتی  !به دست آوردن مقدار یک کمیت ترکیباتی
 در این روش، ما بیشتر مسایل را از طریق دوگان آنها، حل می کنیم. منظور از دوگان یک مساله، آن است که به جای پرداختن به شمردن خود کمیت، به شمردن مقداری که متناظر با آن کمیت است، بپردازیم و بدین گونه، سختی مساله را هموار نماییم. با یک مساله ساده شروع می کنیم. در این روش، ما بیشتر مسایل را از طریق دوگان آنها، حل می کنیم. منظور از دوگان یک مساله، آن است که به جای پرداختن به شمردن خود کمیت، به شمردن مقداری که متناظر با آن کمیت است، بپردازیم و بدین گونه، سختی مساله را هموار نماییم. با یک مساله ساده شروع می کنیم.
 --- ---
 !!مثال !!مثال
  آیا می توان ماتریسی به ابعاد {TEX()} {m\times n} {TEX}ساخت به طوری که مجموع درایه های هر سطر آن مثبت و مجموع درایه های هر ستون آن منفی شود؟  آیا می توان ماتریسی به ابعاد {TEX()} {m\times n} {TEX}ساخت به طوری که مجموع درایه های هر سطر آن مثبت و مجموع درایه های هر ستون آن منفی شود؟
 __حل__ __حل__
  شاید این مسئله در نگاه اول، مشکل به نظر آید؛ ولی با اندکی توجه، به سادگی حل می شود. ایده ی اصلی حل، این است که مجموع اعداد همه ی سطرها و مجموع اعداد همه ی ستون ها، هر دو یک کمیت را می شمارند و آن، مجموع تمام اعضای ((ماتریس)) است و مسلماً این مقدار نمی تواند هم مثبت و هم منفی باشد؛ یعنی این کار، امکان پذیر نیست.  شاید این مسئله در نگاه اول، مشکل به نظر آید؛ ولی با اندکی توجه، به سادگی حل می شود. ایده ی اصلی حل، این است که مجموع اعداد همه ی سطرها و مجموع اعداد همه ی ستون ها، هر دو یک کمیت را می شمارند و آن، مجموع تمام اعضای ((ماتریس)) است و مسلماً این مقدار نمی تواند هم مثبت و هم منفی باشد؛ یعنی این کار، امکان پذیر نیست.
 --- ---
 !!مثال !!مثال
  مجموع تعداد عناصر تمام زیر مجموعه های یک مجموعه ی {TEX()} {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 \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()} {2^{n-1}} {TEX} زیر مجموعه آمده است. چرا؟
 حال، چون {TEX()} {n} {TEX}عضو داریم و هر عضو در{TEX()} {2^{n-1}} {TEX} زیر مجموعه آمده است، تعداد یک های ماتریس{TEX()} {n \times 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()} {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 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}. (چرا؟) زیرا{TEX()} {\sum_{k=0}^n {n\choose k}=2^n} {TEX}. (چرا؟)
 --- ---
 !!مثال !!مثال
 #@ #@
 @#16: @#16:
  تعداد دنباله های{TEX()} {A_1,A_2,\cdots ,A_k} {TEX} را که در شرایط زیر صدق می کنند، به دست آورید.  تعداد دنباله های{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_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()} {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()} {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()} { 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}. پس بیایید به مسایل قبل برگردیم و از آنها مدد جوییم. باز هم، فرم ماتریسی مسئله را در نظر می گیریم که {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] [http://Olympiad.roshd.ir/computer/content/pdf/0142.pdf]
 --- ---
 !همچنین ببینید !همچنین ببینید
 *((دوگونه شمردن II )) *((دوگونه شمردن II ))
 *((اصل اکسترمال )) *((اصل اکسترمال ))
 #@^ #@^

تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..