موضوع مقاله: شمارش مضاعف | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # شمارش مضاعف | مقدمه: در ترکیبیات، دوگانه شمردن، که به آن شمارش مضاعف نیز گفته می‌شود، یک روش اثبات ترکیبیاتی برای نشان دادن آن است که دو عبارت با یکدیگر برابرند؛ با ادعا کردن این که دو روش برای شمردن اندازهٔ یک مجموعه وجود دارد. | ## بخش 1: شمارش مضاعف | در این روش، که ون لینت و ویلسون آن را «یکی از مهمترین ابزارها در ترکیبیات» خوانده‌اند. به این صورت عمل می‌کنیم که یک مجموعه متناهی X عضوی را از دو دیدگاه متفاوت توصیف می‌کنیم و به دو عبارت مجزا می‌رسیم. نمونه‌ها تشکیل دسته‌ها یک نمونه از روش دوگانه شمردن، شمردن تعداد راه‌هایی است که می‌توان یک دسته از افراد را از n نفر تشکیل داد، با این اجازه که هر عضو این مجموعه (حتی صفر تای آن‌ها) می‌تواند عضو این دسته باشد. به این صورت، داریم تعداد زیرمجموعه‌های که یک مجموعهٔ n عضوی می‌تواند داشته باشد می‌شماریم. یک راه برای تشکیل یک دسته این است که از هر شخص بخواهیم تا انتخاب کند که باشد یا نباشد. هر شخص دو جواب دارد-بله یا خیر-و این پاسخ از انتخاب دیگر افراد مستقل است؛ بنابراین تعداد حالات با برابر است. | ## بخش 2: شمارش مضاعف | پس برای هر k ممکن، تعداد راه‌های ممکن برای تشکیل یک دسته k عضوی از n نفر برابر ضریب دو جمله‌ای است. از این رو کل تعداد دسته‌های ممکن برابر مجموع ضرایب دوجله‌ای روی k = 0, 1, 2, ... با یک روش دوگانه شماری مشابه می‌توان به یک اتحاد تعمیم‌یافته رسید لم دست دادن یک تئوری دیگر که معمولاً با دوگانه‌شماری اثبات می‌شود. در اصطلاحات محاوره‌ای تر، در یک مهمانی از افراد که تعدادی از آن‌ها با یکدیگر دست می‌دهند، تعداد زوجی از افراد باید با تعداد فردی از افراد دیگر دست دست داده باشند؛ به همین دلیل، به این نتیجه لم دست دادن نیز می گویند. تعداد ظهور یال‌ها روی راس‌ها در یک گراف ممکن به دو روش شمرده شود:باجمع کردن درجات تمامی رئوس، یا با جمع کردن دو ظهور به ازای هر یال؛ بنابراین: که e تعداد یال‌ها است. پس جمع درجات رئوس یک گراف عددی زوج است، چیزی که اگر تعدادی فردی رای با درجه فرد داشته باشیم اتفاق نمی‌افتد. | ## بخش 3: شمارش مضاعف | این حقیقت، با این اثبات، در ۱۷۳۶ صفحهٔ لئونارد اویلر دربارهٔ هفت پل کونیکسبرگ پدیدار می‌شود، که اولین مطالعه بر روی نظریه گراف است. آیگنر و زایگلر(۱۹۹۸)چهار اثبات برای این مطلب لیست می‌کنند، یکی از آن‌ها، یک اثبات به روش دوگانه شماری توسط جیم پیتمن است، «زیباترین آنها». اثبات پیتمن تعداد دنباله‌هایی از یال‌های جهت‌دار که می‌توان به گراف تهی n راسی اضافه کرد به طوریکه از آن یک درخت ریشه‌دار تشکیل شود به دو روش متفاوت می‌شمارد. یک راه برای تشکیل چنین دنباله‌ای شروع از یکی از Tn درخت ممکن و غیرریشه‌دار است، یکی از n راس را به عنوان ریشه انتخاب کن، سپس یکی از !(n-1)تا حالت دنباله‌های ممکن که n-1 تا یال را اضافه می‌کند انتخاب کن؛ بنابراین کل تعداد دنباله‌هایی که از این روش می‌توان ساخت برابر است با: . راه دیگر برای شمردن این دنباله‌ها که یال‌ها را یکی یکی در یک گراف تهی لحاظ بکنیم، و بعد تعداد انتخاب‌های ممکن در هر مرحله را بشماریم. فرض کنید که تا الان n - k یال اضافه شده باشد، بنابراین گرافی که با این یال‌ها تشکیل شده‌است یک جنگل ریشه دار با k درخت است، پس (n(k - 1 انتخاب برای لحاظ شدن یال بعدی وجود دارد:راس شروع‌شونده می‌تواند هر یک از n راس گراف باشد، و راس پایانی‌اش می‌توانند ریشه هر یک از k - 1 درخت‌ای بجز درخت شامل راس شروع‌شونده باشد؛ بنابراین، اگر تعداد انتخاب‌های مرحله اول و مرحله دوم و... | ## جمع‌بندی | با برابر قرار دادن این دو فرمول برای تعداد دنباله‌های یال‌ها، فرمول کایل نتیجه می‌شود: و همان‌طور که آیگنر و زایگلر شرح دادند، این فرمول و اثبات آن می‌توانند تعمیم بیابند تا تعداد حالات جنگل‌های ریشه‌دار با k درخت برای هر k بشمارد.