اصل جمع

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

 www.tizhosh.ir

 بیشتر اوقات با مسائلی رو به رو می شویم که

 از ما خواسته شده است تعداد راه های مختلف انجام یک کار معین را به دست بیاوریم.

در این شاخه از ریاضیات می توان از اصل جمع استفاده کرد

 که ابتدایی ترین اصل در آنالیز ترکیبی است.

اصل جمع

فرض کنید می خواهیم تعداد روشهای انجام یک کار معین

 که آن را کار P می نامیم را به دست آوریم.

 برای این منظور روشهای انجام کار P را به چند دسته ی مجزا تقسیم می کنیم.

اگر به عنوان مثال کار P را بتوانیم به دو دسته ی مجزای «الف» و «ب» تقسیم کنیم،

 و همچنین اگر برای انجام کار P به روش «الف»،

 A راه و برای انجام کار P به روش«ب» B راه وجود داشته باشد،

در این صورت برای انجام کار A+B، P راه وجود خواهد داشت.

شبکه ی بالا را در نظر می گیریم .

اگر در شبکه بالا حرکت فقط در جهت های 

 

 

و ↑ مجاز باشد؛

چند مسیر از A تا E وجود دارد؟

برای اینکه بدانیم از A تا E چند مسیر وجود دارد

ابتدا شبکه را به صورت زیر نام گذاری می کنیم.

شـکل فـوق را دوباره به صورت شکل (3) رسم می کنیم

 و تعداد راه های موجود از A تا هر نقطه را

در دایره ی متناظر آن می نویسیم.

از A تا C تنها یک مسیر وجود دارد

و ازA تا B نیز یک مسیر وجود دارد.

 همچنین ازA تا D ، ازA تا F ، از A تا G ، از A تا H ، از A تا I و از A تا K

نیز تنها یک مسیر وجود دارد.

پس در دایره های متناظر با I ،H ، G، F ، D ، B و K عدد یک را می نویسیم.

حال اگر بخواهیم از نقطه ی A تا نقطه L برویم

 تعداد مسیرهای موجود از A تا L برابر با

مجموع تعداد مسیرهای موجود ازA تا B

و تعداد مسیرهای موجود از A تا C است.

پس در دایره ی متناظر با L عدد 2 را می نویسیم.

حال اگر بخواهیم از نقطه ی A تا نقطه ی M برویم

تعداد مسیرهای موجود از A تا M برابر با مجموع

تعداد مسیرهای موجود از A تا D

 و تعداد مسیرهای موجود از A تا L است.

به صورت مشابه می توان گفت از A تا P نیز 3 = 2 + 1 مسیر

 و از A تا N نیز 4 = 3 + 1 مسیر

و از A تا T نیز 4 = 3 + 1 مسیر وجود دارد.

 به این ترتیب می توان شکل را کامل کرد.

بنابراین از A تا E ، ٍ70 مسیر وجود دارد.

حال اگر در شبکه بالا حرکت در جهت 

 

نیز مجاز باشد ،

 تعداد مسیرهای موجود از A تا E به صورت زیر محاسبه می شود:

 

واضح است که از A تا C یک مسیر و از A تا B نیز یک مسیر وجود دارد.

و همچنین از A تا D ، از A تا F ، از A تا G ، از A تا H ،

از A تا I و از A تا K نیز یک مسیر وجود دارد.

وهمچنین چون حرکت در جهت

 نیز مجاز است

 تعداد مسیرهای موجود از A تا L برابر با 3 مسیر می باشد.

به ترتیب مشابه عددی که در دایره ی P نوشته می شود

 برابر با مجموع سه عدد نوشته شده، در دایره C ، L و F است.

 پس عددی که در دایره متناظر با p می نویسیم مساوی با عدد 5 است.

به همین ترتیب تعداد راه های موجود تا بقیه نقاط را می یابیــم

 و در دایـره های مربـوط به آنــها می نویسیم.

 بنابراین تعداد مسیرهای موجود از A تا E که حرکت در جهت

 

 → ،  یا

مجاز باشد برابر با 321 می باشد.

حال اگر در شبکه ی زیر حرکت فقط در جهت

، یا

مجاز باشد،

 

 چند مسیر از A تا B وجود دارد؟

اگر به شکل توجه کنید متوجه می شوید از A تا C ، از A تا D ،

 از A تا E ،از A تا K ، از A تا L ، از A تا M و از A تا N

 فقط یک مسیر وجود دارد

 و همچنین از A تا F ، از A تا G ، از A تا H ، از A تا O ،

 از A تا P و از A تا R تنها یک مسیر وجود دارد.

پس تعـداد مسیــر از A تا C برابر با 129 مسیـر است.

بنابراین تعداد مسیرها از A تا I برابر با 130 مسیر می باشد.

وهمچنین تعداد مسیرها از A تا T برابر با 170 مسیر می باشد.

 در نتیجه تعداد مسیرهای موجود از A تا S برابر با171 مسیر است.

به این ترتیب تعداد راه های موجود تا بقیه نقاط را می یابیم

 و در دایره های مربوط به آنها می نویسیم.

بنابراین تعداد مسیرهای موجود از A تا B که حرکت در جهت

 

، یا  

مجاز باشد، برابر با 299 می باشد.

/ 0 نظر / 82 بازدید