ارتباط جایگشت و ترکیب: چرا تعداد ترکیبهای rتایی برابر P(n,r) تقسیم بر r! است؟
بازتعریف جایگشت و ترکیب با مثالهای روزمره
در شمارششناسی (Combinatorics)1 دو مفهوم بنیادی به نامهای جایگشت (Permutation)2 و ترکیب (Combination)3 وجود دارد. تفاوت اصلی آنها در اهمیت «ترتیب» است. در جایگشت، چینش اشیاء مهم است، اما در ترکیب، تنها انتخاب اعضا اهمیت دارد و ترتیب نقشی ایفا نمیکند.
مثال جایگشت: فرض کنید میخواهیم از بین 3 نفر (A، B و C) یک رئیس و یک نایبرئیس انتخاب کنیم. در اینجا ترتیب انتخاب مهم است، زیرا (رئیس =A و نایبرئیس =B) با (رئیس =B و نایبرئیس =A) تفاوت دارد. تعداد این جایگشتها برابر است با:
مثال ترکیب: حالا میخواهیم از بین همین 3 نفر، یک کمیتهٔ 2 نفره (بدون مسئولیت خاص) انتخاب کنیم. در این حالت، انتخاب {A,B} با {B,A} یکی است. تعداد ترکیبها برابر است با:
همانطور که میبینید، تعداد ترکیبها (3) دقیقاً برابر است با تعداد جایگشتها (6) تقسیم بر 2! (که برابر 2 است). این همان قاعدهٔ اصلی مقالهٔ ماست.
اثبات رابطهٔ C(n,r) = P(n,r) / r! به زبان ساده
برای درک دلیل این رابطه، مراحل زیر را گام به گام طی میکنیم.
گام اول: تعداد جایگشتهای r شیء از n شیء برابر است با:
این فرمول، همهٔ چینشهای مرتب rتایی را میشمارد.
گام دوم: فرض کنید یک ترکیب خاص (مجموعهٔ r عضوی بدون ترتیب) داریم. این ترکیب میتواند به چند شکل مختلف مرتب شود؟ هر مجموعهٔ r عضوی، دقیقاً r! جایگشت (چینش خطی) متفاوت دارد.
گام سوم: حالا کل جایگشتهای P(n,r) را در نظر بگیرید. اگر این جایگشتها را بر اساس ترکیبهای یکسان (مجموعههای عضو) دستهبندی کنیم، هر دسته شامل r! جایگشت خواهد بود (چون هر ترکیب را به r! شکل میتوان مرتب کرد). بنابراین:
مثال عددی برای درک بهتر: فرض کنید n=4 و r=2. ابتدا P(4,2) = 4×3 = 12. حالا ترکیبها را بنویسید: {1,2}، {1,3}، {1,4}، {2,3}، {2,4}، {3,4}. تعداد آنها 6 است. توجه کنید که 12 / 2! = 12 / 2 = 6. رابطه تأیید میشود.
مقایسهٔ ساختاری جایگشت و ترکیب در یک نگاه
| ویژگی | جایگشت (Permutation) | ترکیب (Combination) |
|---|---|---|
| اهمیت ترتیب | مهم | بیاهمیت |
| فرمول کلی | $P(n,r) = \frac{n!}{(n-r)!}$ | $C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$ |
| رابطه با P(n,r) | مستقل | $C(n,r) = P(n,r) / r!$ |
| مثال عینی | چیدن کتاب در قفسه | انتخاب اعضای تیم |
کاربرد عملی: مسابقهٔ علمی و انتخاب سوالات
فرض کنید در یک مسابقهٔ علمی، 10 سوال وجود دارد. هر شرکتکننده باید 3 سوال را برای پاسخدهی انتخاب کند (ترتیب انتخاب مهم نیست). تعداد راههای انتخاب سوالات برابر است با:
حالا اگر مسئله به این صورت بود که سوالات باید به ترتیب اولویت (سوال اول مهمتر از سوال دوم و ...) پاسخ داده شوند، آنگاه ترتیب اهمیت مییافت و باید از جایگشت استفاده میکردیم:
توجه کنید که 720 دقیقاً 3! = 6 برابر 120 است. این مثال نشان میدهد که در عمل، هر زمان ترتیب حذف شود، تعداد حالات به شدت کاهش مییابد.
چالشهای مفهومی رایج
۱. آیا همیشه میتوان ترکیب را از جایگشت به دست آورد؟
بله، به شرطی که اشیاء متمایز باشند و تکرار نداشته باشیم. رابطهٔ $C(n,r) = P(n,r) / r!$ برای همهٔ اعداد صحیح $0 \le r \le n$ برقرار است. اگر $r=0$ باشد، هر دو طرف برابر 1 میشوند.
۲. چرا در فرمول ترکیب یک r! دیگر در مخرج ظاهر میشود؟
دلیل آن این است که هر ترکیب (مجموعهٔ بدون ترتیب) میتواند به r! روش مختلف مرتب شود و به جایگشت تبدیل گردد. بنابراین برای برگشت از جایگشت به ترکیب، باید این تعداد حالت اضافی را حذف کنیم. به عبارت دیگر، ترکیب «خارج کردن اثر ترتیب» از جایگشت است.
۳. اگر برخی اشیاء تکراری باشند، آیا این رابطه همچنان برقرار است؟
خیر. رابطهٔ $C(n,r) = P(n,r)/r!$ فرض میکند همهٔ n شیء متمایز هستند. در حالت وجود اشیاء تکراری، باید از فرمولهای جایگشت با تکرار یا ترکیب با تکرار استفاده کرد که پیچیدهتر هستند و در این مقاله نمیگنجند.
پاورقیها
1شمارششناسی (Combinatorics): شاخهای از ریاضیات که به مطالعهٔ روشهای شمارش، چیدمان و ترکیب اشیاء میپردازد.
2جایگشت (Permutation): هر چینش مرتب از تعدادی عضو یک مجموعه که در آن ترتیب قرار گرفتن اعضا مهم است.
3ترکیب (Combination): هر انتخاب از تعدادی عضو یک مجموعه بدون توجه به ترتیب آنها.
4فاکتوریل (Factorial): حاصلضرب همهٔ اعداد طبیعی از 1 تا n که با نماد $n!$ نمایش داده میشود. مثلاً $4! = 4 \times 3 \times 2 \times 1 = 24$.