جایگشتها و ترکیبها
جایگشتها آرایشهای مرتب اشیاء را شمارش میکنند و ترکیبها انتخابهای نامرتب را شمارش میکنند؛ این دو با هم هسته اصلی شمارش را تشکیل میدهند.
Definition
جایگشت یک مجموعه، آرایش مرتبی از عناصر آن است (یا یک نگاشت دوسویی از مجموعه به خودش)؛ ترکیب، انتخاب نامرتبی از تعداد ثابتی از عناصر از یک مجموعه است.
Scope
این موضوع به شمارش آرایشها (با تکرار و بدون تکرار)، انتخابها و اصلاحات آنها، از جمله درهمریختگیها (derangements)، جایگشتهای دایرهای و جایگشتهای با موقعیتهای محدود میپردازد. همچنین آمار جایگشتها مانند نزولها (descents)، وارونگیها (inversions) و ساختار چرخهای را معرفی میکند که شمارش ابتدایی را به نظریه مدرن و غنیتر گروه متقارن متصل میکند.
Core questions
- چند روش برای مرتب کردن n شیء متمایز وجود دارد و چند روش برای مرتب کردن r تا از آنها وجود دارد؟
- چگونه تکرار و عدم تمایز، تعداد آرایشها را تغییر میدهد؟
- درهمریختگیها (derangements) چه هستند و یک جایگشت تصادفی چند وقت یکبار هیچ عنصری را ثابت نمیکند؟
- کدام آمارهها در جایگشتها همتوزیع هستند؟
Key concepts
- فاکتوریل و فاکتوریل نزولی
- آرایشها با تکرار و بدون تکرار
- درهمریختگیها (Derangements)
- جایگشتهای دایرهای
- وارونگیها (Inversions) و نزولها (descents)
- اعداد استرلینگ
Key theories
- تجزیه چرخهای جایگشتها
- هر جایگشت به طور منحصر به فرد به چرخههای مجزا تجزیه میشود؛ شمارش جایگشتها بر اساس نوع چرخهای آنها توسط اعداد استرلینگ نوع اول کنترل میشود و زیربنای ساختار گروه متقارن است.
- شمارش درهمریختگیها (Derangement enumeration)
- تعداد جایگشتهای بدون نقطه ثابت، که از طریق اصل شمول و عدم شمول به دست میآید، به n!/e نزدیک میشود و نتیجه کلاسیک را میدهد که حدود 37% از جایگشتها درهمریختگی هستند.
Clinical relevance
شمارش جایگشت و ترکیب در احتمال (نتایج با احتمال برابر)، الگوریتمهای مرتبسازی و درهمسازی، طراحی آزمایش و فضاهای کلید رمزنگاری ظاهر میشود، جایی که اندازه فضای آرایش، دشواری و امنیت را تعیین میکند.
History
ترکیبیات جایگشتها توسط کار مکماهون در اوایل قرن بیستم در مورد تحلیل ترکیبیاتی نظاممند شد و بعدها از طریق نظریه مدرن آمار جایگشتها تعمیق یافت.
Key figures
- Percy MacMahon
- Richard P. Stanley
Related topics
Seminal works
- stanley2011
Frequently asked questions
- یک مجموعه n عنصری چند جایگشت دارد؟
- این مجموعه n! جایگشت دارد، که حاصلضرب تمام اعداد صحیح مثبت تا n است، زیرا هر یک از n موقعیت توسط یک عنصر متمایز باقیمانده پر میشود.
- درهمریختگی (derangement) چیست؟
- درهمریختگی جایگشتی است که در آن هیچ عنصری در موقعیت اصلی خود باقی نمیماند، مانند یک بازچینی که در آن هیچ نامهای به پاکت خودش برنمیگردد.