به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+4 امتیاز
773 بازدید
در دبیرستان توسط 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} $$

برای ترجمه ی یک جمله از انگلیسی به فرانسوی دو چیز ضروری است. اول، باید جمله ی انگلیسی را تماما بفهمیم. دوم، باید با اصطلاحات ویژه ای که در زبان فرانسوی هستند آشنا باشیم. این وضعیت خیلی شبیه هنگامی است که سعی داریم شرط را که با کلمات بیان شده است با نمادهای ریاضی بیان کنیم. اول، باید آن را تمام درک کنیم. دوم، باید با اصطلاحات ریاضی ریاضی آشنا باشیم.
...