شمارش مضاعف

در ترکیبیات(به انگلیسی: Combinatorics)، دوگانه شمردن(به انگلیسی: Double counting)، که به آن شمارش مضاعف نیز گفته می‌شود، یک روش اثبات ترکیبیاتی برای نشان دادن آن است که دو عبارت با یکدیگر برابرند؛ با ادعا کردن این که دو روش برای شمردن اندازهٔ یک مجموعه وجود دارد. در این روش، که ون لینت و ویلسون آن را «یکی از مهمترین ابزارها در ترکیبیات» خوانده‌اند. به این صورت عمل می‌کنیم که یک مجموعه متناهی X عضوی را از دو دیدگاه متفاوت توصیف می‌کنیم و به دو عبارت مجزا می‌رسیم. چون هر دو عبارت برابر اندازهٔ یک مجموعه هستند پس با یکدیگر برابرند.

نمونه‌ها

تشکیل دسته‌ها

یک نمونه از روش دوگانه شمردن، شمردن تعداد راه‌هایی است که می‌توان یک دسته از افراد را از n نفر تشکیل داد، با این اجازه که هر عضو این مجموعه (حتی صفر تای آن‌ها) می‌تواند عضو این دسته باشد. به این صورت، داریم تعداد زیرمجموعه‌های که یک مجموعهٔ n عضوی می‌تواند داشته باشد می‌شماریم. یک راه برای تشکیل یک دسته این است که از هر شخص بخواهیم تا انتخاب کند که باشد یا نباشد. هر شخص دو جواب دارد-بله یا خیر-و این پاسخ از انتخاب دیگر افراد مستقل است؛ بنابراین تعداد حالات با $2\times 2\times ...\times 2=2^{n}$ برابر است. راه دیگر این است که اندازهٔ مجموعه باید عددی بین ۰ تا n باشد. پس برای هر k ممکن، تعداد راه‌های ممکن برای تشکیل یک دسته k عضوی از n نفر برابر ضریب دو جمله‌ای است.

${n \choose k}.$

از این رو کل تعداد دسته‌های ممکن برابر مجموع ضرایب دوجله‌ای روی k = 0, 1, 2, ... n است. برابر قرار دادن دو عبارت یک اتحاد را می‌دهد.

$\sum _{k=0}^{n}{n \choose k}=2^{n},$

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

$\sum _{k=d}^{n}{n \choose k}{k \choose d}=2^{n-d}{n \choose d}$

لم دست دادن

یک تئوری دیگر که معمولاً با دوگانه‌شماری اثبات می‌شود. بحث این گونه مطرح می‌شود که هر گراف ساده شامل(به انگلیسی: undirected graph)تعداد زوجی راس با درجه(به انگلیسی: degree) فرد دارد. یعنی، تعداد رئوسی که تعداد فردی یال دارند باید زوج باشد. در اصطلاحات محاوره‌ای تر، در یک مهمانی از افراد که تعدادی از آن‌ها با یکدیگر دست می‌دهند، تعداد زوجی از افراد باید با تعداد فردی از افراد دیگر دست دست داده باشند؛ به همین دلیل، به این نتیجه لم دست دادن نیز می گویند.

برای اثبات این با دوگانه‌شماری، راس (d(v را درجه راس v در نظر بگیرید. تعداد ظهور یال‌ها روی راس‌ها در یک گراف ممکن به دو روش شمرده شود:باجمع کردن درجات تمامی رئوس، یا با جمع کردن دو ظهور به ازای هر یال؛ بنابراین:

$\sum _{v}d(v)=2e\,$

که e تعداد یال‌ها است. پس جمع درجات رئوس یک گراف عددی زوج است، چیزی که اگر تعدادی فردی رای با درجه فرد داشته باشیم اتفاق نمی‌افتد. این حقیقت، با این اثبات، در ۱۷۳۶ صفحهٔ لئونارد اویلر(به انگلیسی: Leonhard Euler) دربارهٔ هفت پل کونیکسبرگ(به انگلیسی: Seven Bridges of Königsberg) پدیدار می‌شود، که اولین مطالعه بر روی نظریه گراف است.

شمردن درخت‌ها

فرمول کایلی این مطلب را می‌رساند که $1=2^{2-2}$ درخت برای دو راس، $3=3^{3-2}$ درخت برای سه راس، و $16=4^{4-2}$ درخت برای چهار راس وجود دارد.

اضافه کردن یک یال جهت‌دار به جنگل ریشه‌دار

T_n، تعداد درختهایی که می‌توان با n راس متفاوت تشکیل داد چقدر است؟ فرمول کایلی جواب را می‌دهد T_n = n^{n − 2}. آیگنر و زایگلر(۱۹۹۸)چهار اثبات برای این مطلب لیست می‌کنند، یکی از آن‌ها، یک اثبات به روش دوگانه شماری توسط جیم پیتمن است، «زیباترین آنها».

اثبات پیتمن تعداد دنباله‌هایی از یال‌های جهت‌دار که می‌توان به گراف تهی n راسی اضافه کرد به طوریکه از آن یک درخت ریشه‌دار تشکیل شود به دو روش متفاوت می‌شمارد.

یک راه برای تشکیل چنین دنباله‌ای شروع از یکی از T_n درخت ممکن و غیرریشه‌دار است، یکی از n راس را به عنوان ریشه انتخاب کن، سپس یکی از !(n-1)تا حالت دنباله‌های ممکن که n-1 تا یال را اضافه می‌کند انتخاب کن؛ بنابراین کل تعداد دنباله‌هایی که از این روش می‌توان ساخت برابر است با: T_nn(n − ۱)! = T_nn!. راه دیگر برای شمردن این دنباله‌ها که یال‌ها را یکی یکی در یک گراف تهی لحاظ بکنیم، و بعد تعداد انتخاب‌های ممکن در هر مرحله را بشماریم. فرض کنید که تا الان n - k یال اضافه شده باشد، بنابراین گرافی که با این یال‌ها تشکیل شده‌است یک جنگل ریشه دار با k درخت است، پس (n(k - 1 انتخاب برای لحاظ شدن یال بعدی وجود دارد:راس شروع‌شونده می‌تواند هر یک از n راس گراف باشد، و راس پایانی‌اش می‌توانند ریشه هر یک از k - 1 درخت‌ای بجز درخت شامل راس شروع‌شونده باشد؛ بنابراین، اگر تعداد انتخاب‌های مرحله اول و مرحله دوم و... در هم ضرب کنیم، کل تعداد حالات بدست می‌آید.

$\prod _{k=2}^{n}n(k-1)=n^{n-1}(n-1)!=n^{n-2}n!.$

با برابر قرار دادن این دو فرمول برای تعداد دنباله‌های یال‌ها، فرمول کایل نتیجه می‌شود:

$\displaystyle T_{n}n!=n^{n-2}n!$

و

$\displaystyle T_{n}=n^{n-2}.$

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

منابع

• ویکی‌پدیای انگلیسی
• Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis" (PDF), Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8: 128–140. ویرایش و ترجمه در Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. (1976), Graph Theory 1736–1936, Oxford University Press.