نگاهی به ریاضیات پیشرفته/ترکیبیات
|
|
ترکیبیات شاخه ای از علم ریاضیات است که عمدتاً به شمارش، هم به عنوان وسیله و هم به عنوان هدف برای به دست آوردن نتایج، و خواص معین ساختارهای محدود مربوط می‌شود . ارتباط نزدیکی با بسیاری از حوزه های دیگر ریاضیات دارد و کاربردهای زیادی از منطق گرفته تا فیزیک آماری و از زیست شناسی تکاملی تا علوم کامپیوتر دارد .
دامنه کامل ترکیبیات مورد توافق جهانی قرار نگرفته است. به گفته HJ Ryser ، تعریف موضوع دشوار است زیرا از زیربخش های ریاضی زیادی عبور می کند. تا آنجا که یک منطقه را می توان با انواع مشکلاتی که به آن پرداخته توصیف کرد، ترکیبات با موارد زیر درگیر است:
- شمارش سازه‌های مشخص، که گاهی به‌عنوان آرایش‌ها یا پیکربندی‌ها به معنایی بسیار کلی، مرتبط با سیستم‌های محدود شناخته می‌شوند،
- وجود چنین ساختارهایی که معیارهای معینی را برآورده می کنند،
- ساخت این سازه ها، شاید از بسیاری جهات، و
- بهینه‌سازی : یافتن «بهترین» ساختار یا راه‌حل از میان چندین احتمال، خواه «بزرگترین»، «کوچک‌ترین» یا ارضای برخی معیارهای بهینه‌سازی دیگر .
لئون میرسکی گفته است: "ترکیب‌شناسی مجموعه‌ای از مطالعات مرتبط است که وجه اشتراک دارند و در عین حال به طور گسترده در اهداف، روش‌ها و درجه انسجامی که به دست آورده‌اند، متفاوت هستند." یکی از راه‌های تعریف ترکیب‌ها، شاید توصیف زیربخش‌های آن با مسائل و تکنیک‌هایشان باشد. این رویکردی است که در زیر استفاده می شود. با این حال، دلایل صرفاً تاریخی نیز برای گنجاندن یا عدم گنجاندن برخی موضوعات زیر چتر ترکیبیات وجود دارد. اگرچه عمدتاً به سیستم های محدود مربوط می شود، برخی از سؤالات و تکنیک های ترکیبی را می توان به یک تنظیم نامتناهی (به طور خاص، قابل شمارش ) اما گسسته گسترش داد.
ترکیبیات به دلیل گستردگی مشکلاتی که با آن برخورد می کند به خوبی شناخته شده است. مشکلات ترکیبی در بسیاری از حوزه‌های ریاضیات محض ، به ویژه در جبر ، نظریه احتمال ، توپولوژی ، و هندسه ، و همچنین در بسیاری از حوزه‌های کاربردی آن به وجود می‌آیند. بسیاری از سؤالات ترکیبی در طول تاریخ به صورت مجزا در نظر گرفته شده اند، و یک راه حل موقت برای یک مسئله ایجاد شده در برخی زمینه های ریاضی ارائه می دهند. با این حال، در اواخر قرن بیستم، روش‌های نظری قدرتمند و کلی توسعه یافتند و ترکیب‌ها را به شاخه‌ای مستقل از ریاضیات تبدیل کردند. یکی از قدیمی‌ترین و در دسترس‌ترین بخش‌های ترکیبیات، نظریه گراف است که به خودی خود پیوندهای طبیعی متعددی با سایر حوزه‌ها دارد. ترکیبیات به طور مکرر در علوم کامپیوتر برای به دست آوردن فرمول ها و تخمین ها در تجزیه و تحلیل الگوریتم ها استفاده می شود .
به ریاضیدانی که ترکیب‌شناسی را مطالعه می‌کند، ترکیب‌گرا می‌گویند .
شاخه های ترکیبیات
ویرایشترکیبات شمارشی
ویرایشترکیبات شمارشی کلاسیک‌ترین دامنه ترکیبات است و بر شمارش تعداد اشیاء ترکیبی خاص تمرکز دارد. اگرچه شمارش تعداد عناصر در یک مجموعه یک مسئله ریاضی نسبتاً گسترده است، بسیاری از مشکلاتی که در کاربردها ایجاد می‌شوند، توصیف ترکیبی نسبتاً ساده‌ای دارند. اعداد فیبوناچی مثال اصلی یک مسئله در شمارش ترکیب ها هستند. دوازده راه یک چارچوب یکپارچه برای شمارش جایگشت ها، ترکیب ها و پارتیشن ها فراهم می کند.
ترکیبات تحلیلی
ویرایشترکیبات تحلیلی با شمارش ساختارهای ترکیبی با استفاده از ابزارهای تحلیل پیچیده و نظریه احتمال سروکار دارند. برخلاف ترکیب‌های شمارشی که از فرمول‌های ترکیبی صریح و توابع تولیدکننده برای توصیف نتایج استفاده می‌کنند، هدف ترکیب‌های تحلیلی دستیابی به فرمول‌های مجانبی است.
تئوری تقسیم
ویرایشنظریه پارتیشن مسائل مختلف شمارش و مجانبی مربوط به پارتیشن‌های عدد صحیح را مطالعه می‌کند و ارتباط نزدیکی با سری‌های q، توابع ویژه و چندجمله‌ای متعامد دارد. در ابتدا بخشی از تئوری و تحلیل اعداد بود، اما اکنون بخشی از ترکیب یا یک رشته مستقل در نظر گرفته می شود. این شامل رویکرد دوگانه و ابزارهای مختلف در تحلیل و تئوری تحلیلی اعداد است و مربوط به مکانیک آماری است.
نظریه گراف
ویرایشنمودارها اشیاء اساسی در ترکیب بندی ها هستند. ملاحظات تئوری گراف از تعداد (به عنوان مثال، تعداد نمودارها در n رأس با k یال) تا ساختارهای موجود (مانند چرخه‌های همیلتونی) تا نمایش‌های جبری (مثلاً با توجه به نمودار G و دو عدد x و y، توته چندین Do انجام می‌دهد) را شامل می‌شود. جملات T G (x، y) تفسیر مختلط دارند؟). اگرچه ارتباط بسیار قوی بین نظریه گراف و ترکیبیات وجود دارد، اما گاهی اوقات به عنوان موضوعات جداگانه در نظر گرفته می شوند.در حالی که روش‌های ترکیبی برای بسیاری از مسائل نظریه گراف به کار می‌روند، این دو رشته عموماً برای یافتن راه‌حل‌هایی برای انواع مختلف مسائل استفاده می‌شوند.
تئوری طراحی
ویرایشتئوری طراحی مطالعه طرح های ترکیبی است که مجموعه ای از زیر مجموعه ها با ویژگی های تقاطع متمایز هستند. طرح های بلوک طرح های ترکیبی از نوع خاصی هستند. این ناحیه یکی از قدیمی ترین بخش های ترکیبیات است، مانند مسئله دانشجویی کرکمن که در سال 1850 ارائه شد. راه حل مسئله، مورد خاصی از سیستم اشتاینر است که سیستم ها نقش مهمی در طبقه بندی گروه های ساده محدود دارند. این حوزه بیشتر به نظریه کدگذاری و ترکیبات هندسی مربوط می شود.
هندسه محدود
ویرایشهندسه محدود مطالعه سیستم های هندسی است که فقط تعداد محدودی نقطه دارند. ساختارهایی شبیه به آنهایی که در هندسه های پیوسته یافت می شوند (صفحه اقلیدسی، فضای تصویر واقعی و غیره) اما به صورت ترکیبی تعریف شده اند، اصلی ترین ساختارهای مورد مطالعه هستند. این منطقه منبع غنی از نمونه ها برای تئوری طراحی است. نباید آن را با هندسه گسسته (هندسه مرکب) اشتباه گرفت.
تئوری نظم
ویرایشنظریه نظم مطالعه مجموعه های جزئی منظم، متناهی و نامتناهی است. نمونه های مختلفی از نظم جزئی در جبر، هندسه، نظریه اعداد، و در سراسر ترکیبات و نظریه گراف ظاهر می شود. کلاس ها و نمونه های قابل توجهی از نظم های جزئی شامل شبکه ها و جبرهای بولی است.
نظریه ماتروئید
ویرایشنظریه ماتروئید بخشی از هندسه را انتزاعی می کند. ویژگی مجموعه ها (معمولا مجموعه های محدود) بردارهایی را در فضای برداری مطالعه می کند که به ضرایب خاصی در یک رابطه وابستگی خطی وابسته نیستند. نه تنها ساختار، بلکه خواص شمارش نیز متعلق به نظریه ماتروئید است. نظریه ماتروئید توسط هاسلر ویتنی معرفی شد و به عنوان بخشی از نظریه نظم مورد مطالعه قرار گرفت. اکنون یک رشته تحصیلی مستقل با تعدادی از ارتباطات با سایر بخش های ترکیبی است.
ترکیبات افراطی
ویرایشترکیبات اکسترمال به بررسی سوالات اکسترمال در سیستم های مجموعه می پردازد. انواع سوالات مطرح شده در این مورد در مورد بزرگترین نمودار ممکن است که ویژگی های خاصی را برآورده می کند. به عنوان مثال، بزرگترین نمودار بدون مثلث در 2n راس، یک گراف دو قسمتی کامل Kn، n است. حتی یافتن پاسخ افراطی دقیق f(n) اغلب بسیار دشوار است و فقط می توان یک تخمین مجانبی ارائه داد. نظریه رمزی بخش دیگری از ترکیبات افراطی است. بیان می کند که هر پیکربندی به اندازه کافی بزرگ حاوی یک نظم است. این یک تعمیم پیشرفته از اصل کبوتر است.
ترکیبات احتمالی
ویرایشدر ترکیبات احتمالی، سؤالات این است: احتمال یک ویژگی خاص برای یک شی گسسته تصادفی، مانند یک نمودار تصادفی چقدر است؟ به عنوان مثال، میانگین تعداد مثلث ها در یک نمودار تصادفی چقدر است؟ روش‌های احتمالی نیز برای تعیین وجود اشیاء مرکب با ویژگی‌های تجویز شده خاص (که یافتن مثال‌های صریح ممکن است دشوار باشد) استفاده می‌شود، صرفاً با مشاهده اینکه احتمال انتخاب تصادفی یک شی با آن ویژگی‌ها بیشتر از 0 است. اغلب به آن اشاره می‌شود. به عنوان روش احتمالی) در کاربرد ترکیبات اکسترمال و نظریه گراف بسیار مؤثر بود. یک منطقه نزدیک مطالعه زنجیره های مارکوف محدود، به ویژه در اجسام مرکب است. در اینجا دوباره از ابزارهای احتمالی برای تخمین زمان اختلاط استفاده می شود.
ترکیبات جبری
ویرایشترکیبهای جبری رشته‌ای از ریاضیات است که از روش‌های جبر انتزاعی به‌ویژه نظریه گروهی و نظریه نمایش در زمینه‌های ترکیبی مختلف استفاده می‌کند و بالعکس از تکنیک‌های ترکیب‌بندی برای مسائل جبر استفاده می‌کند. ترکیبات جبری به طور مداوم در حال گسترش دامنه خود است، هم در موضوعات و هم در تکنیک ها، و می تواند به عنوان حوزه ای از ریاضیات در نظر گرفته شود که در آن تعامل روش های ترکیبی و جبری به ویژه قوی و قابل توجه است.
ترکیبات هندسی
ویرایشترکیبات هندسی مربوط به هندسه محدب و گسسته، به ویژه ترکیبات چند وجهی است. به عنوان مثال، می پرسد که یک پلی توپ محدب چند وجه از هر بعد می تواند داشته باشد. خواص متریک پلی توپ ها نیز نقش مهمی ایفا می کند، برای مثال قضیه کوشی در مورد صلبیت پلی توپ های محدب. پلی توپ های ویژه نیز در نظر گرفته می شوند، مانند پلی توپ های پرموتوهدرا، اسوکیاهدرا و بیرخوف. هندسه ترکیبی نامی تاریخی برای هندسه گسسته است.
ترکیبات حسابی
ویرایشترکیبهای حسابی از تعامل بین نظریه اعداد، ترکیب‌ها، نظریه ارگودیک و تحلیل هارمونیک پدید آمدند. این در مورد تخمین های مرکب مربوط به عملیات حسابی (جمع، تفریق، ضرب و تقسیم) است. نظریه اعداد جمعی (گاهی اوقات ترکیبات جمعی نامیده می شود) به یک مورد خاص اشاره دارد که در آن فقط عملیات جمع و تفریق درگیر است. یکی از تکنیک های مهم در ترکیب های حسابی، نظریه ارگودیک سیستم های دینامیکی است
ترکیبات بی نهایت
ویرایشترکیبات نامتناهی یا ترکیبات بی نهاییت یا تئوری مجموعه های ترکیبی امتدادی از ایده های ترکیبیات به مجموعه های نامتناهی است. این بخشی از تئوری مجموعه ها، حوزه ای از منطق ریاضی است، اما از ابزارها و ایده هایی از نظریه مجموعه ها و ترکیبات افراطی استفاده می کند. جیان کارلو روتا از نام ترکیب های پیوسته برای توصیف احتمال هندسی استفاده کرد، زیرا شباهت های زیادی بین شمارش و اندازه گیری وجود دارد.
منابع
ویرایشویکی پدیای انگلیسی