اصل شمارش (۱- اصل ضرب و اصل جمع)
آنچه در این مقاله میخوانید
Toggleمقدمه اصل شمارش
هدف اصلی ما در این قسمت از وبلاگ تاتوره بیان اصل شمارش است. گرچه در نظر اول شمردن کاری ابتدایی و آسان جلوه میکند، اما گاهی با مسائلی در نهایت پیچیدگی و شاید هیجان انگیز برخورد میکنیم. هدف اصلی آنالیز ترکیبی ارائه روشهای شمارش و تعیین تعداد حالات ممکن پیشامدها بدون شمارش هر یک از حالات است. اصول چندگانه ای در این رابطه وجود دارد که در این قسمت به اصل ضرب و مثال های متعددی از آن (۱۱ مثال) می پردازیم. پس با ما همراه باشید.
اصل ضرب
اصل ضرب یکی از اصول چندگانه اصل شمارش است. در بسیاری از موارد، سؤالاتی از نوع «به چند طریق میتوان…؟» مطرح میشود. یعنی از ما میخواهند که تعداد حالات ممکن را تعیین کنیم. مثلا فرض کنید میخواهیم بدانیم «به چند طریق میتوان سه نفر به نامهای A.B,C را در یک صف قرار داد؟» حالات مختلف قرار گرفتن این سه نفر در یک صف بصورت زیر است:
\({\rm{ABC}},{\rm{\;ACB}},{\rm{\;BCA}},{\rm{\;BAC}},{\rm{\;CAB}},{\rm{\;CBA}}\)
که در آن منظور از ACB، یعنی افراد A,C,B به ترتیب در ردیف اول، دوم و سوم صف قرار دارند. اگر به جای سه نفر بخواهیم با ۶ نفر این صف را تشکیل دهیم، در اینصورت نوشتن حالات مختلف کاری سخت و طاقت فرسا خواهد بود. همان طور که بعدها خواهیم دید، میبایست ۷۲۰ حالت مختلف را نوشت. برای ۱۰ نفر تعداد حالات ممکن برابر است با ۳۶۲۸۸۰۰، اما برای محاسبه تعداد حالات قرار دادن ۱۷ نفر در یک صف با اعداد نجومی سر و کار داریم.
برای این کار، فرض کنید به یک کامپیوتر با سرعت نسبتاً زیاد، برنامه ای بدهیم که حالات مختلف مرتب کردن ۱۷ نفر در یک صف را نوشته و تعداد آنها را بشمارد. اگر این کامپیوتر در هر ثانیه ۵۰۰۰۰ تا از این حالات را ساخته و بشمارد، مدت زمان شمارش و چاپ حالات ممکن چیزی بیش از مدت عمر یک انسان است، و اگر از این کامپیوتر بخواهیم همین عمل را برای ۲۶ نفر انجام دهد، زمانی بیش از صد تریلیون سال برای انجام این کار باید صرف کرد. بنابراین ناگزیر روش دیگری برای شمارش اتخاذ کنیم. در واقع در جستجوی شیوه ایی هستیم بطوری که بدون نوشتن حالات مختلف بتوان تعداد حالات ممکن را تعیین کرد. برای شروع قضیه زیر را که به اصل اساسی شمارش یا اصل ضرب موسوم است در زیر میآوریم.
قضیه۱:
فرض کنید عملی را میتوان به m طریق انجام داد. اگر به ازای هر یک از روش هایی که عمل اول را میتوان انجام داد، به دنبال آن عمل دوم به n طریق بتواند انجام گیرد. آنگاه m×n طریق مختلف برای انجام توأم این در عمل وجود دارد.
اثبات:
اگر حالات مختلف انجام عمل اول را با \({a_1},{\rm{\;}}{a_2},{\rm{\;}}.{\rm{\;}}.{\rm{\;}}.{\rm{\;}},{\rm{\;}}{a_m}\) و حالات مختلف انجام عمل دوم را با \({b_1},\;{b_2}\;,\;.\;.\;.\;.\;,\;{b_n}\) نشان دهیم، با توجه به نمودار زیر میتوان حالات ممکن را شمرد.
باید توجه کرد که در مسائلی میتوان قضیه اساسی شمارش را به کاربرد که واجد شرایط زیر باشد:
- به ازای هر یک از \(m\;\) روشی که عمل اول انجام میشود، عمل دوم را مستقلاً بتوان انجام داد.
- کلمه «مستقلاً» در اینجا بسیار مهم است و بیانگر آن است که تعداد حالات انجام عمل دوم به روشی که عمل اول انجام شده بستگی نداشته باشد.
مثال۱:
حال اولین مثال از اصل ضرب یا اصل شمارش را بیان میکنیم. فرض کنید میخواهیم کمیته ای متشکل از یک مرد و یک زن تشکیل دهیم. برای این کار چهار مرد \({m_3} – \;{m_2} – \;{m_1}\) و \({m_4}\) و سه زن \({w_1} – \;{w_2} – \;{w_3}\) نامزد شدهاند. برای شمردن تعداد حالات ممکن برگزیدن یک زن و یک مرد با چند عمل سر و کار داریم؟
حل مثال۱:
عمل اول: انتخاب یک مرد.
عمل دوم: انتخاب یک زن.
برای انجام عمل اول ۴ طریق وجود دارد، در صورتی که عمل دوم را به ۳ روش میتوان انجام داد و انتخاب هم به گونه ای است که به ازای هر یک از چهار حالتی که عمل اول انجام میشود، به دنبال آن و مستقل از نحوه انجام عمل اول، عمل دوم را به سه روش میتوان انجام داد.
برای روشن شدن این مطلب، فرض کنید به عنوان مثال آقای \({m_1}\) انتخاب شده است، در اینصورت برای انجام عمل دوم یعنی انتخاب یک زن، هر یک از خانم های \({{\rm{w}}_1}\)، \({{\rm{w}}_2}\) و \({{\rm{w}}_3}\)را میتوان برگزید. این مطلب در نمودار زیر آورده شده است.
به همین طریق، اگر آقای \({m_2}\) انتخاب شود، هر یک از خانم های \({{\rm{w}}_1}\)، \({{\rm{w}}_2}\) و \({{\rm{w}}_3}\) را میتوان انتخاب کرد. یعنی داریم:
بنابراین در مورد این مسأله شرط مستقل بودن برقرار است. لذا میتوان قضیه را به کار برد و نتیجه گرفت که تعداد حالات انتخاب یک زن و یک مرد برابر است با ۱۲ = ۳ × ۴
حال به مثالی توجه کنید که در آن نمیتوان از قضیه اساسی شمارش استفاده کرد.
مثال۲:
میخواهیم از میان چهار پیراهن آبی، مشکی، سبز و صورتی و سه کت مشکی، سفید و قهوه ای، یک کت و یک پیراهن انتخاب کرده مشروط به آن که کت و پیراهن همرنگ نباشند. به چند طریق میتوان این کار را انجام داد؟
حل مثال۲:
نخست یک پیراهن انتخاب میکنیم، برای این کار ۴ روش وجود دارد، بعد از اینکه عمل اول یعنی انتخاب پیراهن انجام شد، عمل دوم بستگی دارد به اینکه کدام یک از حالات عمل اول را انجام داده ایم. برای مثال : اگر پیراهن آبی را انتخاب کرده باشیم، برای انجام عمل دوم (انتخاب یک کت) سه طریق وجود دارد. به نمودار زیر توجه کنید:
اما اگر پیراهن مشکی را انتخاب کنیم، برای انجام عمل دوم با توجه به شرط داده شده در مسئله فقط دو طریق وجود دارد یعنی داریم:
بنابراین در اینجا شرط مستقل بودن برقرار نیست لذا نمیتوان از قضیه اساسی شمارش استفاده کرد.
تعمیم اصل ضرب
اگر عمل اول بتواند به \({m_1}\) طریق انجام گیرد و پس از آن عمل دوم را مستقل از نحوه انجام عمل اول بتوان به \({m_2}\) طریق انجام داد، و به همین طریق عمل سوم به\({m_3}\) طریق و… و بلاخره عمل \(k\) ام مستقل از نحوه انجام عمل \(\left( {k\;–\;1} \right)\) ام به \(m{\;_k}\) طریق انجام گیرد، آنگاه این اعمال را به\(\;{m_1} \times \;{m_2} \times \ldots \times {m_k}\;\)طریق مختلف میتوان انجام داد.
مثال۳ :
ارقام ۱، ۲، ۳، ۴، ۵، ۶، ۷، داده شده اند.
الف) با این ارقام چند عدد ۳ رقمیمیتوان ساخت به شرطی که اعداد حاصل دارای ارقام تکراری نباشند.
ب) با این ارقام چند عدد ۳ رقمیمیتوان ساخت هرگاه تکرار ارقام مجاز باشد.
پ) با این ارقام چند عدد ۳ رقمیفرد میتوان ساخت که دارای ارقام تکراری نباشند.
حل مثال۳:
الف) برای ساختن یک عدد ۳ رقمی بدون ارقام تکراری سه عمل زیر را میبایست انجام داد:
۱- انتخاب یک عدد از میان ۷ عدد و قرار دادن آن در رقم یکان.
۲- انتخاب یک عدد برای رقم دهگان. چون عدد حاصل نباید دارای ارقام تکراری باشد، لذا برای انجام عمل دوم باید از میان شش عدد باقیمانده یکی را برگزید و در رقم دهگان قرار داد.
۳- انتخاب یک عدد برای رقم صدگان. تا به حال دو عدد از میان هفت عدد را برای رقم یکان و دهگان به کار برده ایم، بنابراین برای انجام عمل سوم، عملاً باید از میان پنج عدد باقیمانده یکی را انتخاب کرد، بنابراین عمل اول را به هفت روش، عمل دوم را به شش روش و عمل سوم را به پنج روش میتوان انجام داد، و شیوه انجام سه عمل به گونه ای است که وقتی از هر طریقی عمل را انجام دادیم، تأثیری در تعداد روش های انجام عمل بعدی ندارد، یعنی این مسئله واجد شرط استقلال است. بنابراین تعداد حالت های ممکن، یعنی تعداد اعداد سه رقمی بدون ارقام تکراری که با این هفت عدد میتوان ساخت برابر است با: ۲۱۰ = ۵ × ۶ × ۷
ب) در این حالت اعداد حاصل میتوانند دارای ارقام تکراری باشند. بنابراین تعداد روشهای انجام هر سه عمل یکسان است. پس تعداد حالت های ممکن برابر است با: ۳۴۳ = ۷ × ۷ × ۷
پ) میخواهیم عدد فردی را با استفاده از اعداد ۱، ۲، ۳، ۴، ۵، ۶، ۷ بسازیم.
برای رقم یکان فقط میتوان اعداد ۱، ۳، ۵ و ۷ را مورد استفاده قرار داد. پس عمل اول میتواند به چهار طریق انجام گیرد. برای انجام عمل دوم یعنی انتخاب رقم دهگان، همه اعداد را میتوان انتخاب کرد به جز عددی که برای رقم یکان به کار بردهایم (زیرا تکرار مجاز نیست)، پس عمل دوم را به شش طریق میتوان انجام داد. به همین ترتیب برای انجام عمل سوم پنج طریق وجود دارد. در نتیجه، با توجه به قضیه اساسی شمارش تعداد حالات ممکن برابر است با ۱۲۰ = ۵ × ۶ × ۴ طریق. یعنی ۱۲۰ عدد سه رقمیفرد بدون ارقام تکراری با اعداد ۱ تا ۷ میتوان ساخت.
تذکر مهم:
برای ساختن یک عدد سه رقمیدر قسمت «الف» و «ب»، میتوانیم عمل اول را با انتخاب عددی برای رقم صدگان (رقم از سمت چپ) و عمل دوم را انتخاب عددی برای رقم دهگان و بلاخره عمل سوم را انتخاب عددی برای رقم یکان اختیار کرد.
اما در مورد ساختن اعداد سه رقمیفرد در قسمت (پ)، الزاماً میبایستی از رقم یکان شروع کنیم. در چنین حالتی که میبایست عملی را به طریق خاصی انجام داد، لازم است نخست آن عمل را انجام داد. در مورد سایر اعمال، ترتیب انجام دادن آنها اغلب اختیاری است.
مثال۴:
انجمن تئاتر دانشکده برای نمایش بهاره تمرین میکند. از شش مرد و هشت زن برای اجرا در نقش اصلی مرد و زن آزمایش به عمل میآید. بنابر اصل ضرب، مدیر میتواند زوج اجرا کننده در نقش اصلی را به ۴۸ = ۸ × ۶ روش انتخاب کند.
مثال۵:
چند پلاک نمره خودرو ۷ شماره ای که سه شماره اول آن حروف الفبای لاتین و چهار شماره آخر آن از ارقام ۰ تا ۹ تشکیل شده است میتوان تهیه کرد.
حل مثال۵:
۱۷۵۷۶۰۰۰۰ \( = \)۱۰ × ۱۰ × ۱۰ × ۱۰ × ۲۶ × ۲۶ × ۲۶
مثال۶:
در مثال ۵ چند نمره پلاک خودرو میتوان تهیه نمود، اگر تکرار حروف و ارقام مجاز نباشد.
حل مثال۶:
۶۲۴۰۰۰ \( = \) ۷ × ۸ × ۹ × ۱۰ × ۲۴ × ۲۵ × ۲۶
مثال۷:
اتومبیل A در ۴ مدل، ۱۲ رنگ، ۳ حجم موتور و ۲ نوع دنده به بازار میآید.
الف) چند نوع اتومبیل A متمایز ساخته میشود؟
ب) اگر یکی از رنگ ها آبی باشد، چند اتومبیل A آبی رنگ مختلف ساخته میشود؟
ج) اگر یکی از حجم های موتور \({\rm{V}}\_8\) باشد، چند اتومبیل A آبی رنگ متمایز با حجم موتور \({\rm{V}}\_8\) ساخته میشود؟
حل مثال۷:
الف) ۲۸۸ \( = \) ۲ × ۳ × ۱۲ ×۴
ب) ۲۴\( = \)۲ × ۳ × ۱ × ۴
پ) ۸ \( = \) ۲×۱ × ۱ ×۴
مثال۸:
۵ نوع پاکت، ۴ نوع تمبر هم ارزش مختلف داریم. به چند طریق میتوان پاکتها را تمبردار کرد؟
حل مثال۸:
با توجه به قانون ضرب داریم: \(۵ \times 4 = 20\)
مثال۹:
۵ جاده به قله کوهی میروند. یک کوهنورد به چند طریق میتواند بالا رفته و پایین بیاید؟ همین مسأله را در صورتی که رفتن و برگشتن از دو جاده مختلف باشد حل کنید.
حل مثال۹:
—کوهنورد میتواند یکی از ۵ جاده را انتخاب کند و بالا برود و یکی از ۴ جاده (زیرا از جاده ای که بالا رفته نمیتواند برگردد) را انتخاب کند و پایین بیاید. بنابر اصل ضرب ۲۰ \( = \)۴ × ۵ حالت برای بالا رفتن و پایین آمدن ممکن است.
— در حالتی که جاده دو طرفه باشد داریم: ۲۵\( = \)۵ × ۵ زیرا از همان جاده ای که بالا رفته میتواند پایین بیاید.
مثال۱۰:
یک کشاورز ۲۰ گوسفند و ۲۴ گاو دارد. به چند طریق میتواند یک گاو و یک گوسفند انتخاب کند؟ بعد از این انتخاب، مرتبه دوم به چند طریق امکان دارد؟
حل مثال۱۰:
۲۰ حالت برای انتخاب گوسفند و ۲۴ حالت برای انتخاب گاو داریم، بنابر اصل ضرب ۴۸۰ \( = \)۲۴ × ۲۰ حالت برای انتخاب یک گاو و یک گوسفند داریم.
در مرتبهی دوم چون در مرتبه ی اول یک گاو و یک گوسفند انتخاب شده است، لذا ۱۹ حالت برای انتخاب گاو و ۲۳ حالت برای انتخاب گوسفند داریم. بنابراین طبق اصل ضرب، ۴۳۷ \( = \) ۲۳ × ۱۹ حالت برای انتخاب گاو و گوسفند (برای مرتبه ی دوم) وجود دارد.
مثال۱۱:
شش جفت دستکش به اندازه های مختلف داریم، به چند طریق میتوان یک دستکش چپ و یک دستکش راست انتخاب کرد بطوری که از یک جفت نباشد.
حل مثال۱۱:
۶ حالت برای انتخاب یک دستکش چپ (راست) داریم، چون باید یک دستکش چپ و یک دستکش راست انتخاب کنیم که از یک جفت نباشند، بنابراین ۵ حالت برای انتخاب یک دستکش راست (چپ) وجود دارد، لذا بنابر اصل ضرب ۳۰ \( = \) ۵ × ۶ حالت برای انتخاب یک جفت دستکش چپ و راست که از یک جفت نباشند داریم.
بریم سراغ اصل جمع
اصل جمع
اکنون دومین اصل از اصول چندگانه اصل شمارش را مطرح میکنیم. دو عمل را که یکی به m طریق و دیگری به n طریق امکان انجام دارد را در نظر میگیرم. طبق اصل ضرب، اگر بعد از انجام عمل اول (به یکی از m طریق)، عمل دوم را بتوان به n طریق انجام داد، آنگاه m×n طریق مختلف برای انجام توأم آنها وجود دارد. (آنگاه این دو عمل را ناسازگار می گوییم.) در اینصورت برای محاسبه تعداد حالت های انجام عمل اول یا دوم از اصل جمع استفاده میکنیم. این اصل در قالب یک قضیه بدون اثبات آمده است.
قضیه:
اگر بتوان کاری را به m طریق و کار دیگری را به n طریق انجام داد، و نتوان این دو کار را همزمان انجام داد، آنگاه هر یک از دو کار را میتوان به یکی از راه انجام داد.
توجه کنید که وقتی میگوییم رویدادی خاص، نظیر کار مذکور در بالا که میتواند به m راه رخ دهد، فرض بر این است که این m راه از هم متمایز هستند مگر اینکه خلاف آن ثابت شود.
مثال ۱۲:
کتابخانه دانشکده ۴۰ کتاب درسی در زمینه اقتصاد کلان و ۵۰ کتاب درسی در زمینه اقتصاد خرد دارد. بنابر اصل جمع، یک دانشجوی این دانشکده برای کسب اطلاعات بیشتر درباره یکی از این دو موضوع میتواند کتابی را از بین ۴۰+۵۰=۹۰ کتاب درسی انتخاب کند.
حال که با مفهوم اصل ضرب و جمع در این قسمت آشنا شدید در مطلب آینده مبحث فاکتوریل و فرمول استرلینگ که زیر مجموعه اصل شمارش میباشند را توضیح خواهم داد. پس با هم به تاتوره بعدی می رویم.
سایت دیگر که در این رابطه آموزش داده است:
مطالب زیر را حتما مطالعه کنید
تابع چیست؟(قسمت دوم)+دامنه و برد + نمودار + 15 مثال
تابع چیست؟(قسمت اول) 16 مثال کامل + تعاریف و قضایا
50 مثال حل شده از اصل شمارش – جایگشت و ترکیب
ریاضی – مشتق و انتگرال توابع برداری – طول قوس – تابع طول قوس
ریاضی – معادلات خط و صفحه – خط در فضا – صفحه در فضا
ریاضی – بردار – بردار در فضا – خط در فضا – حاصل ضرب خارجی
2 دیدگاه
به گفتگوی ما بپیوندید و دیدگاه خود را با ما در میان بگذارید.
دیدگاهتان را بنویسید لغو پاسخ
برای نوشتن دیدگاه باید وارد بشوید.
Thanks
سلام خیلی عالی ، ممنون از زحمات شما بزرگواران .