====== سوال ۹ ======


گراف ۲۰ راسی زیر با راس‌های $1, 2, \cdots , 20$ را در نظر بگیرید. به چند طریق می‌توان از این گراف تعدادی یال حذف کرد به طوری که گراف همبند بماند؟ توجه کنید یک حالت این است که هیچ یالی حذف نکنیم.

{{ :سوالات_المپیاد:مرحله‌ی_دوم:دوره‌ی_۲۶:selection_010.png |}}

  - $207391$
  - $946025$
  - $2 \times 4^{10}$
  - $834261$
  - $738634$




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

$a_n$ را تعداد حالات خواسته شده برای یک گراف $2n$-راسی در نظر می‌گیریم. $b_n$ را نیز مانند $a_n$‌ تعریف می‌کنیم؛ با این تفاوت که از قبل بدانیم بین دو راس سمت چپ مسیری وجود داشته است. داریم:

$$a_n=3a_{n-1}+b_{n-1}$$

و 

$$b_n=4a_{n-1}+2b_{n-1}$$

از روابط بازگشتی بالا مقدار $a_{10}$ که پاسخ مسئله است به‌دست می‌آید.

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