ریاضی 955 بازدید

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

در طرف دیگر ترکیب بسیار ساده‌تر است و جزییات اهمیتی ندارند. در این زمینه تفاوتی بین «آلیس، باب و چارلی» با «چارلی، باب و آلیس» وجود ندارد. بدین ترتیب جایگشت‌ها در مورد لیست‌ها به کار می‌روند و ترتیب در مورد آن‌ها مهم است؛ در حالی که ترکیب‌ها در مورد گروه‌ها کاربرد دارند و ترتیب هیچ اهمیتی ندارد.

جایگشت

در ابتدا مفهوم جایگشت را بررسی می‌کنیم. جایگشت یعنی همه روش‌های ممکن برای انجام دادن یک کار. به این دلیل از واژه جذاب جایگشت استفاده می‌کنیم که قرار است در مورد همه جزییات دقیق باشیم و این جزییات شامل ترتیب همه آیتم‌ها نیز می‌شود. فرض کنید 8 نفر وجود دارند:

  1. آلیس (Alice)
  2. باب (Bob)
  3. چارلی (Charlie)
  4. دیوید (David)
  5. حوا (Eve)
  6. فرانک (Frank)
  7. جرج (George)
  8. هوراسیو (Horatio)

چند روش برای اهدای جوایز مقام اول، دوم و سوم بین این هشت نفر وجود دارد؟

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

  • مدال طلا: 8 گزینه به صورت A B C D E F G H وجود دارد. (حالا دلیل انتخاب این اسامی را متوجه شده‌اید.) A یا آلیس مدال طلا را می‌برد.
  • مدال نقره: 7 گزینه به صورت B C D E F G H وجود دارد. فرض می‌کنیم B یعنی باب مدال طلا را ببرد.
  • مدال برنز: 6 گزینه به صورت C D E F G H وجود دارد. فرض کنید C یعنی چارلی مدال برنز را ببرد.

گرچه ما افراد معینی را برای دریافت مدال‌ها انتخاب کردیم، اما مهم نیست این افراد چه کسانی باشند. ما در ابتدا هشت گزینه داریم، سپس 7 گزینه و در نهایت 6 گزینه، پس مجموع تعداد گزینه‌ها برابر با 336 = 8 × 7 × 6 است.

توضیح بیشتر

اینک نگاهی به جزییات می‌اندازیم. ما باید سه نفر را از میان 7 نفر انتخاب کنیم. برای انجام این کار با همه گزینه‌ها (8) آغاز می‌کنیم و هر بار یکی از آن‌ها را انتخاب می‌کنیم (7 و سپس 6) تا این که همه مدال‌ها اهدا شده باشند.

می‌دانیم که فاکتوریل 8 به صورت زیر است:

1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 =!8

متأسفانه این محاسبه با نتایج ما همخوانی ندارد. ما چگونه می‌توانیم فاکتوریل را در عدد 5 متوقف کنیم؟ این همان جایی است که جایگشت به کار می‌آید. چگونه می‌توانیم از شر حاصلضرب 1 × 2 × 3 × 4 × 5 خلاص شویم؟ می‌دانیم که این مقدار برابر با !5 است. بنابراین اگر !8 را بر !5 تقسیم کنیم، نتیجه مطلوب حاصل می‌شود:

و اگر بپرسید چرا از عدد 5 استفاده کردیم، باید بگوییم چون این تعداد افرادی است که پس از دریافت مدال‌ها باقی می‌مانند، 3 نفر مدال می‌گیرند و 5 نفر بدون مدال باقی می‌مانند. بنابراین یک روش بهتر برای نوشتن عبارت فوق به صورت زیر است:

عبارت فوق تنها یک روش جذاب برای گفتن این است که «از 3 عدد نخست، از 8 تا استفاده کن». اگر در مجموع n آیتم داشته باشیم و بخواهیم k تا را با ترتیب خاصی از میان آن‌ها انتخاب کنیم، فرمول کلی به صورت زیر خواهد بود:

این همان فرمول جذاب جایگشت است. n آیتم داریم و می‌خواهیم تعداد روش‌هایی که می‌توان k آیتم را از میان آن‌ها با ترتیب معین انتخاب کرد، به دست آوریم:

ترکیب

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

به چند روش می‌توان 3 قوطی حلبی را به 8 نفر اهدا کرد؟

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

کسر افزونگی‌ها

در این جا نکته جالبی پیش می‌آید. در واقع افزونگی‌هایی وجود دارند: آلیس باب چارلی = چارلی باب آلیس. اینک برای لحظه‌ای اجازه بدهید ببینیم به چند طریق می‌توانیم این 3 نفر را بازآرایی کنیم؟ ما 3 انتخاب برای نفر اول، 2 انتخاب برای نفر دوم و 1 انتخاب برای نفر سوم داریم. بنابراین بازآرایی 3 نفر اول به 1 × 2 × 3 روش امکان‌پذیر است.

لحظه‌ای صبر کنید، اما این شبیه همان جایگشت است. در واقعیت هم چنین است. اگر N نفر داشته باشیم و بخواهیم بدانیم برای همه آن‌ها چند بازآرایی وجود دارد، این تعداد برابر با N فاکتوریل (!N) خواهد بود.

بنابراین اگر 3 قوطی حلبی داشته باشیم که بخواهیم آن‌ها را اهدا کنیم، !3 یا 6 روش برای هر انتخاب وجود دارد. اگر بخواهیم بدانیم که چه تعداد ترکیب داریم، می‌بایست همه جایگشت‌ها را محاسبه کنیم و آن را بر همه موارد تکراری تقسیم کنیم. در این مورد ما قبلاً حساب کردیم که 336 جایگشت داریم و می‌خواهیم بر 6 افزونگی برای هر جایگشت تقسیم کنیم، بنابراین 336/6 = 56.

فرمول کلی به صورت زیر است:

یعنی «همه روش‌هایی که می‌توان k نفر را از میان n نفر انتخاب کرد را پیدا کن و آن را بر !K تقسیم کن.» با نوشتن این عبارت، «فرمول ترکیب» یا تعداد روش‌های ترکیب K آیتم از مجموعه n شیء را به دست می‌آوریم:

برخی اوقات (c(n,k به صورت زیر نیز نوشته می‌شود:

که ضریب دوجمله‌ای نام دارد.

چند مثال

در ادامه چند مثال از جایگشت (که ترتیب اهمیت دارد) و ترکیب (که ترتیب اهمیتی ندارد) را ارائه کرده‌ایم:

  • ترکیب: انتخاب تیمی 3 نفره از گروهی متشکل از 10 نفر. C(10,3) = 10!/(7! × 3!) = 10 × 9 × 8 / (3 × 2 × 1) = 120
    • جایگشت: انتخاب یک رئیس، نایب‌رئیس و معاون از گروهی 10 نفره. P(10,3) = 10!/7! = 10 × 9 × 8 = 720
  • ترکیب: انتخاب 3 دسر از منویی که 10 آیتم دارد: C(10,3) = 120
    • جایگشت: فهرست بندی 3 مورد از دسرهای مورد علاقه با ترتیب اولویت از منویی حاوی 10 آیتم.

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

اگر به این نوشته علاقه‌مند بودید، موارد زیر نیز احتمالاً مورد توجه شما قرار خواهند گرفت:

==

بر اساس رای 2 نفر

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *