پرش به محتوای اصلی

ترکیبیات و اصول شمارش (گسسته)

خلاصه‌ای از درسنامه‌ی این مبحث در کوئیز سنتر — رایگان و بدون نیاز به ثبت‌نام

خلاصه‌ی درسنامه

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

ترکیبیات: چرا و چگونه؟

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

ترکیبیات ابزار شمارش است و در رمزنگاری، احتمال، تحلیل الگوریتم و شمارش مسیرها به کار می‌آید.

اصول پایه شمارش

اصل جمع و اصل ضرب: اگر کارها با «یا» به هم وصل شوند حالت‌ها را جمع می‌کنیم و اگر با «و» وصل شوند در هم ضرب می‌کنیم.

جایگشت P(n,r)P(n,r)ادامهٔ فرمول را افقی ببین

تعریف: انتخاب و چیدن rrادامهٔ فرمول را افقی ببین شیء از nnادامهٔ فرمول را افقی ببین شیء متمایز با در نظر گرفتن ترتیب.

P(n,r)=n!(n−r)!=n(n−1)(n−2)⋯(n−r+1)\boxed{P(n,r) = \frac{n!}{(n-r)!} = n(n-1)(n-2)\cdots(n-r+1)}ادامهٔ فرمول را افقی ببین

تعداد عوامل: دقیقاً rrادامهٔ فرمول را افقی ببین عامل، از nnادامهٔ فرمول را افقی ببین شروع و رو به پایین.

ترکیب (nr)\binom{n}{r}ادامهٔ فرمول را افقی ببین

تعریف: انتخاب rrادامهٔ فرمول را افقی ببین شیء از nnادامهٔ فرمول را افقی ببین شیء متمایز بدون در نظر گرفتن ترتیب.

(nr)=n!r!(n−r)!=P(n,r)r!\boxed{\binom{n}{r} = \frac{n!}{r!(n-r)!} = \frac{P(n,r)}{r!}}ادامهٔ فرمول را افقی ببین

رابطهٔ این دو: P(n,r)=(nr)×r!P(n,r) = \binom{n}{r} \times r!ادامهٔ فرمول را افقی ببین — زیرا هر ترکیب rrادامهٔ فرمول را افقی ببین عنصری را می‌توان به r!r!ادامهٔ فرمول را افقی ببین شکل مرتب کرد.

خواص مهم:

(nr)=(nn−r)(n0)=(nn)=1∑r=0n(nr)=2n\binom{n}{r} = \binom{n}{n-r} \qquad \binom{n}{0} = \binom{n}{n} = 1 \qquad \sum_{r=0}^{n} \binom{n}{r} = 2^nادامهٔ فرمول را افقی ببین

نکتهٔ طلایی: (nr)\binom{n}{r}ادامهٔ فرمول را افقی ببین تعداد زیرمجموعه‌های rrادامهٔ فرمول را افقی ببین عنصری یک مجموعهٔ nnادامهٔ فرمول را افقی ببین عنصری است.

مثلث پاسکال: مجموع ردیف nnادامهٔ فرمول را افقی ببینام برابر 2n2^nادامهٔ فرمول را افقی ببین است؛ قطر اول همه 11ادامهٔ فرمول را افقی ببین، قطر دوم اعداد طبیعی و قطر سوم اعداد مثلثی‌اند.

جایگشت با تکرار و دسته‌بندی

قضیه: اگر از nnادامهٔ فرمول را افقی ببین شیء، n1n_1ادامهٔ فرمول را افقی ببین تا از نوع اول تا nkn_kادامهٔ فرمول را افقی ببین تا از نوع kkادامهٔ فرمول را افقی ببینام باشد، تعداد جایگشت‌های متمایز برابر است با:

n!n1! n2! ⋯ nk!\boxed{\frac{n!}{n_1!\, n_2!\, \cdots\, n_k!}}ادامهٔ فرمول را افقی ببین

شهود: اگر همه متمایز بودند n!n!ادامهٔ فرمول را افقی ببین حالت داشتیم؛ اشیای هم‌نوع تفاوتی ایجاد نمی‌کنند، پس بر ni!n_i!ادامهٔ فرمول را افقی ببین تقسیم می‌شود.

دسته‌بندی (بلوک‌بندی): اشیای «کنار هم» را یک بلوک واحد فرض کن، بقیه را کنارش بچین، سپس جایگشت داخل بلوک را هم حساب کن.

چیدن یک‌درمیان: اگر m=nm = nادامهٔ فرمول را افقی ببین باشد جواب m!×n!×2m! \times n! \times 2ادامهٔ فرمول را افقی ببین است و اگر m=n+1m = n+1ادامهٔ فرمول را افقی ببین باشد گروه بزرگ‌تر اول و آخر را می‌گیرد و جواب m!×n!m! \times n!ادامهٔ فرمول را افقی ببین می‌شود. برای شرط «هیچ دو تایی کنار هم نباشند» از روش شکاف استفاده کن.

توزیع و معادلات ترکیبیاتی

مسئله: nnادامهٔ فرمول را افقی ببین شیء یکسان را بین kkادامهٔ فرمول را افقی ببین گروه توزیع کن — معادلِ یافتن جواب‌های صحیح نامنفی x1+⋯+xk=nx_1 + \cdots + x_k = nادامهٔ فرمول را افقی ببین.

روش ستاره و خط جواب می‌دهد:

(n+k−1k−1)\boxed{\binom{n+k-1}{k-1}}ادامهٔ فرمول را افقی ببین

برای شرط xi≥1x_i \geq 1ادامهٔ فرمول را افقی ببین فرمول به (n−1k−1)\binom{n-1}{k-1}ادامهٔ فرمول را افقی ببین و برای شرط کلی xi≥aix_i \geq a_iادامهٔ فرمول را افقی ببین با جایگزینی xi→xi−aix_i \to x_i - a_iادامهٔ فرمول را افقی ببین به (n−∑ai+k−1k−1)\binom{n - \sum a_i + k-1}{k-1}ادامهٔ فرمول را افقی ببین تبدیل می‌شود.

اگر اشیاء متمایز باشند و گروه‌ها هم متمایز، جواب knk^nادامهٔ فرمول را افقی ببین است، زیرا هر شیء مستقلاً می‌تواند در یکی از kkادامهٔ فرمول را افقی ببین گروه قرار گیرد.

اصل شمول و عدم شمول

قاعدهٔ طلایی: یک‌تایی‌ها را جمع کن، دوتایی‌ها را کم کن، سه‌تایی‌ها را اضافه کن و همین‌طور یک‌درمیان ادامه بده.

∣A1∪⋯∪An∣=∑∣Ai∣−∑∣Ai∩Aj∣+∑∣Ai∩Aj∩Ak∣−⋯|A_1 \cup \cdots \cup A_n| = \sum|A_i| - \sum|A_i \cap A_j| + \sum|A_i \cap A_j \cap A_k| - \cdotsادامهٔ فرمول را افقی ببین

کاربرد رایجش مسائل بخش‌پذیری و شمارش توابع پوشا است:

∣توابع پوشا∣=∑j=0n(−1)j(nj)(n−j)m\boxed{|\text{توابع پوشا}| = \sum_{j=0}^{n}(-1)^j \binom{n}{j}(n-j)^m}ادامهٔ فرمول را افقی ببین

اصل لانه کبوتری

اصل ساده: mmادامهٔ فرمول را افقی ببین کبوتر و nnادامهٔ فرمول را افقی ببین لانه با m>nm > nادامهٔ فرمول را افقی ببین ← حداقل یک لانه با ≥2\geq 2ادامهٔ فرمول را افقی ببین کبوتر.

تعمیم: با m=n(t−1)+1m = n(t-1)+1ادامهٔ فرمول را افقی ببین کبوتر ← حداقل یک لانه با ≥t\geq tادامهٔ فرمول را افقی ببین کبوتر.

این اصل برای مسائل وجودی به کار می‌رود: جایی که باید ثابت کنی حالتی حتماً وجود دارد، بدون آنکه بتوانی آن را بسازی. مثلاً در هر گراف ساده با p≥2p \geq 2ادامهٔ فرمول را افقی ببین رأس، حتماً دو رأس هم‌درجه وجود دارد.

قضیهٔ دوجمله‌ای

(x+y)n=∑k=0n(nk)xkyn−k\boxed{(x+y)^n = \sum_{k=0}^{n}\binom{n}{k}x^k y^{n-k}}ادامهٔ فرمول را افقی ببین

جملهٔ عمومی (a+b)n(a+b)^nادامهٔ فرمول را افقی ببین که شامل ara^rادامهٔ فرمول را افقی ببین باشد:

Tr+1=(nr)arbn−rT_{r+1} = \binom{n}{r} a^r b^{n-r}ادامهٔ فرمول را افقی ببین

با جایگذاری x=y=1x=y=1ادامهٔ فرمول را افقی ببین به ∑(nk)=2n\sum \binom{n}{k} = 2^nادامهٔ فرمول را افقی ببین و با x=1, y=−1x=1,\, y=-1ادامهٔ فرمول را افقی ببین به ∑(−1)k(nk)=0\sum (-1)^k\binom{n}{k} = 0ادامهٔ فرمول را افقی ببین می‌رسیم.

هویت‌های پرکاربرد: پاسکال (nr)=(n−1r−1)+(n−1r)\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}ادامهٔ فرمول را افقی ببین، واندرموند ∑k(mk)(nr−k)=(m+nr)\sum_{k} \binom{m}{k}\binom{n}{r-k} = \binom{m+n}{r}ادامهٔ فرمول را افقی ببین و جذب k(nk)=n(n−1k−1)k\binom{n}{k} = n\binom{n-1}{k-1}ادامهٔ فرمول را افقی ببین.

استراتژی حل مسائل شمارش

  1. آیا ترتیب مهم است؟ بله ← جایگشت، خیر ← ترکیب.
  2. اشیاء یکسان‌اند یا متمایز؟ متمایز در ظرف متمایز ← knk^nادامهٔ فرمول را افقی ببین؛ یکسان در ظرف متمایز ← ستاره و خط.
  3. شرط مجاورت؟ کنار هم ← بلوک‌بندی؛ عدم مجاورت ← روش شکاف.
  4. توزیع با حداقل؟ جایگزینی متغیر xi=yi+aix_i = y_i + a_iادامهٔ فرمول را افقی ببین.
  5. مسئلهٔ وجودی؟ اصل لانه کبوتری.
  6. بخش‌پذیری یا چند شرط هم‌زمان؟ اصل شمول و عدم شمول.

مباحث مرتبط

هم‌نهشتی و نظریهٔ اعداد (گسسته)گراف و مدل‌سازی (ریاضیات گسسته)مجموعه‌ها، الگو و دنباله (ریاضی ۱)مثلثات و دایرهٔ مثلثاتی (ریاضی ۱)توان گویا و عبارت‌های جبری (ریاضی ۱)معادله و نامعادلهٔ درجه دوم (ریاضی ۱)تابع، دامنه و برد (ریاضی ۱)شمارش، جایگشت و ترکیب (ریاضی ۱)احتمال و مفاهیم آمار (ریاضی ۱)مکان هندسی و استدلال (هندسه ۱)

ادامه‌ی این مبحث رو ببین

با ثبت‌نام رایگان، به بانک کامل سؤال، شبیه‌ساز کنکور و تحلیل پیشرفت دسترسی داری

ثبت‌نام رایگان