المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:ترکیبیات:دوگانه‌ شماری

دوگانه شماری

دوگانه شماری، روشی است برای اثبات تساوی دو عبارت،‌ از طریق طرح مساله‌ای ترکیبیاتی-شمارشی و اثبات این‌که هر دو عبارت، جواب‌ آن مساله اند. به عبارت دیگر، اثبات تساوی دو عبارت ریاضی با اثبات این‌که هردوی آن‌ها برابر با تعداد اعضای مجمومه‌ی واحدی هستند را دوگانه شماری، یا شمارش مضاعف گویند.

مثال‌‌ها

مثال ۱. برای هر عدد طبیعی $n$ نشان دهید: $$\sum \limits_{r=0}^{n} \binom{n}{r} = 2^n$$

پاسخ

مساله:‌ $n$ شکلات متمایز داریم. به چند طریق می‌توانیم تعدادی از آن‌ها را بخوریم؟ این امکان وجود دارد که هیج شکلاتی نخوریم.

راه حل اول: اگر بخواهیم $r$ شکلات بخوریم، $\binom{n}{r}$ طریق برای انتخاب آن‌ها وجود دارد. پس جواب مساله برابر است با: تعداد راه‌های خوردن $0$ شکلات + تعداد راه‌های خوردن $1$ شکلات +‌ … + تعداد راه‌های خوردن $n$ شکلات. یعنی:

$$\sum \limits_{r=0}^{n} \binom{n}{r}$$

راه حل دوم: برای هر شکلات مستقل از بقیه $2$ حالت وجود دارد:‌ یا خورده می‌شود یا نه. پس طبق اصل ضرب به $2^n$ طریق می‌توانیم تعدادی شکلات بخوریم.

بنابراین:

$$\sum \limits_{r=0}^{n} \binom{n}{r} = 2^n$$

مثال ۲. برای هر عدد طبیعی $n$ نشان دهید: $$\sum \limits_{k=1}^{n} 2 k-1 = n^2$$

پاسخ

مساله: به چند طریق می‌توانیم یک شکلات و یک آب‌نبات را به اعضای یک گروه $n$ نفره (هر کدام به یک‌نفر) بدهیم؟ می‌توانیم هر دو را هم به یک نفر بدهیم. راه حل اول: برای هر کدام (شکلات و آب‌نبات)، مستقل از دیگری فردی را به $n$ روش انتخاب می‌کنیم. پس طبق اصل ضرب جواب برابراست با $n^2$.

راه حل دوم: افراد را از $1$ تا $n$ شماره‌گذاری می‌کنیم. فرض کنیم شکلات را به فرد شماره $x$ و آب‌نبات را به $y$ بدهیم. روی کوچک‌ترین عدد از بین این دو یعنی $min(x,y)$ عدد حالت بندی میکنیم:

  • اگر $min(x,y)=n$ پس تنها راه این است که هر دو را به نفر $n$ ام بدهیم.
  • اکر $min(x,y)=n-1$ پس ۳ راه داریم: هر دو را به $n-1$ بدهیم، شکلات را به $n$ و آب‌نبات را به $n-1$ بدهیم، و برعکس.
  • برای $min(x,y)=i$: یک راه این است که هردو را به نفر $i$ ام بدهیم، یا شکلات را به $i$ بدهیم و آب‌نبات را به یکی از $i+1, i+2, ..., n$ یعنی $n-i$ نفر بعدی، یا برعکس، یعنی $2n-2i+1$ حالت. پس برای $min(x,y)=n-k$ تعداد راه‌ها برابر است با $2k-1$.

پس جواب مساله برابراست با: $$\sum \limits_{k=1}^{n} 2 k-1$$

پس:

$$\sum \limits_{k=1}^{n} 2 k-1 = n^2$$

مثال ۳. برای هر عدد طبیعی $n$ نشان دهید: $$\sum \limits_{r=1}^{n} r \binom{n}{r} = n 2^{n-1}$$

پاسخ

مساله: میخواهیم از بین دانش‌آموزان یک کلاس $n$ نفره گروه سرودی با حداقل یک عضو تشکیل داده و یکی‌از اعضای گروه را به عنوان سرگروه انتخاب کنیم. به چند طریق می‌توانیم این کار را انجام دهیم؟

راه حل اول: اگر گروه سرود $r$ عضو داشته باشد، به $\binom{n}{r}$ راه گروه سرود را و به $r$ روش سرگروه را از بین‌ ‌آن‌ها انتخاب می‌کنیم، یعنی $r \binom{n}{r}$ راه. پس جواب مساله برابراست با: $$\sum \limits_{r=1}^{n} r \binom{n}{r}$$

راه حل دوم: اول سرگروه را به $n$ طریق انتخاب می‌‌کنیم و بعد، هرکدام از دانش‌آموزان دیگیر یا در گروه سرود خواهد بود یا نه، پس هر کدام دو حالت دارند. پس طبق اصل ضرب جواب مساله برابراست با: $$n 2^{n-1}$$

پس: $$\sum \limits_{r=1}^{n} r \binom{n}{r} = n 2^{n-1}$$


ابزار صفحه