وارونگی (ریاضیات گسسته)
در علوم کامپیوتر و ریاضیات گسسته، دنباله‎ای وارونگی دارد که دو عنصر آن از نظم عادی خود خارج هستند. تعداد وارونگی‎های یک جایگشت به ما نشان می‎دهد که آن جایگشت تا چه‎حد از نظم طبیعی(همان ترتیب عادی)خود خارج است.
formula_1 را جایگشتی دلخواه درنظربگیرید. اگر در جایگشت formula_1، formula_3 و formula_4 باشد، آنگاه جفت اندیس formula_5 یا جفت عنصر formula_6، یک وارونگی از جایگشت formula_1 نامیده می‌شوند.
وارونگی معمولاً برای جایگشت‌ها تعریف می‌شود، ولی امکان دارد برای دنباله نیز تعریف شود:
formula_8 را یک دنباله (یا جایگشت Multi Set )درنظر بگیرید. اگر formula_3 و formula_10 باشد، به دو اندیس formula_5 یا دو عنصر formula_12 وارونگی formula_8 گفته می‌شود.
برای دنباله‌ها، وارونگی‌ها طبق تعریف مبتنی بر عنصر، یکتا نیستند، زیرا امکان دارد جفت اندیس‌های متفاوت مقادیر یکسانی داشته باشند.
مجموعه وارونگی، مجموعه همه وارونگی‌ها است. مجموعهٔ وارونگی یک جایگشت با توجه به تعریف مبتنی بر مکان، همان است که از معکوس مجموعه وارونگی جایگشت با توجه به تعریف مبتنی بر عنصر به دست می‎آید و بالعکس، تنها با رد و بدل عناصر از جفت‌ها.
عدد وارونگی شاخص بارز مجموعه وارونگی است. این یک اندازه‌گیری رایج از مرتب‌سازی یک جایگشت یا دنباله است.
عدد وارونگی تعداد برخوردها در نمودار پیکانی جایگشت است، آن، از جایگاه اصلی و جمع هر یک از بردارهای مربوط به وارونگی که در زیر تعریف شده‌است.
مهم نیست که از تعریف مبتنی بر مکان یا مبتنی بر عنصر وارونگی برای تعریف عدد وارونگی استفاده شود، زیرا یک جایگشت و معکوس آن دارای تعداد وارونگی‎های یکسانی هستند.
دیگر اندازه‌گیری‌های (پیش-) مرتب‌سازی شامل حداقل تعداد عناصری که می‌توانند از دنباله حذف شوند تا یک دنباله کاملاً مرتب حاصل شود، تعداد و طول «اجراهای» مرتب شده در داخل دنباله، Spearman Footrule (مجموع فاصله‌های هر عنصر از مکان قرارگیری آن پس از مرتب‌سازی) و کمترین تعداد جابجایی مورد نیاز برای مرتب‌سازی دنباله است. الگوریتم‌های مرتب‌سازی مقایسه استاندارد می‌توانند برای محاسبه تعداد وارونگی در زمان سازگار شوند.
سه بردار مشابه در حال استفاده هستند که وارونگی‌های یک جایگشت را در یک بردار خلاصه می‌کنند که آن جایگشت را به‌طور یکتایی مشخص می‌کند. آنها معمولاً "بردار وارونگی" یا "کد لیمر" نامیده می‌شوند. (لیستی از منابع در یافت می‌شود )
این مقاله از اصطلاح "بردار وارونگی استفاده می‌کند" (formula_14) مثل ولفرام. دو بردار باقی مانده گاهی "بردار وارونگی" "چپ" و "راست" نامیده "می‌شوند"، اما برای پیشگیری از اشتباه گرفتن با بردار وارونگی این مقاله آن‎ها "را تعداد معکوس چپ" (formula_15) و "تعداد معکوس راست" (formula_16)می‌نامد.
بعنوان عدد فاکتوریل تعبیر شده‌است. تعداد وارونگی سمت چپ جایگشت‌ها، شاخصreverse colexicographic و تعداد وارونگی سمت راست آن‎ها، شاخص lexicographic را در اختیار ما قرار می‌دهد.
بردار وارونگی (formula_14) : با توجه به تعریف "مبتنی بر عنصر،" formula_18 همان تعداد وارونگی‌هایی است که مؤلفه "کوچکتر" (سمت راست) آن‎ها formula_19 است.
formula_18 تعداد عناصر موجود در formula_1 است که از formula_19 بزرگترند و قبل از formula_19 قرار دارند.
تعداد معکوس سمت چپ (formula_15) : با تعریف "مبتنی به مکان،" formula_26 تعداد وارونگی‌هایی است که مؤلفه "بزرگتر" (راست) آن‎ها "formula_19" است.
formula_26 تعداد عناصر موجود در formula_1 بزرگتر از formula_30 قبل از formula_30 .
تعداد معکوس سمت راست (formula_16) : (اغلب به نام "" خوانده می‌شود)
با تعریف مبتنی بر "مکان،" formula_34 تعداد وارونگی‌هایی است که مؤلفه "کوچکتر" (سمت چپ) آنها formula_19 است.
formula_34 تعداد عناصری است که در formula_1 قرار دارند، از formula_30 کوچکترند و بعد از formula_30 قرار گرفته‌اند.formula_40
formula_14 و formula_16، هردو را می‌توان به کمک نمودار روته یافت؛ که یک ماتریس جابگشت، با ۱هایی است که توسط نقاط نشان داده می‌شوند و یک وارونگی (که اغلب توسط یک صلیب نمایش داده می‌شود) در هر موقعیتی که دارای نقطه ای در سمت راست و زیر آن است، مشخص می‌شود. formula_34 مجموع وارونگی‌های موجود در ردیف i ام نمودار روته است، در حالی که formula_18 مجموع وارونگی‌های موجود در ستون i ام نمودار روته است. ماتریس جایگشت معکوس، ترانهاده شده ماتریس اولیه است بنابراین مؤلفه formula_14 یک جایگشت، مؤلفه formula_16 معکوس آن می‌باشد و بلعکس.
جدول مرتب‌سازی زیر ۲۴ جایگشت حاصل از چهار عنصر با مجموعه‌های وارونگی مکان محور آنها، بردارهای مربوط به وارونگی و اعداد وارونگی را نشان می‌دهد. (ستون‌های کوچک بازتاب ستون‌هایی هستند که در کنار آنها قرار دارند و می‌توان از آنها برای مرتب کردنشان به ترتیب colexicographic استفاده کرد)
مشاهده می‌شود که formula_14 و formula_15 همیشه ارقام مشابهی دارند و این formula_15 و formula_16 هر دو مرتبط به مجموعه وارونگی مکان محور هستند. عناصر غیرمستقیم formula_15 جمع نمودارهای نزولی مثلث نمایش داده شده و همین موارد از formula_16 جمع نمودارهای صعودی آن هستند. (جفت‌های موجود در نمودارهای نزولی دارای مؤلفه‌های راست ۲، ۳، ۴ مشترک هستند، در حالی که جفت‌های موجود در نمودارهای صعودی دارای مؤلفه‌های چپ ۱، ۲، ۳ مشترک هستند). )
ترتیب پیش فرض جدول، ترتیب reverse colexicographic جایگشت formula_1 است، که همان ترتیب colexicographic formula_15 است. ترتیب lexicographic formula_1، همان ترتیب lexicographic formula_16 است.
در ریاضیات ترتیب lexicographic یا (ترتیب الفبایی) نوعی سازماندهی است که در آن کلمات به‎ترتیب الفبایی براساس ترتیب الفبایی حروف تشکیل دهنده‎ی آن‎ها مرتب می‎شوند. همچنین اگر طول دو کلمه باهم متفاوت بود کلمه با طول کمتر اولویت پیدا می‎کند. این نوع سازمان‎دهی به‎صورت کلی در مورد دنباله‎هایی به‎کار می‎روند که
اعضای آن‎ها متناهی باشند و از یک جامعه خاص و متناهی انتخاب شوند که به این جامعه الفبا گفته می‎شود. در مباحث علوم کامپیوتر چنین دنباله‎هایی به‎اصطلاح رشته‎ای از کاراکترها یا ارقام نامیده می‎شوند. به‎طوز مثال با این ترتیب داریم : 25 < 34
این ترتیب به‎طریقی در مقابل ترتیب lexicographic قرار دارد. چون در ترتیب lexicographic به‎دنبال اولین رقم از سمت چپ می‎باشیم که با رقم در همین جایگاه از یک دنباله
دیگر متفاوت باشد اما در ترتیب colexicographic، ما به‎دنبال آخرین رقم از سمت چپ (اولین رقم از سمت راست) می‎باشیم که با رقم موجود در همین جایگاه از دنباله دیگر
متفاوت باشد. به‎طور مثال با ترتیب colexicographic داریم : 34 < 25
مجموعه جایگشت‌های "n مورد،" می‌تواند ساختار یک دستورالعمل جزئی را بدهد، که ترتیب ضعیف جایگشت‌ها نامیده می‌شود، و یک شبکه تشکیل می‌دهد.
اگر یک جایگشت به هر مجموعه وارونگی، با استفاده از تعریف مبتنی بر مکان اختصاص داده شود، نظم حاصل از جایگشت‌ها، همان permutohedron است، که در آن یک لبه مربوط به مبادله دو عنصر با مقادیر متوالی است. این ترتیب ضعیف جایگشت است. اگر یک جایگشت به هر مجموعه وارونگی با استفاده از تعریف مبتنی بر مکان تخصیص داده شود، نظم حاصل یک گراف Cayley خواهد بود، که در آن یک لبه مربوط به تعویض دو عنصر موجود در مکان‌های متوالی است. این نمودار Cayley از یک گروه متقارن، مشابه با permutohedron است، اما با جایگزینی هر جایگشت با معکوس آن حاصل می‌شود.توالی‌های موجود در OEIS :