منو
 صفحه های تصادفی
تحولات خراسان و افغانستان در عهد فتحعلیشاه
گویشهای دیگر ایرانی
صبر
کاربر:رضا محمودی
انحلال مجلس دوم مشروطه
امام علی علیه السلام و پذیرش توبه شخص مرتد
آینه ای از جنس نور
پیامبر اكرم
آیا فرد خوش بینی هستید؟
طایع خلیفه عباسی
 کاربر Online
635 کاربر online

اصل اساسی شمارش

تازه کردن چاپ
علوم ریاضی > علو م رایانه
(cached)





اصول اساسی شمارش

در بسیاری از مسایل به شمردن تعداد حالات پیشامدهایی نظیر قرار گرفتن اشیا در جاهای مشخص یا تقسیم شدن آنها طبق شرایطی معین، یا ایستادن افراد بر حسب ویژگی های خاصی نیازمندیم.
برای مثال، ممکن است به مسایل شمارشی زیر برخورد کنید:
«چند حالت برای ایستادن 5 پسر و 3 دختر در یک صف وجود دارد به طوری که هیچ دو دختری کنار هم قرار نگیرند؟»
«تعداد افراد بزرگ تر از 53000 که ارقام تکراری ندارند، چقدر است؟»
«تعداد زیرمجموعه های 7 عضوی مجموعه که هیچ دو عضو متوالی ندارند، چقدر است؟»
موارد فوق سه مثال ساده از مسایل شمارشی هستند که مربوط به موضوعاتی می باشند که «آنالیز ترکیبی» نامیده می شوند. قبل از هر توضیحی راجع به آنالیز ترکیبی، باید با دو اصل اساسی در مسایل شمارشی یعنی اصل جمع و ضرب آشنا شویم.

اصل جمع

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


مثال

فردی می تواند از سه مسیر هوایی، دریایی و زمینی از شهر به شهر مسافرت کند. فرض کنید 3 راه برای سفر هوایی، 2 راه بری سفر زمینی و 2 راه برای سفر دریایی وجود داشته باشد. این شخص به چند طریق می تواند از شهر به شهر ، مسافرت کند؟


حل.
طبق اصل جمع، این شخص به 7 = 2 + 2 + 3 طریق می تواند از شهر به شهر مسافر ت کند.
فرض کنید یک عدد طبیعی و ، ، ... و ، مجموعه ی متناهی و دو به دو مجزا باشند؛ یعنی به ازای هر داشته باشیم . آن گاه داریم:

اصل ضرب:

اگر پیشامد را بتوان به پیشامد پشت سر هم ، ، ، و ، تقسیم کرد به طوری که:
حالت برای اتفاق افتادن پیشامد ،
حالت برای اتفاق افتادن پیشامد ،
و...
حالت برای اتفاق افتادن پیشامد ،
وجود داشته باشد آن گاه، تعداد حالات اتفاق افتادن پیشامد (اول پیشامد ، بعد پیشامد ، ، و در آخر پیشامد ) برابر است با:




مثال1

شخصی می خواهد از شهر به شهر برود. برای رفتن از شهر به شهر ، باید طبق شکل زیر از شهرهای و عبور کرد. این شخص به چند طریق می تواند از شهر به شهر برود؟
img/daneshnameh_up/a/a8/comm0011a.JPG

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


مثال2

تعداد مقسوم علیه های طبیعی عدد 360 را بیابید.
حل.
چون ، پس هر مقسوم علیه طبیعی 360 را می توان به صورت نوشت که در آن

و بالعکس هر عدد که به صورت فوق نوشته شود یک مقسوم علیه طبیعی عدد 360 است. حال چون را به 4 حالت، را به 3 حالت و را به 2 حالت می توان انتخاب کرد پس تعداد مقسوم علیه های طبیعی 360 برابر است با: .


نکته:

اگر باشد به طوری که ها اعداد اول متمایزی باشند (را به حاصل ضرب عوامل اول تجزیه کرده ایم.) می دانیم عدد ، مقسوم علیه عدد ، است اگر و تنها اگر به بنابراین به ازای هر ، می تواند هر یک از مقادیر را بگیرد. بنابراین طبق اصل ضرب تعداد مقسوم علیه های مثبت برابر است با:

یک دنباله از اعداد یک «دنباله در مبنای » نامیده می شود، اگر به ازای هر باشد. به تعداد جملات یک دنباله طول آن دنباله می گویند. به عنوان مثال مجموعه ی تمام دنباله های به طول 2 در مبنای 2 می باشد.

مثال3

چند دنباله به طول در مبنای وجود دارد؟
حل.
برای ساختن دنباله ی در مبنای ، به طریق می توان را از مجموعه‌ی ، انتخاب کرد. به طریق مشابه، هر یک از جمله های را نیز به طریق می توان انتخاب کرد. پس تعداد دنباله های به طول در مبنای برابر است با .
در مثال های بالا، مشاهده کردید که چگونه اصل های جمع و ضرب به طور جداگانه در حل مسایل شمارشی به کار می روند. اما در حل مسایل پیچیده تر، ما ناچار می شویم از هر دو اصل جمع و ضرب استفاده کنیم. برای روشن شدن این مطلب به حل مثال های زیر می پردازیم.



مثال4

در زبان برنامه نویسی پاسکال نام متغیرها از یک حرف تنها یا یک حرف و به دنبال آن دنباله ای ازاعداد و حروف تشکیل شده است. در این زبان چند متغیر به طول حداکثر 4 وجود دارد؟
حل.
تعداد متغیرهای به طول یک برابر است با 26، تعداد متغیرهای به طول دو برابر است با 36 × 26 (زیرا کاراکتر دوم می تواند هر یک از 26 حرف الفبا یا هر یک از 10 رقم باشد)، تعداد متغیرهای به طول سه برابر است با ، همچنین تعداد متغیرهای به طول چهار بر