به چند طریق میتوان روی شبکهی مختصات از نقطهی $(0,0)$ به $(4,3)$ رفت، اگر در هر قدم فقط یک واحد به راست یا یک واحد به بالا برویم؟
راهنمایی
هر مسیر یک رشته از ۷ حرکت است؛ چند تا از آنها «بالا» است؟
پاسخ و راهحل
پاسخ: $35$
هر مسیر دقیقاً $7$ قدم دارد که $3$ تای آنها «بالا» است. پس کافی است جای قدمهای بالا را انتخاب کنیم:
$$\binom{7}{3} = 35$$
مرحله ۱جایگشت و ترکیبمتوسطتألیفی لمیون
معادلهی $x_1 + x_2 + x_3 = 10$ چند جواب در اعداد صحیح نامنفی دارد؟
راهنمایی
ستاره و خط: ۱۰ ستاره و ۲ خط جداکننده.
پاسخ و راهحل
پاسخ: $66$
هر جواب معادل چیدن $10$ ستاره و $2$ خط در یک ردیف است:
$$\binom{12}{2} = 66$$
مرحله ۱رابطهی بازگشتیمتوسطتألیفی لمیون
چند رشتهی دودویی (از ۰ و ۱) به طول $6$ وجود دارد که در آن دو رقم $1$ پشت سر هم نیامده باشند؟
راهنمایی
$a_n$ را تعداد رشتههای خوب به طول $n$ بگیر و به رقم آخر نگاه کن.
پاسخ و راهحل
پاسخ: $21$
اگر رشته به $0$ ختم شود، بقیهاش هر رشتهی خوب به طول $n-1$ است؛ اگر به $1$ ختم شود، رقم قبلی حتماً $0$ است. پس $a_n = a_{n-1} + a_{n-2}$ با $a_1=2$ و $a_2=3$.
دنباله: $2, 3, 5, 8, 13, 21$ ← پاسخ $21$.