درس ۱ · صفحهٔ ۵۵ تا ۵۹ · حدود ۱۵ دقیقه · تولید هوش مصنوعی
درس ۱ مباحثی در ترکیبیات
در این درس یاد میگیری با دستهبندی اشیا، تشخیص الگوهای چیدن و حذف جابهجاییهای تکراری یا بیاثر، مسئلههای جایگشت و تقسیم افراد به گروههای مشخص را حل کنی.
پیش از شروع
اگر دو حرفِ یک رمز یکسان باشند، آیا جابهجا کردنشان واقعاً رمز تازهای میسازد؟ این موضوع چه اثری روی شمارش رمزها دارد؟
جابهجایی دو حرف یکسان، رمز تازهای نمیسازد؛ پس شمردن همهٔ جابهجاییها میتواند باعث چندبارشماری شود. در این درس یاد میگیریم چه وقت اشیا را یک بسته حساب کنیم و چه وقت حالتهای تکراری را با تقسیم کنار بگذاریم.
کنار هم، مثل یک بسته
کنار هم، مثل یک بسته
فرض کن چند دوست میخواهند برای عکس یادگاری در یک ردیف بایستند و بعضی از آنها اصرار دارند کنار هم باشند. چطور این شرط را در شمارش رعایت کنیم؟
افرادی را که باید کنار هم بمانند، موقتاً یک بسته در نظر بگیر. حالا این بسته، درست مثل یک نفر، در کنار بقیه جابهجا میشود. اگر با این کار در مجموع شیء متمایز داشته باشیم، ترتیب آنها حالت دارد.
اما بسته را نباید بسته نگه داریم! افراد داخل آن هم میتوانند جای خود را عوض کنند، بدون اینکه شرط کنار هم بودن از بین برود. اگر بسته شامل فرد متمایز باشد، برای هر ترتیب بیرونی، ترتیب داخلی داریم. پس طبق اصل ضرب:
اگر چند گروه باید جداگانه کنار هم بمانند، هر گروه را یک بسته میگیریم و تعداد ترتیبهای داخلی همهٔ بستهها را در تعداد ترتیبهای بیرونی ضرب میکنیم. اشتباه رایج این است که فقط جای بستهها را بشماریم و ترتیب داخلشان را فراموش کنیم.
کتاب درسی، صفحهٔ ۵۶
چیدن یکدرمیان
چیدن یکدرمیان
فرض کن برای عکس یادگاری، دانشآموزان دو پایه باید طوری در یک ردیف بایستند که هیچ دو نفرِ همپایه کنار هم نباشند. این بار بهجای بستهسازی، ابتدا الگوی جای پایهها را مشخص میکنیم؛ هنوز کاری نداریم چه کسی در هر جایگاه میایستد.
اگر تعداد دو گروه برابر باشد، دو الگو داریم: ردیف یا با گروه اول شروع میشود یا با گروه دوم. پس از انتخاب الگو، افراد هر گروه را در جایگاههای مخصوص خودشان جابهجا میکنیم و تعداد حالتها را طبق اصل ضرب به دست میآوریم.
اگر یک گروه دقیقاً یک نفر بیشتر داشته باشد، فقط یک الگو ممکن است: گروه پرجمعیتتر باید هم در ابتدای ردیف باشد و هم در انتهای آن. اگر اختلاف تعداد بیشتر از یک نفر باشد، چیدن یکدرمیان ممکن نیست.
نکتهٔ کلیدی: تعداد الگوهای جای گروهها را با تعداد ترتیبهای افراد اشتباه نگیر؛ ابتدا الگو، سپس ترتیب افراد!
کتاب درسی، صفحهٔ ۵۷
حذف ترتیبهای تکراری
حذف ترتیبهای تکراری
فرض کن چند مهره را در یک ردیف میچینی و دو مهره کاملاً همشکل و همرنگاند. اگر فقط جای این دو را عوض کنی، آیا ردیف تازهای دیده میشود؟ نه! پس هر جابهجایی لزوماً یک حالت تازه نیست.
برای شمارش، ابتدا تصور میکنیم همهٔ اشیا برچسب دارند و متمایزند؛ در این صورت ترتیب داریم. حالا برچسبهای اشیای یکسان را پاک میکنیم. اگر یک نوع شیء، بار تکرار شده باشد، هر ترتیب واقعی را بار شمردهایم؛ بنابراین باید بر تقسیم کنیم، نه بر .
اگر چند نوع شیء تکراری داشته باشیم، همین کار را برای هر نوع انجام میدهیم. با تعدادهای و شرط ، تعداد ترتیبهای متمایز برابر است با:
یادت باشد: اینجا اشیای یکسان مجبور نیستند کنار هم باشند؛ تقسیم میکنیم چون جابهجایی آنها بیاثر است، نه چون یک بستهاند.
کتاب درسی، صفحهٔ ۵۸
افراد متفاوت، جابهجایی بیاثر
افراد متفاوت، جابهجایی بیاثر
فرض کن با دوستانت به اردو رفتهای. برای مشخصکردن محل اسکان، مهم است چه کسانی در هر اتاقاند؛ نه اینکه نامشان را با چه ترتیبی بنویسیم. پس حتی وقتی همهٔ افراد متفاوتاند، بعضی جابهجاییها حالت تازهای نمیسازند.
برای اسکان نفر در سه اتاق مشخص با ظرفیتهای ، و نفر، میتوانیم ابتدا افراد را به ترتیب در یک صف بچینیم و بهترتیب به اتاقها بفرستیم. اما جابهجایی افراد داخل هر اتاق، ساکنان آن را تغییر نمیدهد. بنابراین هر اسکان را بار شمردهایم و تعداد اسکانها برابر است با:
راه دیگر، انتخاب پیاپی است: ابتدا ساکنان اتاق اول را انتخاب کنیم، سپس از افراد باقیمانده ساکنان اتاق دوم را؛ بقیه به اتاق سوم میروند:
این دو روش یک نتیجه دارند. دقت کن: افراد یکسان نیستند؛ فقط ترتیبشان درون اتاق بیاثر است.
کتاب درسی، صفحهٔ ۵۹
مثال حلشده
با ارقام چند عدد هفترقمی میتوان نوشت، اگر هر رقمِ دادهشده دقیقاً یک بار استفاده شود؟
در مجموع رقم داریم؛ اگر همه متمایز بودند، تعداد ترتیبها بود.
سه رقم یکساناند؛ جابهجایی آنها عدد تازهای نمیسازد، پس باید بر تقسیم کنیم.
دو رقم نیز یکساناند؛ برای حذف شمارشهای تکراریِ آنها، بر هم تقسیم میکنیم.
رقمهای و هرکدام یک بار آمدهاند و عامل تکرار دیگری نداریم؛ همچنین چون صفر نداریم، همهٔ ترتیبها عدد هفترقمی هستند.
بنابراین تعداد عددها برابر است با .
نکات مهم
- برای کنار هم نگهداشتن اشیا، آنها را بستهبندی میکنیم و تعداد ترتیبهای بستهها را در تعداد ترتیبهای داخلی ضرب میکنیم.
- در چیدن یکدرمیان، ابتدا الگوهای ممکنِ جای دو گروه را مشخص میکنیم و سپس ترتیب افراد هر گروه را میشماریم.
- برای حذف شمارشهای تکراری یا بیاثر، تعداد کل جایگشتها را بر تعداد جابهجاییهایی تقسیم میکنیم که نتیجهٔ تازهای نمیسازند.