آنالیز ترکیبی

ترکیبیات،ریاضیات انتخاب و یا آنالیزترکیبی یکی از شاخه‌های جذاب ریاضیات است که به بررسی مسائل شمارش،گرافها ، بازی‌ها و نیز مسائل ساختاری روی مجموعه‌ها متناهی می پردازد. از جمله کاربردهای مهم این شاخه میتوان به استفاده آن در برنامه نویسی کامپیوتر  و الگوریتم‌ها اشاره کرد. یکی از مسائلی که ترکیبیات را از دیگر شاخه‌های ریاضی متمایز می‌کند این است که آموختن آن نیاز به اطلاعات خاصی از ریاضیات ندارد و داشتن معلومات ریاضی دوره راهنمایی نیز برای درک آن کافی به نظر می رسد چرا که ریشه‌های ترکیبیات در واقع به مسائل معماگونه ریاضی و بازیها میرسد. بسیاری از مسائل ترکیبیات که در گذشته برای تفریح بررسی شده اند امروزه اهمیت زیادی در ریاضیات محض و کاربردی دارند. در قرن اخیر ترکیبیات به یکی از مهمترین شاخه‌های ریاضیات تبدیل شده و مرزهای آن همواره گسترش پیدا می‌کند که یکی از مهمترین علل این گسترش سریع، اختراع کامپیوتر می باشد: به علت سرعت بالای کامپیوترها بسیاری از مسائلی که قبلا قابل بررسی نبودند، بررسی شدند. البته تقابل کامپیوتر و ترکیبیات یک طرفه نبوده است و کامپیوترها نمی توانستند مستقل عمل کنند و برای عمل نباز به برنامه داشتند. اساس برنامه‌های کامپیوتری غالبا الگوریتمهای ترکیبیاتی اند و به همین دلیل اهمیت و کاربرد ترکیبیات پس از اختراع کامپیوتر چندین برابر معلوم شد و باعث شد تا ریاضیدانان بسیاری به تحقیقات گسترده در این زمینه رو آوردند. مباحث ترکیبیات بسیار گسترده اند ولی اساس آن بر پایه روشهای شمارش است که از جمله این روش‌ها می توان به اصل جمع، اصل ضرب، جایگشت اشاره کرد . یکایک شمردن یا شمارش، ممکن است به عنوان فرآیندی آشکار تلقی شود که هر دانشجو در آغاز مطالعه علم حساب فرا می گیرد. ولی به نظر می رسد که پس از آن، به تدریج که دانشجو به زمینه‌های «دشوارتر» ریاضیات، چون جبر، هندسه، مثلثات، و حساب دیفرانسیل و انتگرال می رسد توجه بسیار کمتری به گسترش بیشتر مفهوم شمارش مبذول می شود. یکایک شمردن محدود به حساب نیست. کاربردهایی نیز در زمینه هایی چون نظریه کدگذاری ، حساب احتمالات، و آمار (درریاضیات) و در تحلیل الگوریتم ها (در علم کامپیوتر) دارد.

قواعد

مطالعه خود را در ریاضیات گسسته و ترکیباتی با دو اصل اساسی شمارش آغاز می کنیم قاعده‌های حاصل جمع و حاصل ضرب، بیان این قاعده‌ها و کاربردهای اولیه آنها نسبتاً ساده به نظر می رسد. هنگام تحلیل مسائل پیچیده تر، غالباً قادریم مسئله را به بخشهایی قسمت کنیم که با به کارگیری این اصول اساسی قابل حل است. هدف ما ایجاد قدرت «تجزیه»ی این گونه مسائل و ترکیب راه حلهای جزئی برای رسیدن پاسخ نهایی است. یک راه مناسب برای انجام این امر، تجزیه و تحلیل و حل تعداد زیادی از مسائل گوناگون مربوط به شمردن است. ضمن اینکه تمام مدت باید اصولی را که در راه حلها به کار می روند در نظر داشت. این همان رهیافتی است که ما در اینجا دنبال خواهیم کرد.

اصل اول 

اصل نخست شمارش را می توان به صورت زیر بیان کرد: قاعده حاصل جمع:اگر کاری را بتوان به m طریق و کار دیگری را بتوان به n طریق انجام داد، و اگر این دو کار را نتوان همزمان انجام داد، آنگاه این یا آنگاه را میتوان به m+n طریق انجام داد.

توجه داشته باشید که وقتی می گوییم رویدادی خاص، مثلاً کاری از نوع نخست، می تواند به m طریق دهد، فرض بر این است که این m طریق متمایرند، مگر آنکه خلاف آن بیان شود.

مثال 1 کتابخانه دانشکده ای کتاب درسی دربارهٔ جامعه‌شناسی و 50 کتاب درسی در باره انسان‌شناسی دارد. بنابر قاعده حاصل جمع، دانشجویی که در این دانشکده تحصیل می کند، به منظور فراگیری بیشتر دربارهٔ این یا آن موضوع، می تواند بین 90 = 50 + 40 کتاب درسی انتخاب به عمل آورد. مثال 2 قاعده بالا را می توان به بیشتر از دو کار تعمیم داد مشروط برآنکه هیچ جفتی از کارها را نتوان همزمان انجام داد. به عنوان مثال، یک مدرس علم کامپیوتر که در هر یک از زمینه‌ها اپل، بیسیک، فرترن، و پاسکال مثلاً پنج کتاب مقدماتی وارد، می تواند هر یک از این 20 کتاب را به دانشجوی علاقه‌مند به فراگیری نخستین و برنامه نویسی توصیه کند.

اصل دوم 

مثال زیر مدخلی برای معرفی اصل دوم شمارش است. مدیر کارخانه ای به منظور اتخاذ تصمیمی دربارهٔ توسعه کارخانه، 12 نفر از کارمندان خود را در دو گروه گرد آورد. گروه A مرکب از پنج عضو است و بناست دربارهٔ نتایج مساعد احتمالی چنین توسعه تحقیقاتی به عمل آورد. گروه دیگر، یعنی گروه Bکه مرکب از هفت کارمند است دربارهٔ نتایج نامساعد احتمالی بررسیهایی به عمل خواهد آورد. اگر، قبل از اتخاذ تصمیم، مدیر نامبرده بخواهد فقط با یکی از این اعضا دربارهٔ تصمیم صحبت کند، آنگاه بنابر قانون حاصل جمع، می تواند 12 کارمند را احضار کند. ولی، به منظور قضاوت بی طرفانه مدیر نامبرده تقسیم می گیرد که روز دوشنبه با عضوی از گروه Aو سپس روز سه شنبه با عضوی از گروه B صحبت کند تا به اتخاذ تصمیمی نائل گردد. با به کارگیری اصل زیر، ملاحظه می کنیم که او می تواند به 35 = 7 * 5 طریق دو کارمند متعلق به گروههای دو گانه را برگزیند و با آنها صحبت کند.

قاعده حاصل ضرب 

اگر عملی به دو مرحله اول و دوم تقسیم شود و اگر در مرحله اول m نتیجه ممکن و برای هر یک از این نتایج، nنتیجه ممکن در مرحله دوم وجود داشته باشد، آنگاه کل عمل نامبرده می تواند با ترتیب یاد شده، به mn طریق انجام شود.

گاهی این قاعده را اصل انتخاب نیز می نامند.

جایگشت 

مفهوم جایگشت که یکی از مفاهیم مهم در اصول شمارش است را می توان در اثر عبری سفر یتزیر (سفر آفرینش)، که دستنوشته ای است از یک صوفی بین سالهای 200و 600، یافت. ولی شایان توجه است که، حتی قبل از آن، یکی از نتایجی که زنوکراتس از اهالی کالسدان (396 - 314 قبل از میلاد مسیح) به دست آورده بود احتمالاً حاوی «نخستین تلاش ثبت شده برای حل مسئله ای دشوار دربارهٔ ترتیبها و ترکیبها» است. نخستین متن درسی که دربارهٔ برخی از مباحثی که ما در این فصل مورد بحث قرار دادیم کتاب فن حدس زدن اثر ریاضیدان سویسی یاکوب برنولی یکی از هشت ریاضیدان برجسته خانواده برنولی، است. این کتاب مدتی پس از فوت یاکوب برنولی در 1713 منتشر شد و شامل تجدید چاپ نخستین رساله صوری دربارهٔ حساب احتمالات بود. این رساله در 1657 به وسیله کریستیان هویگنس فیزیکدان، ریاضیدان، و منجم هلندای که حلقه‌های دور مشتری را کشف کرد، نوشته شده بود.

ارائه قضیه دو جمله ای 

بلز پاسکال

قضیه دو جمله‌ای به ازای 2n= در اثر اقلیدس ) 300 سال قبل از میلاد مسیح) دیده می شود، ولی عملاًدر قرن شانزدهم اصطلاح «ضریب دو جمله ای» به وسیله میشل اشفل وضع شد. او در اثرش به نام حساب صحیح ضرایب دو جمله ای را تا مرتبه به دست می دهد. بلزپاسکال در پژوهشهای خود دربارهٔ حساب احتمالات، در دهه 1650 رساله ای منتشر کرد که در آن ارتباطهای موجود ضرایب دو جمله ای، ترکیبها، و چند جمله ایها را بررسی می کرد. این نتایج را یاکوب برنولی هنگام اثبات صورت کلی قضیه دو جمله ای، با روشی مشابه با آنچه ما در این فصل ارائه کردیم، به کار برد. استفاده از نماد تا قرن نوزدهم که به وسیله آندره اس فن اتینگهاوزن به کار برده شد، هنوز متداول نشده بود.

در قرن بیستم بود که ظهور کامپیوتر امکان تحلیل منظم و اصولی فرایندها و الگوریتم هایی را که برای تولید جایگشتها و ترکیبها به کار می روند. فراهم ساخت. به طور کلی برای شمارش جایگشت از روش زیر استفاده می کنند.

اگر به عنوان n شی دو به دو متمایز باشند آنگاه هر حال کنار هم قرار گرفتن این n شی کنار هم در یک ردیف را یک جایگشت از این n شی می گوییم. برای ردیف کردن این n شی کنار هم به n مکان نیاز است. برای قرار دادن اولین شی در خانه اول n حالت انتخاب داریم. برای قرار دادن دومین شی در خانه دوم n-1 حالت انتخاب داریم و به همین ترتیب برای قرار داردن n امین شی باقی مانده در خانه nام(خانه اخر) 1 حالت انتخاب داریم به این ترتیب بر طبق اصل ضرب برای قرار دادن این n شی در کنار هم در یک ردیف:

حالت وجود دارد که برابر می باشد با:  

به این ترتیب تعداد حالات جایگشت n شی دو به دو متمایز برابر است.

مثال: به چندطریق می توان 5 کتاب متفاوت را کنار هم در یک قفسه قرار داد؟ 

پاسخ: برطبق توضیحات داده شده جواب برابر است با:  

جایگشت خود می توان به 2 بخش تقسیم شود: 1- جایگشت با تکرار 2- جایگشت دوری

جایگشت با تکرار 

در قسمت قبل در مورد گونه ای جایگشت توضیح دادیم که در آن اشیا در به دو متمایز بودند اما گاهی ممکن است این اشیا در به دو متمایز نباشند و مثلا 3 عدد از انها از یک نوع باشند. چنین حالاتی را جایگشت باتکرار بررسی می کند. با یک مثال روش محاسبه را توضیح می دهیم و سپس فرمولی برای محاسبه حالات بیان می کنیم:

فرض کنید می خواهیم فقط با ارقام 1.2.2.3 اعداد چهار رقمی بسازیم. یعنی عدد 1 یکبار، عدد 2 دو بار، عدد 3 یکبار آمده باشد. بدیهی است که اگر این چهار رقم متمایز و به غیر صفر بودند تعداد اعداد برابر 24=!4 عدد می شد ولی اصل ضرب در این مورد ناخواسته دو عدد 2 را متمایز در نظر گرفته است و مثلا 1223 و 1223 را دو حالت متمایز در یظر گرفته است در حالی که این دو تفاوتی با هم ندارند. با نوشتن تعداد حالات متوجه میشویم که تعداد حالات واقعی این جایگشت !2 برابر مقدار محاسبه شده با اصل ضرب است به این ترتیب تعداد حالات واقعی برابر است. پس به این ترتیب تعداد k شی از یک نوع، به اندازه !K حالات اضافه تولید می کنند که باید از کل حالات که با اصل ضرب محاسبه می‌شود برداشته شوند.

تعریف: اگر n شی در اختیار داشته باشیم که تا از نوع اول، تا از نوع دوم، تا از نوع سوم،....و تا از نوع k ام باشند به گونه ای که این n شی به طریق می توانند در کنار هم قرار بگیرند. در فرمول فوق علت تقسیمها حذف حالات اضافی بوجود آمده است.

مثال: 8 پرچم موجوداند که 3تا به رنگ آبی و 2تا به رنگ قرمز و 3تا به رنگ سفید یکسان هستند.اگر قرار باشد این پرچم ها در یک ردیف کنار  
هم قرار گیرند چند علامت متمایز 8 پرچمی می توان ساخت؟ 

پاسخ:بر طبق مطالب فوق و فرمول ارائه شده تعداد حالات برابر است با:  
واضح است که در این سوال پرچمهای آبی !3 و قرمز !2 و سفید !3 حالت اضافی تولید می کنند که باید از حالات کل یعنی !8 حذف شوند. 

جایگشت دوری 

تا به حال در مورد جایگشتهایی بحث کردیم که در مورد کنار هم قرار دادن چند شی در یک ردیف بودند. حال می خواهیم گونه ای جایگشت را بررسی کنیم که در آن اشیا به صورت دوری در کنار هم قرار گیرند. با یک مثال نحوه محاسبه تعداد حالات جایگشت را توضیح می دهیم و در نهایت فرمولی برای محاسبه ان ارائه می دهیم: فرض کنید می خواهیم تعداد حالاتی را که ممکن است 3 نفربه دور یک میز گرد بنشینند محاسبه کنیم. اگر قرار بر این بود که این افراد در یک ردیف کنار هم باشند این عمل به 6=!3 حالت صورت می پذیرفت. اما در نشستن به دور میز گرد مسئله متفاوت است چرا که بر طبق شکل در این جایگشت هر 3 حالت:

یک حالت محسوب می شوند چرا که هر یک دوران یافته دیگری در یک زاویه معین است و نیز هر سه حالت:

نیز یک حالت محسوب محسوب می شوند. پس تعداد کل حالات متمایز برابر دو عدد است.

به عبارت دیگر می توان A را یکجا قرار داده و B و C را در اطراف او نشاند. این کار به !2=!(2-3) طریق رخ می دهد.