====== سوال ۷ ======

از مجموعه‌ی ‎$\{1‎, ‎2‎, ‎\ldots‎, ‎6\}$‎ چند زیرمجموعه می‌توان انتخاب کرد که
شامل دو عضو متوالی نباشند؟

  - ۳۵
  - ۲۰
  - ۳۶
  - ۱۵
  - ۲۱

<پاسخ>
گزینه (۵) درست است.

**راه‌حل اول:** زیرمجموعه‌های ۰ و ۱ عضوی همگی مطلوب هستند. به غیر از زیرمجموعه‌های $\{4,5\}،\{3,4\}،\{2,3\}،\{2,3\}،\{1,2\}$ و $\{5,6\}$ همه‌ی زیرمجموعه‌های دو عضوی مطلوب هستند. از بین زیرمجموعه‌های سه عضوی فقط زیرمجموعه‌های $\{1,4,6\}،\{1,3,6\}،\{1,2,5\}$ و $\{2,4,6\}$ مطلوب هستند. بنابراین تعداد زیرمجموعه‌های مطلوب برابر $\binom{6}{0} + \binom{6}{1}+[\binom{6}{2}-5]+4$ یعنی ۲۱ می‌باشد.

**راه‌حل دوم:**مسئله را در حالت کلی برای مجموعه‌ی $A=\{1,2,3,..,n\}$ حل می‌کنیم. تعداد زیرمجموعه‌های مطلوب را دراین حالت $a_n$ در نظر می‌گیریم و این زیرمجموعه‌ها را به دو دسته تقسیم می‌کنیم:

  - آن‌هایی که $n$ را دارند. هیچ یک از این زیرمجموعه‌ها $n-1$ را ندارند و مابقی اعضای آن‌ها اعضای مطلوبی از مجموعه‌ي $\{1,2,3,...,n-2\}$ می‌باشد که تعداد این زیرمجموعه‌ها برابر $a_{n-2}$ می‌باشد.
  - آن‌هایی که $n$ را ندارند. در این حالت هر یک از زیرمجموعه‌ها٬ زیرمجموعه‌های مطلوبی از مجموعه‌ی $\{1,2,3,...,n-1\}$  می‌باشد که تعداد این زیرمجموعه برابر $a_{n-1}$ می‌باشد.

بنابراین رابطه‌ی $a_n=a_{n-1}+a_{n-2}$ برقرار است که چون $a_1$ و $a_2=3$ مقادیر $a_5،a_4،a_3$ و $a_6$ به ترتیب برابر ۱۳٬۸٬۵ و ۲۱ به‌دست می‌آیند.



</پاسخ>
  * [[سوال ۸|سوال بعد]]
  * [[سوال ۶|سوال قبل]]