نمره کف قبولی المپیاد چیست؟ با چه نمره ای در المپیاد قبول می شویم؟
دسته‌بندی:   محتوای آموزشی ویژه مدارس برتر

آشنایی با انتخاب در ترکیبیات (انتخاب یا ترکیب چیست)

آشنایی با انتخاب در ترکیبیات (انتخاب یا ترکیب چیست)

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

ترکیب r از n (به بیان دیگر، انتخاب r از n) برابر تعداد راه های انتخاب r شی از n شی متمایز بدون توجه به ترتیب انتخاب آن ها می باشد. انتخاب r شی از n شی را با یکی از نمادهای  نشان می‌دهند که بیشتر از نماد اول استفاده می شود و آن را به صورت "r از n" یا "انتخاب r از n" می خوانند.

برای مثال فرض کنید می خواهیم از بین اعداد 1،2،3،4 دو عدد را انتخاب کنیم. انتخاب ما می تواند به یکی از این 6 طریق باشد:

{1،2}،{1،3}،{1،4}،{2،3}،{2،4}،{3،4}

در نتیجه حاصل انتخاب 2 از 4 برابر 6 می باشد. دقت کنید انتخاب {1،2} با انتخاب {2،1} فرقی نمی کند. به راحتی می توان روابط زیر را ثابت کرد.

به عنوان مثال تعداد راه های انتخاب 1 نفر از n نفر به وضوح برابر 1 است. همینطور تعداد راه های انتخاب n-1 نفر از n نفر مانند این است که از بین n نفر، یک نفر را (به n حالت) انتخاب نکنیم و بقیه را انتخاب کنیم. دقت کنید اثبات این رابطه نیازی به دانستن فرمول انتخاب نداشت و ما برای اثبات آن ها از اثبات ترکیبیاتی استفاده کردیم. همینطور اثبات روابط زیر به صورت استدلال ترکیبیاتی کار سختی نیست.

به عنوان تمرین، این روابط را به صورت ترکیبیاتی اثبات می کنیم:

  1. فرض کنید می خواهیم k نفر از n نفر را انتخاب کنیم و به گردش ببریم. برای این کار می توانیم k نفر از n نفر را انتخاب کنیم. اما راه دیگری نیز به کمک شمارش ترکیبیاتی وجود دارد که شاید کمی عجیب باشد. برای انتخاب این k نفر، می توانیم ابتدا n-k نفر از آن n نفر را که نمی خواهیم به گردش ببریم انتخاب کنیم و بقیه را که k نفر هستند به گردش ببریم.
  2. با استفاده از راهنمایی رو به رو این تساوی را که به فرمول پاسکال معروف است اثبات کنید. یکی از این n نفر را در نظر بگیرید و فرض کنید اسم وی علی باشد. تعداد راه های انتخاب k نفر از n نفر را به کمک اصل جمع دو حالت تقسیم کنید. یکی از حالات این باشد که حتما علی در آن k نفر باشد (پس باید k-1 نفر دیگر انتخاب کنید) و دیگری این باشد که علی در آن k نفر نباشد.
  3. دقت کنید سمت چپ تساوی برابر جمع تعداد راه های انتخاب k شی از n شی برای تمام حالت های k می باشد که معادل است با تعداد کل زیر مجموعه های یک مجموعه n عضوی و این نیز برابر 2n است.

حال می خواهیم فرمول صریح برای انتخاب k شی از n شی را به دست آورده و اثبات کنیم. ابتدا ببینیم انتخاب k نفر از n نفر بدون اهمیت دادن به ترتیب انتخاب و ترتیب آن‌ها و تعداد راه‌های آن با قرار دادن k نفر از n نفر (جایگشت k نفر از n نفر) چه تفاوتی دارد. دقت کنید قرار دادن k نفر از n نفر در یک صف با رعایت ترتیب مشابه این است که ابتدا به "انتخاب k از n" حالت انتخاب کنیم که کدام k نفر از k نفر قرار است در صف بایستند و سپس آن k نفر را به !k حالت در صف بچینیم. از طرفی می دانیم تعداد راه های چیدن k نفر از n نفر در یک صف، طبق اصل ضرب، برابر !(n-k)/!n است. در نتیجه به فرمول صریح

برای تعداد راه های انتخاب k نفر از n نفر می رسیم. یعنی "انتخاب k از n" برابر !(n-k)!(k)/!n است.

در ادامه به حل یک مثال از نمونه سوالات المپیاد ریاضی و یک مثال از نمونه سوالات المپیاد کامپیوتر مرتبط با مبحث انتخاب می پردازیم:

  1. نوید و سعید مشغول بازی «سنگ، کاغذ، قیچی» هستند. در هر دست از این بازی دو نفره٬ دو بازیکن دستشان را به پشت سر خود برده و سپس دست خود را به یکی از سه شکل سنگ٬ کاغذ یا قیچی به دیگران نشان می دهند. سنگ قیچی را می برد و به کاغذ می بازد، کاغذ سنگ را می برد و به قیچی می بازد، و قیچی کاغذ را برده و به سنگ می بازد. در صورتی که هر دو بازیکن یک شکل یکسان را انتخاب کرده باشند، آن دست مساوی اعلام می شود. در این بازی برنده‌ی هر دست ۱ امتیاز و بازنده ۰ امتیاز می گیرد. در صورت تساوی نیز هر دو طرف صفر امتیاز خواهند گرفت. برنده بازی کسی خواهد بود که مجموع امتیازش زودتر از دیگری به عدد ۳ برسد. تعداد حالت هایی از بازی که نوید در انتهای دست هفتم برنده‌ی بازی شود چند است؟

    هر یک از حالات برد، باخت و تساوی نوید 3 حالت دارد (برای مثال برای برد سنگ-قیچی، قیچی-کاغذ و کاغذ-سنگ حالت های مختلف هستند). از طرفی می‌دانیم نوید حتما بازی هفتم را برده است و در شش بازی اول دقیقا دو بازی را نوید و حداکثر دو بازی را سعید برده است (اگر بیش‌تر از دو بازی را سعید ببرد، نوید در کل بازنده بازی خواهد بود). برای محاسبه با استفاده از اصل جمع حالت بندی می‌کنیم:

    1. تعداد حالاتی که در 6 بازی اول نوید 2برد و 4 تساوی داشته باشد برابر است با : C(6,2)×37
    2. تعداد حالاتی که در6 بازی اول نوید 2 برد،3 تساوی و 1 باخت داشته باشد برابر است با: C(6,3)×C(6,1)×37
    3. تعداد حالاتی که در6 بازی اول نوید 2 برد ، 2 تساوی و 2 باخت داشته باشد برابر است با : C(6,2)×C(4,2)×37
  2. پنج مهره سفید و ده مهره سیاه داریم. به چند طریق می توانیم این مهره ها را در یک ردیف از چپ به راست بچینیم به گونه ای که بلافاصله بعد از هر مهره سفید حداقل یک مهره سیاه قرار داشته باشد؟
    پاسخ برابر انتخاب 5 از 10 می باشد. ابتدا ده مهره سیاه را در یک صف به 1 طریق (!) قرار می دهیم. حال برای 5 مهره سفید، 10 انتخاب داریم (9 انتخاب بین مهره های سیاه و یک انتخاب سمت چپ اولین مهره سیاه). با انتخاب 5 از 10 جایگاه، محل قرار گیری مهره های سفید مشخص می شود.

 

از طریق این لینک می توانید کانال تخصصی ریاضی سمپادیا را دنبال نمایید.

از طریق این لینک می توانید کانال تخصصی کامپیوتر سمپادیا را دنبال نمایید.

 

دیگر مقالات سایت
آشنايى كودكان با احساس هاى مختلف

آشنايى كودكان با احساس هاى مختلف

كودكان سراسر احساس هستند، اما خيلي زود ياد مي‌گيرند كه تمامي احساسات خوب نيستند يا از طرف بزرگترها جدي گرفته نمي شوند. كودك با خود مي گويد آيا من اجازه دارم همان چ...

منتظر نشوید 63 ساله شوید!

منتظر نشوید 63 ساله شوید!

واقعا چقدر توانمند هستید؟

من واکسن کرونا زده ام!

من واکسن کرونا زده ام!

در زیر خاطره‌ی یک داوطلب واکسن دانشگاه آکسفورد برای ویروس کرونا را می خوانید.

در اتاق انتظار بیمارستان نشسته‌ام و از...