شمارش مضاعف

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

شمارش مضاعف یا دوگانه شمردن (به انگلیسی: Double Counting) یکی از روش‌های مهم شمردن در ترکیبیات برهانی است. مهم‌ترین کاربرد این نوع شمارش در اثبات اتحادهای ترکیبیاتی است. در واقع روش شمارش مضاعف، محاسبهٔ یک کمیت به دو صورت مختلف و به دست آوردن یک تساوی است.[۱]

به عنوان مثال با استفاده از این روش می‌توان اثبات کرد که ماتریسی را به ابعاد m \times n از اعداد حقیقی به طوری که مجموع درایه‌های هر سطر آن عددی مثبت و مجموع درایه‌های هر ستون آن منفی باشد، نمی‌توان ساخت.

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

  1. علیپور، علیرضا. ترکیبیات. ج. اول. فاطمی، ۱۳۸۲. شابک ‎۹۶۴-۳۱۸-۳۴۲-۴. بازبینی‌شده در ۱۷ آوریل ۲۰۱۲. 
  • Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis", 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 .