شمارش مضاعف

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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


نمونه‌ها[ویرایش]

تشکیل دسته‌ها[ویرایش]

یک نمونه از روش دوگانه شمردن،شمردن تعداد راه‌هایی است که می‌توان یک دسته از افراد را از n نفر تشکیل داد،با این اجازه که هر عضو این مجموعه (حتی صفر تای آن‌ها) میتواند عضو این دسته باشد.به این صورت ، داریم تعداد زیرمجموعه‌های که یک مجموعه‌ی n عضوی می‌تواند داشته باشد می‌شماریم.یک راه برای تشکیل یک دسته این است که از هر شخص بخواهیم تا انتخاب کند که باشد یا نباشد.هر شخص دو جواب دارد-بله یا خیر-و این پاسخ از انتخاب دیگر افراد مستقل است.بنابراین تعداد حالات با 2\times 2\times ...\times 2 = 2^{n} برابر است.راه دیگر این است که اندازه‌ی مجموعه باید عددی بین 0 تا 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 تعداد یال‌ها است.پس جمع درجات رئوس یک گراف عددی زوج است،چیزی که اگر تعدادی فردی رای با درجه فرد داشته باشیم اتفاق نمی‌افتد.این حقیقت،با این اثبات،در 1736 صفحه‌ی لئونارد اویلر(به انگلیسی: Leonhard Euler) در باره هفت پل کونیکسبرگ(به انگلیسی: Seven Bridges of Königsberg) پدیدار می‌شود، که اولین مطالعه بر روی نظریه گراف است.


شمردن درخت‌ها[ویرایش]

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

Tn،تعداد درختهایی که می‌توان با n راس متفاوت تشکیل داد چقدر است؟فرمول کایلی جواب را می‌دهد Tn = nn − 2. آیگنر و زایگلر(1998)چهار اثبات برای این مطلب لیست می‌کنند،یکی از آن‌ها،یک اثبات به روش دوگانه شماری توسط جیم پیتمن است،"زیباترین آنها".

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

یک راه برای تشکیل چنین دنباله‌ای شروع از یکی از Tn درخت‌ ممکن و غیرریشه‌دار است، یکی از n راس را به عنوان ریشه انتخاب کن،سپس یکی از !(n-1)تا حالت دنباله‌های ممکن که n-1 تا یال را اضافه می‌کند انتخاب کن.بنابراین کل تعداد دنباله‌های از این روش می‌توان ساخت برابر است با: Tnn(n − 1)! = Tnn!. راه دیگر برای شمردن این دنباله‌ها که یال‌ها را یکی یکی در یک گراف تهی لحاظ بکنیم،و بعد تعداد انتخاب‌های ممکن در هر مرحله را بشماریم.فرض کنید که تا الان 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 بشمارد.

منابع[ویرایش]