تابع مولد برای تعداد راه های انتخاب 5 عدد متمایز از عددهای ۱ تا $n$ که هیچ دو تای آنها پشت سر هم نباشند بیابید.

Question

تابع مولد تعداد راه‌های انتخاب 5 عدد متمایز از اعدادِ 1، 2، 3، ... تا $n$ را بیابید به طوری که هیچ دوتای آنها اعدادی متوالی نباشند.

تلاش من: برای حل چنین مسأله‌ای باید آن‌را به شکل زیر نوشت:

$$x_1+x_2+x_3+x_4+x_5=n$$

که هر $x_i$ای مجموعه اعدادی از 1 تا $n$ را در برمی‌گیرد، اما چون $x$های بعدی همه عددی می‌توانند انتخاب کنند به جز عدد یک و به همین منوال $x$های دیگر نیز همان عدد را می‌توانند انتخاب کنند به جز یک عدد که همان عدد قبلی است پس این گونه باید نوشت که

$$\big(\big(x^1+x^2+\dots\big)\big(x^2+x^3+\dots\big)^4$$

Answer 1

تعداد حالت شرایط مساله را با نماد $X(n,5)$ نشان دهید.اگر بخواهیم $5$ عدد را از میان $n+1$ عدد طبیعی ابتدا با شرایط مساله انتخاب کنیم دو حالت داریم.حالت اول اینکه که در انتخاب ما $n+1$ باشد که در این حالت نباید $n$ باشد.حالت دوم اینکه $n+1$ در انتخاب ما نباشد یعنی هر $5$ عدد از $n$ عدد طبیعی ابتدا باشند.پس:

$X(n+1,5)=X(n,5)+X(n-1,4)$

بنابر این برای $n$ های به اندازه کافی بزرگ داریم:

$X(n,5)=X(n-1,5)+X(n-2,4)$

با توجه به اینکه

$X(n,2)=\binom{n}{2} -(n-1)= \frac{1}{2} (n-1)(n-2)$

رابطه بازگشتی بالا ساده می شود و مساله حل است.(بقیه برای خواننده).

$\Box$