الانعكاس (الرياضيات المتقطعة)

يترك${\displaystyle \pi }$ليكن تبديلاً . يوجد انعكاس لـ${\displaystyle \pi }$بين${\displaystyle i}$و${\displaystyle j}$لو${\displaystyle i<j}$و${\displaystyle \pi (i)>\pi (j)}$يُشار إلى الانعكاس بزوج مرتب يحتوي إما على المواضع${\displaystyle (i,j)}$^{[ 1 ] [ 2 ]} أو العناصر${\displaystyle {\bigl (}\pi (i),\pi (j){\bigr )}}$[ ^{3 ] [ 4 ] [ 5 ]​}

مجموعة الانعكاسات هي مجموعة جميع الانعكاسات. مجموعة انعكاسات التبديل باستخدام الترميز المكاني هي نفسها مجموعة انعكاسات التبديل العكسي باستخدام الترميز العنصري مع تبديل عنصري كل زوج مرتب. وبالمثل، فإن مجموعة انعكاسات التبديل باستخدام الترميز العنصري هي نفسها مجموعة انعكاسات التبديل العكسي باستخدام الترميز المكاني مع تبديل عنصري كل زوج مرتب. ^{[ 6 ]}

تُعرَّف الانعكاسات عادةً للتباديل، ولكن يمكن تعريفها أيضًا للمتتاليات: ليكن${\displaystyle S}$ليكن تسلسلاً (أو تبديلاً متعدد المجموعات ^{[ 7 ]} ). إذا${\displaystyle i<j}$و${\displaystyle S(i)>S(j)}$إما زوج من الأماكن${\displaystyle (i,j)}$^{[ 7 ] [ 8 ]} أو زوج العناصر${\displaystyle {\bigl (}S(i),S(j){\bigr )}}$^{[ 9 ]} يُطلق عليه اسم قلب${\displaystyle S}$.

بالنسبة للتسلسلات، فإن الانعكاسات وفقًا للتعريف القائم على العناصر ليست فريدة، لأن أزواجًا مختلفة من الأماكن قد يكون لها نفس زوج القيم.

رقم الانعكاس${\displaystyle {\mathtt {inv}}(X)}$^{[ 10 ]} من سلسلة${\displaystyle X=\langle x_{1},\dots ,x_{n}\rangle }$، هو عدد عناصر مجموعة الانعكاس. وهو مقياس شائع لترتيب (يُسمى أحيانًا الترتيب المسبق) التبديل ^{[ 5 ]} أو المتتالية. ^{[ 9 ]} يتراوح عدد الانعكاس بين 0 و${\displaystyle {\frac {n(n-1)}{2}}}$بما في ذلك. التبديل ومعكوسه لهما نفس رقم الانعكاس.

على سبيل المثال${\displaystyle {\mathtt {inv}}(\langle 1,2,\dots ,n\rangle )=0}$بما أن التسلسل مرتب. كذلك، عندما${\displaystyle n=2m}$زوجي،${\displaystyle {\mathtt {inv}}(\langle m+1,m+2,\dots ,2m,1,2,\dots ,m\rangle )=m^{2}}$(لأن كل زوج${\displaystyle (1\leq i\leq m<j\leq 2m)}$(وهو انعكاس). يوضح هذا المثال الأخير أن المجموعة التي تبدو "مرتبة تقريبًا" يمكن أن يكون لها عدد تربيعي من الانعكاسات.

رقم الانعكاس هو عدد التقاطعات في مخطط السهم للتبديل، ^{[ 6 ]} مسافة كيندال تاو للتبديل من تبديل الهوية، ومجموع كل متجه من المتجهات المتعلقة بالانعكاس المحددة أدناه.

تشمل مقاييس الترتيب الأخرى الحد الأدنى لعدد العناصر التي يمكن حذفها من التسلسل للحصول على تسلسل مرتب بالكامل، وعدد وطول "التسلسلات" المرتبة داخل التسلسل، وقاعدة سبيرمان (مجموع المسافات بين كل عنصر وموضعه المرتب)، وأقل عدد من عمليات التبادل اللازمة لترتيب التسلسل. ^{[ 11 ]} يمكن تكييف خوارزميات الترتيب المقارن القياسية لحساب عدد الانعكاسات في زمن O( n log n ) . ^{[ 12 ]}

تُستخدم ثلاثة متجهات متشابهة لتكثيف معكوسات التبديل في متجه يحدده بشكل فريد. تُسمى هذه المتجهات عادةً متجهات الانعكاس أو شفرة ليمر . (يمكنك الاطلاع على قائمة المصادر هنا ).

تستخدم هذه المقالة مصطلح متجه الانعكاس (${\displaystyle v}$) مثل Wolfram . ^{[ 13 ]} يُطلق على المتجهين المتبقيين أحيانًا اسم متجه الانعكاس الأيسر والأيمن ، ولكن لتجنب الخلط مع متجه الانعكاس، تُطلق عليهما هذه المقالة اسم عدد الانعكاسات اليسرى (${\displaystyle l}$) وعدد الانقلابات اليمنى (${\displaystyle r}$). عند تفسيرها كعدد مضروب، فإن عدد الانعكاس الأيسر يعطي التباديل المعجمية العكسية، ^{[ 14 ]} وعدد الانعكاس الأيمن يعطي المؤشر المعجمي.

متجه الانعكاس${\displaystyle v}$: مع التعريف القائم على العناصر${\displaystyle v(i)}$هو عدد الانقلابات التي يكون مكونها الأصغر (الأيمن)${\displaystyle i}$[ ^{3 ]​}

${\displaystyle v(i)}$هو عدد العناصر في${\displaystyle \pi }$أكبر من${\displaystyle i}$قبل${\displaystyle i}$.

${\displaystyle v(i)~~=~~\#\{k\mid k>i~\land ~\pi ^{-1}(k)<\pi ^{-1}(i)\}}$

عدد الانقلابات اليسرى${\displaystyle l}$: مع التعريف القائم على المكان${\displaystyle l(i)}$هو عدد الانقلابات التي يكون مكونها الأكبر (الأيمن)${\displaystyle i}$.

${\displaystyle l(i)}$هو عدد العناصر في${\displaystyle \pi }$أكبر من${\displaystyle \pi (i)}$قبل${\displaystyle \pi (i)}$.

${\displaystyle l(i)~~=~~\#\left\{k\mid k<i~\land ~\pi (k)>\pi (i)\right\}}$

عدد الانقلابات إلى اليمين${\displaystyle r}$يُطلق عليه غالبًا اسم رمز ليمر : مع التعريف القائم على المكان${\displaystyle r(i)}$هو عدد الانقلابات التي يكون مكونها الأصغر (الأيسر)${\displaystyle i}$.

${\displaystyle r(i)}$هو عدد العناصر في${\displaystyle \pi }$أصغر من${\displaystyle \pi (i)}$بعد${\displaystyle \pi (i)}$.

${\displaystyle r(i)~~=~~\#\{k\mid k>i~\land ~\pi (k)<\pi (i)\}}$

كلاهما${\displaystyle v}$و${\displaystyle r}$يمكن إيجادها بمساعدة مخطط روث ، وهو عبارة عن مصفوفة تبديل حيث يتم تمثيل الرقم 1 بنقاط، وانعكاس (غالبًا ما يتم تمثيله بعلامة ×) في كل موضع توجد به نقطة على اليمين وأسفله.${\displaystyle r(i)}$هو مجموع الانعكاسات في الصف${\displaystyle i}$من مخطط روث، بينما${\displaystyle v(i)}$هو مجموع الانعكاسات في العمود${\displaystyle i}$مصفوفة التبديل للمصفوفة العكسية هي المصفوفة المنقولة ، لذلك${\displaystyle v}$أحد التبديلات هو${\displaystyle r}$ومعكوسها، والعكس صحيح.