در بسیاری از مسایل به شمردن تعداد حالات پیشامدهایی نظیر قرار گرفتن اشیا در جاهای مشخص یا تقسیم شدن آنها طبق شرایطی معین، یا ایستادن افراد بر حسب ویژگی های خاصی نیازمندیم.
برای مثال، ممکن است به مسایل شمارشی زیر برخورد کنید:
«چند حالت برای ایستادن 5 پسر و 3 دختر در یک صف وجود دارد به طوری که هیچ دو دختری کنار هم قرار نگیرند؟»
«تعداد افراد بزرگ تر از 53000 که ارقام تکراری ندارند، چقدر است؟»
«تعداد زیرمجموعه های 7 عضوی مجموعه که هیچ دو عضو متوالی ندارند، چقدر است؟»
موارد فوق سه مثال ساده از مسایل شمارشی هستند که مربوط به موضوعاتی می باشند که «آنالیز ترکیبی» نامیده می شوند. قبل از هر توضیحی راجع به آنالیز ترکیبی، باید با دو اصل اساسی در مسایل شمارشی یعنی اصل جمع و ضرب آشنا شویم.
اگر پیشامد را بتوان به پیشامد ، تقسیم کرد به طوری که:
حالت برای اتفاق افتادن پیشامد ،
حالت برای اتفاق افتادن پیشامد ،
و...
حالت برای اتفاق افتادن پیشامد ،
وجود داشته باشد و هیچ دو پیشامدی با هم اتفاق نیفتند آنگاه، تعداد حالات اتفاق افتادن یکی از پیشامدهای ، ، .، یا برابر است با
فردی می تواند از سه مسیر هوایی، دریایی و زمینی از شهر به شهر مسافرت کند. فرض کنید 3 راه برای سفر هوایی، 2 راه بری سفر زمینی و 2 راه برای سفر دریایی وجود داشته باشد. این شخص به چند طریق می تواند از شهر به شهر ، مسافرت کند؟
حل. طبق اصل جمع، این شخص به 7 = 2 + 2 + 3 طریق می تواند از شهر به شهر مسافر ت کند.
فرض کنید یک عدد طبیعی و ، ، ... و ، مجموعه ی متناهی و دو به دو مجزا باشند؛ یعنی به ازای هر داشته باشیم . آن گاه داریم:
اگر پیشامد را بتوان به پیشامد پشت سر هم ، ، ، و ، تقسیم کرد به طوری که:
حالت برای اتفاق افتادن پیشامد ،
حالت برای اتفاق افتادن پیشامد ،
و...
حالت برای اتفاق افتادن پیشامد ،
وجود داشته باشد آن گاه، تعداد حالات اتفاق افتادن پیشامد (اول پیشامد ، بعد پیشامد ، ، و در آخر پیشامد ) برابر است با:
تعداد مقسوم علیه های طبیعی عدد 360 را بیابید.
حل. چون ، پس هر مقسوم علیه طبیعی 360 را می توان به صورت نوشت که در آن
و بالعکس هر عدد که به صورت فوق نوشته شود یک مقسوم علیه طبیعی عدد 360 است. حال چون را به 4 حالت، را به 3 حالت و را به 2 حالت می توان انتخاب کرد پس تعداد مقسوم علیه های طبیعی 360 برابر است با: .
اگر باشد به طوری که ها اعداد اول متمایزی باشند (را به حاصل ضرب عوامل اول تجزیه کرده ایم.) می دانیم عدد ، مقسوم علیه عدد ، است اگر و تنها اگر به بنابراین به ازای هر ، می تواند هر یک از مقادیر را بگیرد. بنابراین طبق اصل ضرب تعداد مقسوم علیه های مثبت برابر است با:
یک دنباله از اعداد یک «دنباله در مبنای » نامیده می شود، اگر به ازای هر باشد. به تعداد جملات یک دنباله طول آن دنباله می گویند. به عنوان مثال مجموعه ی تمام دنباله های به طول 2 در مبنای 2 می باشد.
چند دنباله به طول در مبنای وجود دارد؟ حل. برای ساختن دنباله ی در مبنای ، به طریق می توان را از مجموعه‌ی ، انتخاب کرد. به طریق مشابه، هر یک از جمله های را نیز به طریق می توان انتخاب کرد. پس تعداد دنباله های به طول در مبنای برابر است با .
در مثال های بالا، مشاهده کردید که چگونه اصل های جمع و ضرب به طور جداگانه در حل مسایل شمارشی به کار می روند. اما در حل مسایل پیچیده تر، ما ناچار می شویم از هر دو اصل جمع و ضرب استفاده کنیم. برای روشن شدن این مطلب به حل مثال های زیر می پردازیم.
در زبان برنامه نویسی پاسکال نام متغیرها از یک حرف تنها یا یک حرف و به دنبال آن دنباله ای ازاعداد و حروف تشکیل شده است. در این زبان چند متغیر به طول حداکثر 4 وجود دارد؟
حل. تعداد متغیرهای به طول یک برابر است با 26، تعداد متغیرهای به طول دو برابر است با 36 × 26 (زیرا کاراکتر دوم می تواند هر یک از 26 حرف الفبا یا هر یک از 10 رقم باشد)، تعداد متغیرهای به طول سه برابر است با ، همچنین تعداد متغیرهای به طول چهار برابر است با . بنابراین طبق اصل جمع تعداد متغیرهای به طول حداکثر 4 برابر است با:
.
در حل مثال قبل دیدیم که مسأله را نمی توان مستقیماً با اصل جمع یا ضرب حل کرد. بنابراین مسأله را به چند مسأله ی کوچکتر (براساس طول متغیرها) تقسیم کردیم. سپس هر یک از زیر مسأله ها را حل کردیم و بعد با ترکیب جواب زیر مسأله ها (جمع زدن جواب آنها)، جواب مسأله ی اصلی را به دست آوردیم. این تکنیک که روش تقسیم و حل نام دارد در حل بسیاری از مسایل به ما کمک می کند.
تعداد زوج مرتب های از اعداد صحیح را بیابید به طوری که . (دقت کنید که با ، تفاوت دارد.)
حل. (راه اول): (روش تقسیم و حل) اگر باشد آنگاه . حال مسأله را براساس مقدار به سه قسمت زیر تقسیم می کنیم:
•، در این حالت به نامعادله ی می رسیم که 5 جواب دارد. پس تعداد زوج مرتب هایی که مؤلفه ی اول آنها صفر است برابر 5 می باشد.
•، در این حالت به نامعادله ی می رسیم که 5 جواب دارد. پس تعداد زوج مرتب هایی که مؤلفه ی اول آنها است برابر می باشد (خود به دو طریق می تواند انتخاب شود).
•، در این حالت به نامعادله ی می رسیم که 3 جواب دارد. پس تعداد زوج مرتب هایی که مؤلفه ی اول آنها است برابر می باشد (خود به دو طریق می تواند انتخاب شود).
بنابراین طبق اصل جمع، جواب مسأله برابر است با:
راه دوم: (روش اصل متمم). می دانیم تعداد زوج مرتب هایی که برابر است با تعداد زوج مرتب هایی که منهای تعداد زوج مرتب هایی که .
اگر ، آنگاه می باشد. حال چون هر یک از مؤلفه های اول و دوم (مستقل از یکدیگر) به 5 طریق ( و ) می توانند انتخاب شوند؛ پس تعداد زوج مرتب هایی که برابر است با .
اگر ، آن گاه ، . پس تعداد زوج مرتب هایی که برابر است با . در نتیجه جواب مسأله برابر است با .
در حل مسأله ی بالا از اصل متمم استفاده کردیم، این اصل می گوید:
تعداد حالات قابل قبول = تعداد حالات غیرقابل قبول – تعداد کل حالات
برای عدد طبیعی چند زوج مرتب از اعداد طبیعی وجود دارد که در معادله ی صدق می کند. (مسابقات ریاضی پاتنام، 1960)
حل. .
پس اگر باشد ، آن گاه و . (دقت کنید که چون x و y باید اعداد طبیعی باشند، جواب و مورد قبول نمی باشد.) در نتیجه به ازای هر تجزیه ی به حاصل ضرب دو عدد طبیعی یک جواب یکتا برای زوج مرتب به دست می آید. ولی تعداد راه های تجزیه ی به حاصل ضرب دو عدد طبیعی برابر با تعداد مقسوم علیه های می باشد. پس اگر باشد، جواب مسأله برابر است با .
یک مکعب به ضلع 3 را در نظر بگیرید که در مرکز هر یک از مکعب های کوچک آن یک نقطه گذاشته شده است (مجموعاً 27 نقطه) چند تا مجموعه ی سه تایی از این نقاط روی یک خط راست قرار دارند؟ (مرحله ی اول پنجمین المپیاد کامپیوتر)
الف) 48
ب) 36
ج) 49
د) 43
ه) 37
حل. گزینه ی ج صحیح است. این مکعب را طوری در نظر بگیرید که اضلاع آن موازی محورهای مختصات باشند. حال 3 لایه ی عمود بر محور ها، 3 لایه ی عمود بر محور ها و 3 لایه ی عمود بر محور ها را در نظر بگیرید. در هر یک از این 9 لایه 2 مجموعه ی سه تایی وجود دارد که قطرهای آن لایه را می سازند. پس پاره خط های سه تایی به طول (قطرهای فرعی) برابر می باشد. همچنین موازی هر یک از محورهای مختصات (محور ها، محور ها و محور ها) نه تا پاره خط سه تایی وجود دارد. پس خط موازی محورهای مختصات وجود دارد که از سه تا از این نقاط می گذرند. همچنین از به هم پیوستن دو به دوی 8 نقطه ی وسط مکعب های گوشه ای مکعب که در یک وجه نیستند و نقطه ی داخل مکعبوسطی (قطرهای اصلی) 4 پاره خط به وجود می آید که از سه تا از این نقاط می گذرد. پس مجموعاً پاره خط با شرایط مورد نظر وجود دارد.
به چند طریق می توان سه عدد متفاوت از میان اعداد صحیح 1 تا 9 انتخاب کرد که مجموع آنها بر سه بخش پذیر باشد؟ (مرحله اول نهمین المپیاد کامپیوتر)
الف) 27
ب) 28
ج) 30
د) 45
ه) 84
حل. گزینه ج صحیح است. اگر بخواهیم سه عدد انتخاب کنیم که مجموع آنها بر سه بخش پذیر باشد، باید باقی مانده ی هر سه عدد بر 3 مساوی باشد (حالت اول) یا باقی مانده ی دو به دوی آنها متمایز باشد (حالت دوم). باقی مانده ی اعضای مجموعه ی
بر 3، برابر 1، باقی مانده ی مجموعه ی بر 3، برابر 2 و باقی مانده‌ی اعضای مجموعه ی بر 3، برابر است. در حالت اول به سه طریق می توان این اعداد را انتخاب کرد. در حالت دوم به سه حالت می توانیم یکی از اعضای ، به سه حالت یکی از اعضای و به سه حالت یکی از اعضای را انتخاب کنیم. پس طبق اصل ضرب به طریق می توانیم سه عدد با باقی مانده های متمایز از بین اعداد صحیح 1 تا 9 انتخاب کنیم. حال طبق اصل جمع جواب مسأله برابر است با
شکل زیر یک جدول با 33 نقطه را نشان می دهد. می خواهیم با استفاده از حرکت های مورب (مانند شکل زیر) از نقطه ی گوشه ی سمت چپ و پایین به نقطه ی گوشه ی سمت راست و پایین برویم. توجه کنید که با هر حرکت مورب فقط می توان به سمت راست شکل رفت. این کار به چند طریق ممکن است؟
الف) ب) ج) د) ه)
حل. گزینه ه صحیح است. نقاط سطر دوم را به ترتیب بنامید. هر مسیری از نقطه ی گوشه ی سمت چپ و پایین (نقطه ی ) به نقطه گوشه ی سمت راست و پایین (نقطه ) از نقاط می گذرد (چرا؟). از هر یک از نقاط می توانیم هم به سمت راست پایین و هم به سمت راست بالا برویم. از نقطه هم باید به نقطه ی برویم. بنابراین طبق اصل ضرب تعداد مسیرهای مورد نظر از به برابر است با .
به چند طریق می توان از میان اعداد 1 تا 30، سه عدد متمایز انتخاب کرد، به طوری که تشکیل تصاعد هندسی دهند؟
الف) 6
ب) 10
ج) 11
د) 12
ه) 13
حل. گزینه د صحیح است. اگر تصاعد هندسی را به شکل نشان دهیم داریم: . پس به ازای هر ، دقیقاً تصاعد هندسی با قدر نسبت وجود دارد. پس طبق اصل جمع، تعداد کل تصاعد ها برابر است با: .
در طبقه بندی ریاضیات، اصول جمع و ضرب بسیار بدیهی هستند، و به همین دلیل اغلب توسط دانش آموزان، نادیده گرفته می شوند. ولی این دو اصل به واقع در حل مسایل شمارشی نقش اساسی دارند. به طوری که در این قسمت دیدیم، ممکن است یک مسأله را نتوان به راحتی حل کرد ولی با تقسیم آن مسأله به چند زیر مسأله ی کوچک تر وحل آن زیر مسأله ها و سپس ادغام جواب زیر مسأله‌ها، می توان جواب مسأله ی اصلی را به دست آورد.
از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..
وزارت آموزش و پرورش > سازمان پژوهش و برنامه‌ريزی آموزشی
شبکه ملی مدارس ایران رشد
که هیچ دو عضو متوالی ندارند، چقدر است؟»
را بتوان به 
پیشامد 
، تقسیم کرد به طوری که:
حالت برای اتفاق افتادن پیشامد 
،
حالت برای اتفاق افتادن پیشامد 
،
حالت برای اتفاق افتادن پیشامد 
،
.، یا 
به شهر
مسافرت کند. فرض کنید 3 راه برای سفر هوایی، 2 راه بری سفر زمینی و 2 راه برای سفر دریایی وجود داشته باشد. این شخص به چند طریق می تواند از شهر
، 
، ... و 
، 
داشته باشیم 
. آن گاه داریم:
، و 
به شهر 
برود. برای رفتن از شهر 
به شهر 
، باید طبق شکل زیر از شهرهای 
و 
عبور کرد. این شخص به چند طریق می تواند از شهر 
طریق می تواند از شهر 
یک عدد طبیعی و 
، 
، پس هر مقسوم علیه طبیعی 360 را می توان به صورت 
نوشت که در آن
را به 4 حالت، 
را به 3 حالت و 
را به 2 حالت می توان انتخاب کرد پس تعداد مقسوم علیه های طبیعی 360 برابر است با: 
.
باشد به طوری که 
ها اعداد اول متمایزی باشند (
را به حاصل ضرب عوامل اول تجزیه کرده ایم.) می دانیم عدد 
، مقسوم علیه عدد 
، 
می تواند هر یک از مقادیر 
را بگیرد. بنابراین طبق 
یک «دنباله در مبنای 
باشد. به تعداد جملات یک دنباله طول آن دنباله می گویند. به عنوان مثال 
مجموعه ی تمام دنباله های به طول 2 در مبنای 2 می باشد.
را از مجموعه‌ی 
، انتخاب کرد. به طریق مشابه، هر یک از جمله های 
را نیز به 
، همچنین تعداد متغیرهای به طول چهار برابر است با 
. بنابراین طبق اصل جمع تعداد متغیرهای به طول حداکثر 4 برابر است با:
.
از اعداد صحیح را بیابید به طوری که 
. (دقت کنید که 
با 
، تفاوت دارد.)
. حال مسأله را براساس مقدار 
به سه قسمت زیر تقسیم می کنیم:
، در این حالت به نامعادله ی 
می رسیم که 5 جواب 
دارد. پس تعداد زوج مرتب هایی که مؤلفه ی اول آنها صفر است برابر 5 می باشد.
، در این حالت به نامعادله ی 
می رسیم که 5 جواب 
است برابر 
می باشد (خود 
، در این حالت به نامعادله ی 
می رسیم که 3 جواب 
دارد. پس تعداد زوج مرتب هایی که مؤلفه ی اول آنها 
است برابر 
می باشد (خود 
منهای تعداد زوج مرتب هایی که 
.
و 
) می توانند انتخاب شوند؛ پس تعداد زوج مرتب هایی که 
.
. پس تعداد زوج مرتب هایی که 
. در نتیجه جواب مسأله برابر است با 
.
باشد. آنگاه:
صدق می کند. (مسابقات ریاضی پاتنام، 1960)
.
باشد 
، آن گاه 
و 
. (دقت کنید که چون x و y باید اعداد طبیعی باشند، جواب 
و 
مورد قبول نمی باشد.) در نتیجه به ازای هر تجزیه ی 
به حاصل ضرب دو عدد طبیعی یک جواب یکتا برای زوج مرتب 
به دست می آید. ولی تعداد راه های تجزیه ی 
باشد، جواب مسأله برابر است با 
.
عمود بر محور 
عمود بر محور 
ها و 3 لایه ی 
عمود بر محور 
ها را در نظر بگیرید. در هر یک از این 9 لایه 2 مجموعه ی سه تایی وجود دارد که قطرهای آن لایه را می سازند. پس پاره خط های سه تایی به طول 
(قطرهای فرعی) برابر 
می باشد. همچنین موازی هر یک از محورهای مختصات (محور 
خط موازی محورهای مختصات وجود دارد که از سه تا از این نقاط می گذرند. همچنین از به هم پیوستن دو به دوی 8 نقطه ی وسط مکعب های گوشه ای مکعب که در یک وجه نیستند و نقطه ی داخل 
وسطی (قطرهای اصلی) 4 پاره خط به وجود می آید که از سه تا از این نقاط می گذرد. پس مجموعاً 
پاره خط با شرایط مورد نظر وجود دارد.
بر 3، برابر 1، باقی مانده ی مجموعه ی 
بر 3، برابر 2 و باقی مانده‌ی اعضای مجموعه ی 
بر 3، برابر است. در حالت اول به سه طریق می توان این اعداد را انتخاب کرد. در حالت دوم به سه حالت می توانیم یکی از اعضای 
طریق می توانیم سه عدد با باقی مانده های متمایز از بین اعداد صحیح 1 تا 9 انتخاب کنیم. حال طبق اصل جمع جواب مسأله برابر است با 
با 33 نقطه را نشان می دهد. می خواهیم با استفاده از حرکت های مورب (مانند شکل زیر) از نقطه ی گوشه ی سمت چپ و پایین به نقطه ی گوشه ی سمت راست و پایین برویم. توجه کنید که با هر حرکت مورب فقط می توان به سمت راست شکل رفت. این کار به چند طریق ممکن است؟
بنامید. هر مسیری از نقطه ی گوشه ی سمت چپ و پایین (نقطه ی 
می گذرد (چرا؟). از هر یک از نقاط 
می توانیم هم به سمت راست پایین و هم به سمت راست بالا برویم. از نقطه 
هم باید به نقطه ی 
.
نشان دهیم داریم: 
. پس به ازای هر 
، دقیقاً 
تصاعد هندسی با قدر نسبت 
وجود دارد. پس طبق اصل جمع، تعداد کل تصاعد ها برابر است با: 
.