شمارش و قواعد احتمال

شمارش و قواعد احتمال (counting & the rules of probability) جعبه‌ابزاری است که یک گزارهٔ کلامی دربارهٔ شانس را به عدد تبدیل می‌کند: نخست حالت‌هایی را که یک پیشامد می‌تواند رخ دهد می‌شماریم، سپس پیشامدها را با جبر کوچکی از قواعد ترکیب می‌کنیم. در رویکرد کلاسیک (لاپلاس) همهٔ برآمدهای فضای نمونه (sample space) $S$ هم‌شانس‌اند، پیشامد (event) $A$ زیرمجموعه‌ای از $S$ است و

پس تمام دشواری کار در درست شمردن $n(A)$ و $n(S)$ نهفته است. قواعد — قاعدهٔ جمع (addition rule)، قاعدهٔ متمم (complement rule)، احتمال شرطی (conditional probability)، قاعدهٔ ضرب (multiplication rule)، استقلال (independence) — همان چیزی‌اند که به شما اجازه می‌دهند احتمالی را که مستقیماً قابل شمارش نیست، از روی احتمال‌هایی که قابل شمارش‌اند به دست آورید.

۱. خاستگاه — Origin

نظریهٔ کلاسیک از نامه‌نگاری سال ۱۶۵۴ میان بلز پاسکال (Blaise Pascal) و پیر دو فرما (Pierre de Fermat) دربارهٔ مسئلهٔ امتیازها (problem of points) (تقسیم عادلانهٔ شرط‌بندی در بازی نیمه‌تمام) زاده شد: چگونه باید مبلغ شرط‌بندیِ بازیِ شانسی را که پیش از پایان قطع شده است تقسیم کرد. پاسخ آنان — وزن‌دهی به هر برآمد بر پایهٔ شمار حالت‌هایی که هنوز می‌تواند رخ دهد — دقیقاً همان تعریف «شمردن حالت‌های مطلوب» است که در بالا آمد. فن حدس‌زدن (Ars Conjectandi) اثر یاکوب برنولی (Jacob Bernoulli) در ۱۷۱۳ قانون اعداد بزرگ را افزود، لاپلاس (Laplace) در نظریهٔ تحلیلی احتمالات (۱۸۱۲) به تعریف کلاسیک شکل استاندارد آن را داد، قاعدهٔ توماس بیز (Thomas Bayes) برای وارون‌کردن یک احتمال شرطی پس از مرگ او (۱۷۶۳) منتشر شد، و آ. ن. کولموگروف (A. N. Kolmogorov) در ۱۹۳۳ کل این حوزه را بر پایه‌ای اصل‌موضوعی نشاند. برای کنکور تنها دو مورد آخر کاربرد عملی دارند: اصول موضوعهٔ کولموگروف تعیین می‌کند احتمال چیست، و قضیهٔ بیز راه استاندارد وارون‌کردن یک گزارهٔ شرطی است.

۲. ساختار — The structure itself

۲.۱ دو اصل شمارش

هر آنچه در ادامه می‌آید، کاربرد مکرر همین دو اصل است.

۲.۲ چهار فرمول پایهٔ شمارش

دو پرسش تعیین می‌کند به کدام فرمول نیاز دارید: آیا ترتیب مهم است؟ (does order matter?) و آیا تکرار مجاز است؟ (is repetition / replacement allowed?). برای انتخاب $r$ شیء از میان $n$ شیء:

این چهار مورد با یک اتحاد به هم پیوند می‌خورند که ارزش حفظ‌کردن دارد — یک انتخاب مرتب همان انتخاب نامرتب است که $r$ شیء برگزیده‌اش سپس چیده می‌شوند:

۲.۳ حالت‌های خاص استاندارد

اتحادهای پرکاربرد: $\binom{n}{r}=\binom{n}{n-r}$، قاعدهٔ پاسکال $\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}$، و $\sum_{r=0}^{n}\binom{n}{r}=2^{n}$.

۲ـ۴. تخصیص واحدهای یکسان با مقادیر متمایز

تخصیص صحیح (integer allocation) واحدهای یکسان را به دریافت‌کنندگان متمایز (labelled recipients) اختصاص می‌دهد. هر برآمد، بردار مقادیر است، نه انتخاب واحدهای متمایز: جابه‌جایی دو مقدار نابرابر میان دریافت‌کنندگان، تخصیص تازه‌ای می‌سازد. این کار را از صرفاً انتخاب مجموعهٔ نامرتبِ مقادیر جدا کنید.

فرض کنید تمام $N$ واحد باید به $k$ دریافت‌کننده تخصیص یابد، با کران صحیح مشترک $U$ و مقادیر دوبه‌دو متمایز:

مقادیر را به‌صورت $0\le a_1<a_2<\cdots<a_k\le U$ مرتب کنید. چون $a_i\ge i-1$:

نخست $U\ge k-1$ را بررسی کنید. حداکثر مجموع ممکن را نیز با استفاده از $k$ مقدار مجازِ بزرگ‌تر بررسی کنید:

اگر مجموع برابر حداقل باشد، تنها مجموعهٔ مقادیر $\{0,1,\ldots,k-1\}$ است: افزایش هر مقدارِ مرتب‌شده، مجموع را افزایش می‌دهد. برای دریافت‌کنندگان متمایز، این مجموعه $k!$ تخصیص می‌دهد. اگر مجموع بیش از حداقل باشد، فهرست‌های صعودی مجاز با رعایت مجموع و کران بالا را بشمارید، سپس هر فهرست را جایگشت دهید:

این ضریب، یکسان‌بودن کران‌ها برای همهٔ دریافت‌کنندگان را فرض می‌کند. برای محدودیت اختصاصی هر دریافت‌کننده، باید جایگشت‌های مجاز را بررسی کرد. برای مجموع‌های بزرگ‌تر، بنویسید $a_i=(i-1)+y_i$: مقادیر باقیمانده باید $0\le y_1\le\cdots\le y_k\le U-k+1$ و $\sum_i y_i=N-\frac{k(k-1)}{2}$ را رعایت کنند. قید ترتیب باقی می‌ماند؛ اینها متغیرهای نامقیدِ ستاره و میله نیستند.

مثال تازه. شش ژتون یکسان را میان چهار صندوق نام‌گذاری‌شده توزیع کنید؛ سهم هر صندوق عدد صحیحی از صفر تا چهار و هر چهار مقدار متمایز باشد. حداقل مجموع برابر است با

پس مقادیر دقیقاً $\{0,1,2,3\}$ هستند و

یک مجموعهٔ نامرتب، ۲۴ تخصیص به دریافت‌کنندگان متمایز می‌سازد. ستاره و میلهٔ معمولی $\binom{6+4-1}{4-1}=\binom{9}{3}=84$ می‌دهد، اما مقادیر برابر و مقادیر بیش از چهار را نیز شامل می‌شود. انتخاب $\binom{5}{4}=5$ مجموعهٔ مقادیر، مجموع آنها را نادیده می‌گیرد؛ فقط یک مجموعه مجموع شش دارد.

۲.۵ اصول موضوعه و قواعد احتمال

اصول موضوعهٔ کولموگروف: $0\le P(A)\le 1$، $P(S)=1$، و $P(A\cup B)=P(A)+P(B)$ هرگاه $A\cap B=\varnothing$. اصل جمع‌پذیری به تعداد شمارای پیشامدهای مجزا نیز تعمیم دارد؛ قواعد دیگر زیر از اصول موضوعه نتیجه می‌شوند:

قانون دمورگان پلی است که مسیر متمم را کارآمد می‌کند:

و برای $n$ پیشامد مستقل، $P(\text{at least one})=1-\prod_{i=1}^{n}\bigl(1-P(A_i)\bigr)$.

برای نتایج قبولی/رد مستقل، تنها قبول‌شدن فرد مشخص مستلزم قبولی او و ردشدن همهٔ دیگران است. فقط پس از تصریح استقلال، احتمال‌های حاشیه‌ای قبولی/رد را ضرب کنید؛ برای شرطِ دقیقاً یک قبول، بر مجموع احتمال حالت‌های مجزای تنهاقبول‌شدن تقسیم کنید. بدون استقلال، احتمال‌های توأم یا شاخه‌های شرطی لازم‌اند.

۳. طرز به‌کارگیری — How to apply it

الف) شمارش. چهار پرسش را به ترتیب پاسخ دهید تا فرمول خودش انتخاب شود:

1. آیا اشیا متمایزند؟ «شماره‌گذاری‌شده / متمایز» ⇒ بله. برای چیدمان انواع تکراری از $n!/(n_1!\cdots n_k!)$ استفاده کنید؛ توزیع واحدهای یکسان به بردار مقادیر و قواعد تخصیص بالا نیاز دارد.
2. آیا جایگاه اهمیت دارد؟ عبارت‌هایی که یک جایگاه را نام می‌برند — «مهرهٔ سوم»، «در یک ردیف»، «اول … سپس …»، رمز/شمارهٔ چند رقمی — شمارش را مرتب می‌کنند. کمیته، دستِ کارت و زیرمجموعه نامرتباند.
3. آیا جایگذاری وجود دارد؟ «با جایگذاری» ⇒ $n^{r}$؛ «بدون جایگذاری» ⇒ $P(n,r)$ یا $\binom{n}{r}$.
4. آیا محدودیتی هست؟ نخست جایگاه‌های مقیّد را پر کنید، سپس جایگاه‌های آزاد را با آنچه باقی مانده بشمارید. اگر محدودیت به موقعیت‌های ناسازگار تقسیم می‌شود، از اصل جمع روی حالت‌های مجزا استفاده کنید و بررسی کنید که حالت‌ها واقعاً مجزا و جامع باشند.

ب) احتمال. پیش از محاسبه، ترجمه کنید. پیشامدها را با حرف نام‌گذاری کنید و سپس هر عبارت فارسی را به یک نماد نگاشت کنید:

سپس کم‌هزینه‌ترین مسیر را برگزینید: اگر داده‌ها شاخهٔ «هیچ‌کدام» را توصیف می‌کنند، از راه متمم بروید؛ اگر داده‌ها زنجیره‌ای از مرحله‌هایند، در طول درخت ضرب کنید؛ اگر داده‌ها به تفکیک دسته داده شده‌اند، از احتمال کل استفاده کنید؛ و اگر پرسش شرطی‌سازیِ داده‌شده را وارون می‌کند، از بیز استفاده کنید.

۴. مثال حل‌شده — Worked mini-example

یک محموله شامل $10$ واحد متمایز است که $3$ تای آن‌ها معیوب (defective) و $7$ تا سالم (sound) هستند. بازرس $3$ واحد را بدون جایگذاری بیرون می‌کشد.

(الف) اندازهٔ فضای نمونه. برای نمونه‌ای سه‌تایی ترتیب بی‌اهمیت است، پس

(ب) دقیقاً یک معیوب. انتخاب اینکه کدام معیوب و کدام دو سالم (اصل ضرب):

(ج) حداقل یک معیوب — از راه متمم، چون «هیچ معیوبی» یک شمارش سادهٔ تک‌مرحله‌ای است:

(د) گزاره‌ای دربارهٔ جایگاه‌ها — «دو تای اول سالم و سومی معیوب باشد» جایگاه‌ها را نام می‌برد، پس با کشیدنِ مرتب کار کنید و در طول درخت ضرب کنید:

که عامل آخرش همان احتمال شرطی $P(\text{3rd defective}\mid\text{first two sound})=\tfrac38$ است.

(ه) وارسی تقارن. بدون شرط، سومین واحدِ کشیده‌شده با احتمال $\tfrac{3}{10}$ معیوب است — همان احتمال واحد نخست. هم‌ارز آن، شمارش مستقیم کشیدن‌های مرتب: $\binom{3}{1}\times P(9,2)=3\times 72=216$ از $P(10,3)=720$، و $216/720=0.3$. جایگاه پیش از آنکه به کشیدن‌های قبلی نگاه کنید هیچ اطلاعاتی حمل نمی‌کند؛ اما پس از آن اطلاعات فراوانی حمل می‌کند.

۵. اشتباه نشود با… — Confused with

همسایه‌های شمارشی

همسایه‌های احتمالی

نکتهٔ کنکوری: دو واکنش سریع بیشتر سؤال‌های این حوزه را حل می‌کند. (۱) اول ترتیب، بعد فرمول — دنبال واژه‌ای بگردید که یک جایگاه را نام می‌برد («سوم»، «اولین»، «در یک ردیف»)؛ اگر چنین واژه‌ای باشد، شمارش یک جایگشت است و گزینهٔ انحرافی کلاسیک دقیقاً همان $\binom{n}{r}$ است که ترتیب را نادیده می‌گیرد. (۲) وقتی صورت سؤال «هیچ‌کدام / هیچ‌یک» یا شرطی دربارهٔ دو نفیِ هم‌زمان به شما می‌دهد، اجتماع فقط یک تفریق فاصله دارد: $P(A\cup B)=1-P(A^{c}\cap B^{c})$، و تلهٔ کارگذاشته‌شده خودِ مقدار میانی $P(A^{c}\cap B^{c})$ است — داوطلب مرحلهٔ دشوار را درست انجام می‌دهد و $1-(\cdot)$ پایانی را فراموش می‌کند. با احتساب نمرهٔ منفی، هر گزینه‌ای را هم که از سقف بدیهی فراتر می‌رود در نگاه اول کنار بگذارید (شمارشی بزرگ‌تر از $n^{r}$، یا احتمالی بیرون از $[0,1]$ یا بزرگ‌تر از مجموع پیشامدهای درگیر). در تخصیص صحیح با مقادیر متمایز، پیش از شمارش جایگشت‌ها مقادیر را مرتب و حداقل مجموع را بررسی کنید؛ ستاره و میلهٔ نامقید ممکن است بردارهای ممنوع را بشمارد.