به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
پرسش سوال

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

+4 امتیاز
814 بازدید
در دبیرستان توسط Poo (21 امتیاز)

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

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

1 پاسخ

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

این کلمه $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} $$

چگونه می توانم به محفل ریاضی کمک کنم؟

کانال تلگرام محفل ریاضی

سوالات مشابه

“ ریاضیدان، کسی است که شباهت ها را بین قضایا دریابد. ریاضیدان بهتر کسی است که بتواند شباهت بین برهان ها را ببیند. بهترین ریاضیدان کسی است که بتواند به شباهت بین نظریه ها توجه کند. و می توان تصور کرد که ریاضیدان نهایی کسی است که بتواند شباهت بین شباهت ها را مشاهده کند.
...