اثبات ترکیبیاتی
اثبات ترکیبیاتی
فایده اثبات ترکیبی
استنلی (1997) مثالی از یک مسئله شمارش ترکیبی (شمارش تعداد دنباله های k زیر مجموعه S1، S2، … Sk، که می تواند از مجموعه ای از n مورد تشکیل شود به طوری که زیر مجموعه ها دارای یک تقاطع مشترک خالی باشند) ارائه می دهد. با دو دلیل مختلف برای حل آن. اثبات اول، که ترکیبی نیست، از استقراء ریاضی و توابع تولید استفاده می کند تا بفهمد که تعداد دنباله های این نوع (2k-1)n است. اثبات دوم مبتنی بر مشاهده است که 2k −1 زیر مجموعه مناسب از مجموعه {1، 2، …، k} و (2k −1)n توابع از مجموعه {1، 2، … وجود دارد. ، n} به خانواده زیر مجموعه های مناسب {1، 2، …، k}. دنباله هایی که باید شمارش شوند را می توان در مطابقت یک به یک با این توابع قرار داد، جایی که تابع تشکیل شده از یک دنباله معین از زیر مجموعه ها، هر عنصر i را به مجموعه نگاشت می کند {j | i ∈ Sj}.
استنلی می نویسد: «نه تنها اثبات ترکیبی فوق بسیار کوتاه تر از اثبات قبلی ما است، بلکه دلیل پاسخ ساده را کاملاً شفاف می کند. همانطور که در اینجا اتفاق افتاد، اغلب اینطور است که اولین اثباتی که به ذهن می رسد دشوار و بی ظرافت است، اما پاسخ نهایی یک اثبات ترکیبی ساده را نشان می دهد. استنلی هم به دلیل ظرافت بیشتر آنها نسبت به اثبات های غیرترکیبی و هم بینش بیشتری که در مورد ساختارهایی که توصیف می کنند ارائه می کند، یک اصل کلی را تدوین می کند که برهان های ترکیبی باید بر اثبات های دیگر ترجیح داده شوند، و بسیاری از مشکلات یافتن برهان های ترکیبی را به عنوان تمرین فهرست می کند. برای حقایق ریاضی که از طریق ابزارهای دیگر صادق هستند.
دانلود فایل اکسل فهرست بها 1400
منبع : ویکی پدیا