موضوع مقاله: وارونگی (ریاضیات گسسته) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # وارونگی (ریاضیات گسسته) | مقدمه: تعداد وارونگی های یک جایگشت به ما نشان می دهد که آن جایگشت تا چه حد از نظم طبیعی(همان ترتیب عادی)خود خارج است. | ## بخش 1: وارونگی (ریاضیات گسسته) | اگر در جایگشت ، و باشد، آنگاه جفت اندیس یا جفت عنصر ، یک وارونگی از جایگشت نامیده می‌شوند. وارونگی معمولاً برای جایگشت‌ها تعریف می‌شود، ولی امکان دارد برای دنباله نیز تعریف شود: را یک دنباله (یا جایگشت Multi Set )درنظر بگیرید. برای دنباله‌ها، وارونگی‌ها طبق تعریف مبتنی بر عنصر، یکتا نیستند، زیرا امکان دارد جفت اندیس‌های متفاوت مقادیر یکسانی داشته باشند. مجموعهٔ وارونگی یک جایگشت با توجه به تعریف مبتنی بر مکان، همان است که از معکوس مجموعه وارونگی جایگشت با توجه به تعریف مبتنی بر عنصر به دست می آید و بالعکس، تنها با رد و بدل عناصر از جفت‌ها. عدد وارونگی تعداد برخوردها در نمودار پیکانی جایگشت است، فاصله Kendall tau آن، از جایگاه اصلی و جمع هر یک از بردارهای مربوط به وارونگی که در زیر تعریف شده‌است. مهم نیست که از تعریف مبتنی بر مکان یا مبتنی بر عنصر وارونگی برای تعریف عدد وارونگی استفاده شود، زیرا یک جایگشت و معکوس آن دارای تعداد وارونگی های یکسانی هستند. دیگر اندازه‌گیری‌های (پیش-) مرتب‌سازی شامل حداقل تعداد عناصری که می‌توانند از دنباله حذف شوند تا یک دنباله کاملاً مرتب حاصل شود، تعداد و طول «اجراهای» مرتب شده در داخل دنباله، Spearman Footrule (مجموع فاصله‌های هر عنصر از مکان قرارگیری آن پس از مرتب‌سازی) و کمترین تعداد جابجایی مورد نیاز برای مرتب‌سازی دنباله است. | ## بخش 2: وارونگی (ریاضیات گسسته) | الگوریتم‌های مرتب‌سازی مقایسه استاندارد می‌توانند برای محاسبه تعداد وارونگی در زمان سازگار شوند. بردارهای مربوط به وارونگی سه بردار مشابه در حال استفاده هستند که وارونگی‌های یک جایگشت را در یک بردار خلاصه می‌کنند که آن جایگشت را به‌طور یکتایی مشخص می‌کند. دو بردار باقی مانده گاهی بردار وارونگی چپ و راست نامیده می‌شوند، اما برای پیشگیری از اشتباه گرفتن با بردار وارونگی این مقاله آن ها را تعداد معکوس چپ و تعداد معکوس راست می‌نامد. تعداد معکوس سمت چپ : با تعریف مبتنی به مکان، تعداد وارونگی‌هایی است که مؤلفه بزرگتر (راست) آن ها است. تعداد معکوس سمت راست : (اغلب به نام کد لیمر خوانده می‌شود) با تعریف مبتنی بر مکان، تعداد وارونگی‌هایی است که مؤلفه کوچکتر (سمت چپ) آنها است. و ، هردو را می‌توان به کمک نمودار روته یافت؛ که یک ماتریس جابگشت، با ۱هایی است که توسط نقاط نشان داده می‌شوند و یک وارونگی (که اغلب توسط یک صلیب نمایش داده می‌شود) در هر موقعیتی که دارای نقطه ای در سمت راست و زیر آن است، مشخص می‌شود. مجموع وارونگی‌های موجود در ردیف i ام نمودار روته است، در حالی که مجموع وارونگی‌های موجود در ستون i ام نمودار روته است. | ## بخش 3: وارونگی (ریاضیات گسسته) | ماتریس جایگشت معکوس، ترانهاده شده ماتریس اولیه است بنابراین مؤلفه یک جایگشت، مؤلفه معکوس آن می‌باشد و بلعکس. (ستون‌های کوچک بازتاب ستون‌هایی هستند که در کنار آنها قرار دارند و می‌توان از آنها برای مرتب کردنشان به ترتیب colexicographic استفاده کرد) مشاهده می‌شود که و همیشه ارقام مشابهی دارند و این و هر دو مرتبط به مجموعه وارونگی مکان محور هستند. عناصر غیرمستقیم جمع نمودارهای نزولی مثلث نمایش داده شده و همین موارد از جمع نمودارهای صعودی آن هستند. (جفت‌های موجود در نمودارهای نزولی دارای مؤلفه‌های راست ۲، ۳، ۴ مشترک هستند، در حالی که جفت‌های موجود در نمودارهای صعودی دارای مؤلفه‌های چپ ۱، ۲، ۳ مشترک هستند). این نوع سازمان دهی به صورت کلی در مورد دنباله هایی به کار می روند که اعضای آن ها متناهی باشند و از یک جامعه خاص و متناهی انتخاب شوند که به این جامعه الفبا گفته می شود. در مباحث علوم کامپیوتر چنین دنباله هایی به اصطلاح رشته ای از کاراکترها یا ارقام نامیده می شوند. اگر یک جایگشت به هر مجموعه وارونگی، با استفاده از تعریف مبتنی بر مکان اختصاص داده شود، نظم حاصل از جایگشت‌ها، همان permutohedron است، که در آن یک لبه مربوط به مبادله دو عنصر با مقادیر متوالی است. | ## جمع‌بندی | اگر یک جایگشت به هر مجموعه وارونگی با استفاده از تعریف مبتنی بر مکان تخصیص داده شود، نظم حاصل یک گراف Cayley خواهد بود، که در آن یک لبه مربوط به تعویض دو عنصر موجود در مکان‌های متوالی است.