به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+4 امتیاز
769 بازدید
در دبیرستان توسط Poo (21 امتیاز)

اثبات کنید تعداد کلمات n حرفی با حروف aوb که دقیقا m عبارت ab دارند برابر است با انتخاب 2m+1 از n+1.

مرجع: کتاب انالیز ترکیبی علیرضا علیپور نشر الگو فصل 3 بخش ترکیب ها مساله شماره34

1 پاسخ

+1 امتیاز
توسط کیوان عباس زاده (3,110 امتیاز)

این کلمه $n$ حرفی قرار است شامل $m$ عبارت $ab$ باشد . پس شکل کلی کلمه به صورت زیر است :

$ \underbrace{b...b}  \underbrace{a...a}  \ ((ab)) \underbrace{b...b}  \underbrace{a...a} \ ((ab)) \ ... \ ((ab)) \underbrace{b...b}  \underbrace{a...a} \\  \ \ \ x_{1}  \  \ \ \ \ \  y_{1}  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_{2} \  \ \ \ \ \  \ \ y_{2}  \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_{m+1} \  \ \  y_{m+1} $

چون قرار است کلمه فقط حاوی $m$ عبارت $ab$ باشد پس قبل اولین عبارت $ab$ و بین هر دو عبارت متوالی $ab$ و بعد آخرین عبارت $ab$ نباید هیچ حرف $a$ قبل $b$ قرار گیرد. فرض کنید $ x_{k} $ و $ y_{k} $ ها به ترتیب تعداد حروف $b$ و $a$ در جایگاه های مشخص شده هستند پس :

$ x_{1} + y_{1} + x_{2} + y_{2} +...+ x_{m+1} + y_{m+1}=n-2m $

در این معادله $ x_{k} $ و $ y_{k} $ ها اعداد صحیح نامنفی هستند . پس تعداد این کلمات برابر است با تعداد جواب های معادله بالا در مجموعه اعداد صحیح نامنفی که برابر است با :

$$ \binom{(n-2m)+(2m+2)-1}{(2m+2)-1} = \binom{n+1}{2m+1} $$

این چرخ فلک که ما در او حیرانیم<br> فانوس خیال از او مثالی دانیم<br> خورشید چراغ دان و عالم فانوس<br> ما چون صوریم کاندرو حیرانیم
...