جزوه دوره آمار و احتمال دکتر علی شریفی - جلسه اول - ترکیبیات و شمارش

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

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

آمار و احتمال

آمار و احتمال یکی از پایه‌ای ترین مباحث هست که معمولاً در همه جا بهش نیاز خواهیم داشت. بیاید با یه سوال پیش پا افتاده بحث رو شروع کنیم. فرض کنید یک مسابقه تلویزیونی وجود داره و هزینه شرکت در مسابقه 5000 تومان هست و 1 میلیون نفر شرکت کننده هم در مسابقه وجود دارن. در صورتی که مسابقه رو ببریم، 50 میلیون تومان بعنوان جایزه دریافت خواهیم کرد. حالا، چه کنیم؟ شرکت کنیم یا نکنیم؟ اصلاً جایزه چه قدر باشه می‌صرفه برامون که شرکت کنیم؟ بریم با آمار و احتمال تحلیل کنیم!

احتمال اینکه مسابقه رو برنده بشیم چقدره؟ 1 بر روی 1 میلیون. یعنی چی؟ یعنی احتمال اینکه 50 میلیون رو ببریم برابر هست با 1 بر روی 1 میلیون. پس یعنی چقدر از 50 میلیون گیرمون میاد؟ در واقع، 50 تک تومن! چجوری حساب شد؟ اینجوری: 50,000,000 × (1/1,000,000) = 50

حالا، هزینه شرکت در مسابقه چقدر بود؟ 5000 تومان. پس به صورت میانگین، با شرکت در مسابقه داریم 4950 تومان ضرر می‌کنیم. چون داریم 5000 تومان بعنوان هزینه میدیم ولی در عوض چیزی که گیرمون میاد 50 تومان هست. پس با شرکت در این مسابقه داریم 4950 تومان از دست می‌دیم!

حالا بریم سراغ یه مسئله ساده دیگه. فرض کنید یک جلسه مهمی داریم و برای رسیدن به جلسه دو راه داریم. می‌تونیم با تاکسی خطی بریم و 7 هزار تومان کرایه بدیم و یا با تاکسی دربست بریم و 30 هزار تومان بپردازیم. احتمال رسیدن با تاکسی خطی 50 درصده و با تاکسی دربست 100 درصد محتمله که برسیم. همچنین، در صورتی که جلسه رو از دست بدیم 50 هزار تومن ضرر می‌کنیم. حالا، چه کنیم؟ با کدوم بریم؟ باید Expected حساب کنیم.

اگه با تاکسی خطی بریم 7 هزار تومان کرایه دادیم، از طرفی با احتمال 50 درصد یک ضرر 50 هزار تومانی خواهیم داشت. یعنی مجموعاً 7000 + 50000 × (1/2) = 32000 تومان ضرر خواهیم کرد. ولی اگه با تاکسی دربست بریم، فقط 30 هزار تومان کرایه دادیم بدون هیچ ضرر اضافه‌ای. حالا کدوم بهتره؟ منطقاً تاکسی دربست! چون زیانش کمتره.

خلاصه، آمار و احتمال خیلی کاربردیه و در تمام مسائل عادی و پیش پا افتاده در زندگی هم به کار میاد.

کوییز

حالا، قراره در قالب یک کوییز دانش قبلی‌مون از مباحث شمارش و ترکیبیات و احتمال رو محک بزنیم. در ادامه‌ی هر سوال جوابش هم آورده شده. اگه تمایل داشتین که بدونید از قبل چقدر بلدین، قبل دیدن جواب‌ها، خودتون جواب مسائل رو حساب کنید.

سوال اول

جواب سوال اول

با 5 راه مختلف از سمرقند می‌رسیم به بخارا. مستقل از اینکه چجوری از سمرقند به بخارا برسیم، برای رسیدن به بلخ از بخارا 2 راه وجود داره. پس در کل میشه 5 × 2 راه مختلف که می‌تونه مارو از سمرقند به بلخ برسونه. به این روشی که برای حل این مسئله در پیش گرفتیم، اصل ضرب گفته میشه. شرط اینکه بشه از اصل ضرب برای حل مسائل استفاده کرد اینکه کارهایی که دارن انجام میشن مستقل از هم دیگه باشن. مثلاً، 3 تا پیراهن مختلف داریم و 3 تا شلوار مختلف. در کل 3 × 3 راه مختلف وجود داره برای ست کردن و پوشیدن پیراهن و شلوارها. ولی اگه محدودیت بذاریم که مثلاً شلوار قرمز رو نخوایم با لباس آبی بپوشیم، اون موقع دیگه نمیشه از اصل ضرب استفاده کرد. چون انتخاب پیراهن به انتخاب شلوار مرتبط میشه و دیگه از هم دیگه مستقل نخواهند بود.

سوال دوم

جواب سوال دوم

منطقاً اولین رقم از سمت چپ نمی‌تونه 0 باشه، پس 9 تا رقم خواهیم داشت. ارقام وسط هر کدوم بین 0 تا 9 هستن، پس 10 حالت دارن. رقم یکان هم چون قراره فرد باشه پس 5 حالت داره. پس مجموعاً میشه 45 هزار حالت.

سوال سوم

توجه داشته باشید که هیچ کدام از گزینه‌های این سوال درست نیست.

جواب سوال سوم

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

اگه از سمت راست شروع کنیم به پر کردن ارقام، بازم به مشکل می‌خوریم. چون نمی‌دونیم تو ارقامی که تا حالا در نظر گرفته شده 0 اومده یا نه.

برای اینکه بتونیم از اصل ضرب برای حل این سوال استفاده کنیم باید بیایم اول یکان رو پر کنیم و بعد بریم سراغ چپ‌ترین رقم. چپ‌ترین رقم 0 نمی‌تونه باشه و چون از قبل یکان رو هم پر کردیم پس در کل 8 حالت داره. بعد، میشه به راحتی ارقام وسط رو پر کرد و مسئله حل میشه. جواب نهایی میشه 13440.

سوال چهارم

جواب سوال چهارم

این سوال هم با اصل ضرب قابل حله. جواب نهایی میشه 120 که معادل هست با 5 فاکتوریل.

سوال پنجم

جواب سوال پنجم

جای یک میهمان را فیکس در نظر می‌گیریم و بقیه را دور آن می‌چینیم. پاسخ برابر با 24 خواهد بود.

سوال ششم

جواب سوال ششم

جواب سوال میشه 60. 3 جایگاه داریم و 5 تا بچه.

به مسائل این چنینی محاسبه جایگشت‌های r عضوی از n عضوی گفته میشه. به صورت کلی میشه مسئله رو اینطور تعریف کرد: n شی داریم، چند جایگشت با r شی از بین آن‌ها خواهیم داشت؟ جواب این مسئله به صورت P(n, r) مشخص میشه. یعنی، تعداد جایگشت‌های r تایی از یک مجموعه n تایی که معادل میشه با !(n-r)/!n. به همین ترتیب در این مسئله داریم P(5, 3) که معادل هست با !2/!5.

سوال هفتم

جواب سوال هفتم

جواب میشه 455. حالا ببینیم که چطور محاسبه میشه. تو این سوال همه افراد سرودخوان باهم یکی هستن و فرقی بینشون نیست. در واقع می‌خوایم یک مجموعه انتخاب کنیم و افراد یا عضو اون مجموعه هستن یا نیستن. یعنی، می‌خوایم تعداد انتخاب‌ها یا ترکیب‌ها رو در این سوال بشمریم. تعداد ترکیب‌های n عضو از r عضو که معادل هست با C(n, r) که داره تعداد زیرمجموعه‌های r عضوی از یک مجموعه n عضوی رو بهمون نشون میده و ترتیب اینجا برامون مهم نیست. برای C(n, r) داریم: P(n, r)/!r که معادل هست با (!n!/((n-r)!r. تو این سوال n معادل هست با 15 و r برابر هست با 3. اگه علاقه‌مند هستین که در مورد رابطه ترکیب بیشتر بدونید، پیشنهاد می‌کنم به دقیقه 30 از ویدیو این جلسه مراجعه کنید.

حالا یه سوال، C(20, 0) داره چیو نشون میده؟ داره میگه تعداد حالت‌هایی رو به من بده که من بتونم از یک مجموعه 20 حالتی، مجموعه تهی رو انتخاب کنم. پس جواب میشه 1. از اینجا میشه نتیجه گرفت که !0 برابر هست با 1.

حالا یه سوال دیگه، بین C(20, 5) و C(20, 15) چه رابطه‌ای هست؟ به صورت شهودی اگه بخوایم بگیم، اینطور میشه که انگار 20 نفر رو داریم، قراره یک گروه سرود 5 نفره از بینشون تشکیل بدیم. یا بیایم از بین 20 نفر 5 نفر رو انتخاب کنیم برای گروه سرود، یا بیایم 15 نفر رو از 20 نفر بذاریم کنار تا 5 نفر باقی‌مونده انتخاب بشن. پس باهم دیگه یکی هستن.

سوال هشتم

جواب سوال هشتم

جواب این سوال با استفاده از ترکیب و انتخاب به دست میاد. در کل 10 گام باید برداریم تا از مبدا به مقصد برسیم. 6 گام در جهت افقی هست و 4 گام در جهت عمودی. پس جواب میشه C(10, 6) = C(10, 4) که نهایتاً میشه 210. یعنی انگار زیر مجموعه‌هایی رو می‌خوایم که در اون گام‌ها به نحوی باشن که 4 تا گام عمودی وجود داشته باشه و 6 تا گام افقی.

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

تو این حالت تعداد کل مسیرهایی که مارو از مبدا به مقصد می‌رسونه برابر هست با 210 تا. حالا باید بیایم حالت‌هایی که باعث میشه از نقطه وسط بگذریم رو حساب کنیم و در نهایت از تعداد کل مسیرها کم کنیم. مسیرهایی که از نقطه قرمز رنگ رد میشه برابر هست با مسیرهایی که از نقطه شروع به نقطه قرمز می‌رسه، در تعداد مسیرهایی که از نقطه قرمز شروع و به نقطه پایانی میرسه. شبیه همون مسئله اول می‌مونه. با استفاده از اصل ضرب قابل محاسبه‌ست. می‌خوایم از نقطه شروع حرکت کنیم و به نقطه قرمز برسیم. چند حالت داریم؟ در کل میشه C(5, 3) حالت که 10 تاست. حالا می‌خوایم از نقطه قرمز شروع کنیم به حرکت و به نقطه پایان برسیم. چند حالت داریم؟ بازم میشه 10 حالت. پس چند تا مسیر داریم که باعث میشه از نقطه قرمز رنگ عبور کنیم؟ 10 × 10 تا. حالا جواب نهایی این مسئله چی میشه؟ 100 - 210 که میشه 110 مسیر.

سوال نهم

جواب سوال نهم

میشه این مسئله رو شبیه مسئله قبلی کرد و با کشیدن شکل حلش کرد. سه تا متغیر داریم که می‌تونن معادل بشن با سه تا خط عمودی. جواب مسئله قراره بشه 15 که می‌تونه معادل بشه با 16 تا خط افقی. تعداد اعداد 0 تا 15 میشه 16 تا چون صورت سوال گفته اعدادمون صحیح و نامنفی هستن. پس شکل مورد نظر به صورت زیر میشه:

اگه جوابی به صورت 5 + 6 + 4 باشه میشه به صورت زیر نشونش داد:

پس خیلی ساده شد الان. جواب مسئله میشه C(17, 2) که برابر هست با 136.

سوال دهم

جواب سوال دهم

چند تا عدد از 1000 عدد بر 5 بخش‌پذیر هستند؟ میشه کف 1000/5 که 200 تا میشه. پس تا اینجا باید از 1000 تا عدد 200 تا رو کم کنیم و 800 تا عدد باقی می‌مونه. حالا، چند تا عدد از 1000 عدد بر 3 بخش‌پذیر هستن؟ 333 تا عدد میشه. از 800 تا عدد باقی‌مونده 333 عدد رو هم کم می‌کنیم. تا اینجا 467 تا عدد باقی‌ مونده. ولی تا اینجا یک سری اعداد رو دو بار کم کردیم. کدوم عددهارو؟ عددهایی که هم بر 3 بخش پذیر هستن و هم بر 5. یعنی در واقع عدد هایی که بر 15 بخش‌پذیر هستن و میشه 66 تا عدد. چیکار کنیم که مشکل حل شه؟ 66 تا عدد رو یک بار دیگه اضافه کنیم به 467 عدد. پس جواب این مسئله میشه 533. به این قاعده میگن اصل شمول و عدم شمول. بریم یه سوال دیگه رو با این قاعده بررسی کنیم.

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

تعداد کل مسیرها از نقطه مبدا تا نقطه مقصد میشه C(11, 6) = 462 تا مسیر. حالا تعداد مسیرهایی که از نقطه مبدا شروع میشن و از نقطه قرمز اول رد میشن و به نقطه انتهایی می‌رسن برابر هست با C(4, 1) × C(7, 3) که برابر هست با 140. بعد، تعداد مسیرهایی که از مبدا شروع میشن و از نقطه قرمز دوم رد میشن و به نقطه مقصد می‌رسن برابر میشه با C(7, 3) × C(4, 2) که برابر هست با 210 تا. حالا، تعداد مسیرهایی که از مبدا شروع میشن و از هر دو نقطه قرمز عبور می‌کنن و به مقصد می‌رسن، برابر هست با C(4, 1) × C(3, 1) × C(4, 2) که معادل هست با 72. حالا برای به دست آوردن جواب باید بیایم تعداد کل مسیرهارو منهای تعداد مسیرهایی کنیم که از یکی از نقاط قرمز رد میشه و در نهایت جمع کنیم با تعداد مسیرهایی که از هر دو نقطه قرمز می‌گذره. یعنی:

The Answer: 462 - (140+210) + 72 = 184

پس جواب مسئله 184 هست.

حالا اگه بخوایم اصل شمول و عدم شمول رو توضیح بدیم برای مجموعه دوتایی به این صورت میشه:

|A U B| = |A| + |B| - |A ∩ B|

در واقع این رابطه داره میگه که بیا اندازه مجموعه A رو که میشه قسمت نارنجی + قسمت قرمز جمع کن با اندازه مجموعه B که میشه قسمت زرد + قسمت قرمز. بعد چون قسمت قرمز دو بار در محاسبات آورده شده یک بار کمش کن تا جواب نهایی درست بشه و بتونی اندازه A و B رو داشته باشی.

و برای مجموعه سه تایی به صورت زیر تعریف میشه:

|A U B U C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

در اینجا هم داره میگه بیا اول اندازه مجموعه‌های A و B و C رو به صورت جدا باهم جممع کن که میشه:

مجموعه A = قسمت نارنجی + قسمت قرمز + قسمت آبی + قسمت خاکستری

مجموعه B = قسمت زرد + قسمت قرمز + قسمت بنفش + قسمت خاکستری

مجموعه C = قسمت سبز + قسمت آبی + قسمت بنفش + قسمت خاکستری

بعد بیا قسمت‌های تکراری رو که دو بار محاسبه کردی از حالت قبلی کم کن یعنی:

قسمت قرمز + قسمت خاکستری

قسمت آبی + قسمت خاکستری

قسمت بنفش + قسمت خاکستری

حالا چون قسمت خاکستری کلا از بین رفت، پس در نهایت باید بیایم یک بار دیگه قسمت خاکستری رو اضافه کنیم که بتونیم اندازه کلی A و B و C رو باهم داشته باشیم.

جمع‌بندی مطالب ارائه شده

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

اگر جایی ایراد یا مشکلی بود، حتما بهم بگید تا تصحیحش کنم.

ویدیو این جلسه

صفحه گیت‌هاب مرتبط با این دوره

جزوه جلسه بعدی (جلسه دوم)