دسته‌بندی:   محتوای آموزشی ویژه مدارس برتر

اصول شمارش در ترکیبیات

اصول شمارش در ترکیبیات

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

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

بلوز شلوار
آبی آبی
زرد آبی
سبز آبی
آبی مشکی
زرد مشکی
سبز مشکی

 

طبق جدول فوق، شش حالت برای پوشیدن لباس وجود دارد. اما آیا کشیدن این جدول لازم بود؟ پاسخ منفی است. می توانستیم اینگونه سوال را حل کنیم که برای انتخاب شلوار 2 انتخاب (2 حالت) و برای انتخاب بلوز 3 انتخاب (3 حالت) داریم. با توجه به این که رنگ شلوار و بلوز محدودیتی ندارد و انتخاب آن‌ها از یکدیگر مستقل است، تعداد حالت های مطلوب با توجه به اصل ضرب برابر  2×3=6 می باشد.

اصل ضرب چیست؟

تعریف اصل ضرب در ترکیبیات و ریاضی برای انجام 2 کار به این شکل است که که اگر کار شماره 1 (در مثال فوق پوشیدن شلوار) به a طریق و به ازای هر حالت انجام کار ۱، کار ۲ (در مثال فوق پوشیدن بلوز) به b طریق قابل انجام باشد، تعداد روش‌های انجام این ۲ کار با هم برابر a×b است.

چند مثال از اصل ضرب

  1. فرض کنید در یک مدرسه 4 کلاس وجود دارد که در کلاس اول، دوم، سوم و چهارم به ترتیب 15، 10، 5 و 8 دانش‌آموز دارند. می‌خواهیم یک شورای دانش‌آموزی برای این مدرسه انتخاب کنیم به طوری که از هر کلاس ۱ نفر در این شورا عضو باشد. این کار به چند طریق ممکن است؟
    پاسخ: برای انتخاب نماینده از کلاس اول 15 حالت، نماینده از کلاس دوم 10 حالت، نماینده از کلاس سوم 5 حالت و نماینده از کلاس چهارم 8 حالت دارد. در نتیجه انتخاب اعضای شورا به 15×10×5×8 حالت امکان پذیر است. دقت کنید که نوشتن تمام حالات این انتخاب کاری بسیار طولانی و زمانبر می باشد!
  2. چند ۴ رقمی داریم؟
    برای هر رقم، یک جایگاه، مانند شکل زیر، در نظر می‌گیریم و تعداد حالات آن رقم را می‌نویسیم. رقم هزارگان، ۹ حالت دارد (۰ نمی‌تواند باشد) و هر کدام از ارقام یکان، دهگان و صدگان، ۱۰ حالت دارند؛ بنابراین 9×10×10×10=9000 عدد 4 رقمی داریم.
  3. چند ۴ رقمی زوج داریم؟
    باز هم برای هر رقم، یک جایگاه، مانند شکل زیر در نظر می‌گیریم و تعداد حالات آن رقم را می‌نویسیم. رقم هزارگان ۹ حالت دارد (۰ نمی‌تواند باشد). رقم دهگان ۱۰ حالت، رقم صدگان نیز، ۱۰ حالت و رقم یکان ۵ حالت دارد (باید زوج باشد). بنابراین تعداد اعداد ۴ رقمی زوج، 9×10×10×5=4500 است.
  4. آرش در يک آزمون با 6 سوال 4 گزينه‌ای و 4 سوال 3 گزينه‌ای شركت می‌كند. اگر پاسخ به سوال‌های 3 گزينه‌ای در اين آزمون الزامی باشد، آرش به چند طريق می‌تواند پاسخ‌نامه‌ی خود را پر كند؟
    پاسخ: برای هر سوال 4 گزينه‌ای 5 حالت (يك حالت اين است كه می‌توانيم سوال را پاسخ ندهيم) و برای هر سوال 3 گزينه‌ای 3 حالت داريم. پس طبق اصل ضرب پاسخ مسئله برابر می‌شود با 56×34.
  5. به چند حالت می‌توان از یک مجموعه‌ی ‎ ۱۰‎عضوی به‌ترتیب سه زیرمجموعه‌ی‎A1 ‎ و A2 و ‎A3‎ را انتخاب کرد به‌طوری که ‎A1∩A2∩A3=ϕ‎؟ (‎Aiها لزوماً متمایز نیستند‎.(‎
    پاسخ: هر عضو از آن۱۰ عضو ۷ انتخاب زیر را مستقل از اعضای دیگر می‌تواند داشته باشد:
    الف) متعلق به هیچ یک از Ai ها نباشد.
    ب) تنها متعلق به یکی از Ai ها باشد. (سه حالت)
    ج) تنها متعلق به دو تا از Ai ها باشد. (سه حالت)
    بنابراین طبق اصل ضرب تعداد حالات ممکن برابر 710‎ می‌باشد.

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

صورت کلی اصل ضرب

اصل ضرب را می‌توان برای n کار مختلف نیز بیان کرد. در واقع اگر کار اول به a1 طریق، کار دوم به a2 طریق و ... و کار n ام به an طریق قابل انجام باشد و انجام این کارها از یکدیگر مستقل باشند، تعداد روش‌های انجام این n کار با هم، برابر a1×a2×...×an می باشد.

در ادامه به بیان اصل دیگری از اصول شمارش به نام اصل جمع در ترکیبیات می پردازیم.

اصل جمع

مانند قبل موضوع را با یک مثال آغاز می کنیم. فرض کنید برای انتخاب نوشیدنی همراه غذا، سه نوع نوشابه مشکی، زرد و سفید و همینطور دو نوع دوغ گازدار و بدون گاز و دو جور دلستر بی طعم و لیمویی دارید. به چند طریق می توانید نوشیدنی خود را انتخاب کنید؟ پاسخ برابر 7 است، زیرا نوشیدنی همراه غذا یا نوشابه و یا دوغ و یا دلستر است و در نتیجه انتخاب نوشیدنی به 2+2+3 طریق امکان پذیر می باشد. دقت کنید که انتخاب یک نوشیدنی به نوشیدنی دیگر ربط دارد و مستقل نیست و از اصل جمع استفاده کردیم.

اصل جمع چیست؟

تعریف اصل جمع در ترکیبیات و ریاضی به این صورت تعریف می‌شود که اگر برای انجام کاری a روش و انجام کار دیگری b روش داشته باشد، تعداد کل حالت های انجام دادن یکی از این دو کار، برابر a+b است. در واقع استفاده از اصل جمع در ترکیبیات، همان حالت‌بندی مساله به چند حالت است که بررسی هرکدام به تنهایی کار ساده تری می باشد. هر کجا که حالت‌بندی کنیم، در واقع از اصل جمع استفاده می‌کنیم. طبیعی است که اصل جمع (یا همان حالت بندی!) برای چند کار که همزمان رخ نمی دهند نیز صادق است.

چند مثال از اصل جمع

  1. چند عدد ۲ رقمی زوج با ارقام متمایز داریم؟
    بیایید مانند روش اصل ضرب، استدلال خود را پیش ببریم. رقم یکان ۵ حالت دارد (زیرا باید زوج باشد). برای تعیین رقم دهگان با توجه به شرط تمایز ارقام به مشکل برمی‌خوریم، زیرا اگر رقم یکان ۰ انتخاب شده باشد، برای انتخاب رقم دهگان ۹ حالت داریم و اگر رقم یکان غیر از ۰ انتخاب شده باشد، برای انتخاب رقم دهگان ۸ حالت داریم (رقم ۰ و رقم انتخاب شده برای یکان نمی‌توانند در دهگان بیایند.). پس در این سوال باید از اصل جمع برای حالت بندی استفاده کنیم. پس اعداد ۲ رقمی زوج با ارقام متمایز را به دو دسته تقسیم می‌کنیم:
    الف) رقم یکان برابر ۰ انتخاب شده باشد. در این حالت انتخاب رقم دهگان ۹ حالت دارد. پس تعداد اعداد این حالت 9×1=9 است.
    ب) رقم یکان غیر از رقم ۰ انتخاب شده باشد. در این حالت انتخاب رقم یکان ۴ حالت و انتخاب رقم دهگان ۸ حالت (به جز 0 و رقم انتخاب شده برای یکان) دارد. پس تعداد اعداد این حالت 8×4=32 است.
    پس در کل با استفاده از اصل جمع، پاسخ برابر 9+32=41 می باشد.
  2. با ارقام {1,2,3,4,5,8} چند عدد 4 رقمی با ارقام متمايز و زوج كه دهگانی بزرگ‌تر از يكان دارند، می‌توان نوشت؟
    پاسخ: برای زوج بودن اين عدد چهاررقمی، بايد رقم يكان برابر يكی از سه رقم 2 و 4 و 8 باشد. اما اگر 8 را نمی توان در جايگاه يكان قرار داد (چرا؟). با توجه به این موضوع از رقم سمت راست شروع به جای‌گذاری اعداد می‌كنيم و يك بار عدد 2 و يك بار عدد 4 را در رقم يكان قرار می دهیم. با استفاده از این اصل جمع می توان دید جواب برابر 24+48=72 می باشد.
  3. چند عدد طبیعی چهار رقمی زوج با ارقام غيرتكراری داریم و که ارقام آن‌ها از 6 كوچک‌تر باشند؟
    پاسخ: اين مسئله را به دو حالت تقسيم می‌كنيم.
    الف) رقم سمت راست، صفر باشد. در این حالت 5×4×3×1=60 عدد داریم.
    ب) رقم سمت راست، غير صفر و زوج باشد. در این حالت 4×4×3×2=96 عدد داریم.
    پس پاسخ طبق اصل جمع برابر 156 می باشد.
  4. می خواهیم آهنگی با نت های موسیقی بسازیم با این شرط ها که فقط از نت های «سل»، «لا» و «سی» استفاده کنیم، بعد از هیچ نت «سل»ای بلافاصله نت «سی» نیاید و طول آهنگ دقیقا سه نت باشد. با فرض اینکه می توان از نت تکراری استفاده کرد به چند طریق می توان چنین آهنگی ساخت؟
    پاسخ: در صورتی که نت اول سل نباشد، برای نت بعدی سه حالت و در صورتی که سل باشد دو حالت داریم. به همین ترتیب نت دوم را تقسیم‌بندی می‌کنیم تا به نتیجه‌ی زیر برسیم:
    2×(2×(3)+1×(2))+1×(1×(3)+1×(2))=21

اصل متمم

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

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

به راحتی می توان دید که تعداد کل اعداد سه رقمی برابر 900 تا می باشد. اعداد سه رقمی با رقم تکراری دارند (مانند اعداد 338 و 272 و 444) و یا رقم تکراری ندارند (مانند اعداد 145 و 509). اگر بخواهیم با اصل جمع و حالت‌بندی این مساله را حل کنیم، حالت‌بندی ما بسیار طولانی خواهد شد و احتمال خطای محاسباتی نیز زیاد می شود. با توجه به توضیحات کافی است تعداد اعداد سه رقمی بدون رقم تکراری را از تعداد کل اعداد سه رقمی کم کنیم تا تعداد اعداد سه رقمی که رقم تکراری دارند را به دست بیاوریم. تعداد اعداد سه رقمی که رقم تکراری ندارند را با کمک اصل ضرب می‌شماریم. رقم سمت صدگان، ۹ حالت دارد (۰ نمی‌تواند در صدگان باشد). رقم دهگان ۹ حالت دارد (برابر رقم صدگان نمی‌تواند باشد). رقم یکان 8 حالت دارد (برابر رقم صدگان و دهگان نمی‌تواند باشد). پس در کل 9×9×8 عدد سه رقمی وجود دارد که رقم تکراری نداشته باشند. حال با استفاده از اصل متمم، تعداد اعداد سه رقمی که رقم تکراری دارند برابر 792-900 یعنی 108 تا می باشد.

اصل متمم چیست؟

فرض کنید A زیرمجموعه‌ای از مجموعه‌ی مرجع M باشد. اصل متمم می‌گوید تعداد اعضایی که در A قرار ندارند (تعداد اعضای ′A)، برابر |M|−|A| است.

چند مثال از اصل متمم

  1. در چند زیرمجموعه از مجموعه‌ی {10,...,1,2,3} حداقل یک عدد زوج، وجود دارد؟
    پاسخ: تعداد کل زیر مجموعه‌های این مجموعه برابر 210 است که 25 تا از آن‌ها هیچ عدد زوجی در خود ندارند. پس با توجه به اصل متمم حکم سوال برابر 25-210 است.
  2. در چند عدد پنج رقمی حداقل یک رقم 3 داریم؟
    پاسخ: تعداد کل اعداد پنج رقمی 104×9 می باشد که در 94×8 از آن ها رقم 3 وجود ندارد. پس پاسخ برابر 94×8-104×9 می باشد.

 

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

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

 

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

معرفی و انتخاب رشته دندان پزشکی

انتخاب رشته:

اصلی‌ترین رقیب رشته پزشکی برای انتخاب در بین داوطلبین کنکور با رتبه‌های برتر درانتخاب رشته...

برای قبولی در المپیاد زیست شناسی چه کتابی بخوانیم؟

برای قبولی در المپیاد زیست شناسی چه کتابی بخوانیم؟

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

در باب ادبیات

در باب ادبیات

به قلم خانم سارا همتی، رتبه یک کنکور تجربی 94

بعد از متن مشاوره‌ای آقای علیرضا سخایی راد رتبه...