قانون ليمر

في الرياضيات ، وتحديداً في علم التوافيق ، يُعدّ رمز ليمر طريقةً خاصةً لترميز كل تبديل ممكن لسلسلة من n عدد. وهو مثال على مخطط ترقيم التباديل، وجدول معكوس .

سُميت شفرة ليمر نسبةً إلى دي إتش ليمر ، ^{[ 1 ]} ولكن الشفرة كانت معروفة منذ عام 1888 على الأقل. ^{[ 2 ]}

الكود

يستفيد قانون ليمر من حقيقة وجود

n!=n\times (n-1)\times \cdots \times 2\times 1

تباديل متتالية من n عددًا. إذا تم تحديد تبديل σ بواسطة المتتالية ( _σ1, ..., σn ) لصورها من 1، ...، _n ، فإنه يُشفّر بواسطة متتالية من n عددًا، ولكن ليست كل هذه المتتاليات صالحة لأن كل عدد يجب استخدامه مرة واحدة فقط. على النقيض من ذلك، تختار التشفيرات التي نناقشها هنا العدد الأول من مجموعة من n قيمة، والعدد التالي من مجموعة ثابتة من $n$ $- 1$ قيمة، وهكذا مع تقليل عدد الاحتمالات حتى العدد الأخير الذي يُسمح له بقيمة ثابتة واحدة فقط؛ كل متتالية من الأعداد المختارة من هذه المجموعات تُشفّر تبديلًا واحدًا. بينما يمكن تعريف العديد من التشفيرات ، فإن لرمز ليمر العديد من الخصائص المفيدة الإضافية؛ فهو المتتالية

L(\sigma )=(L(\sigma )_{1},\ldots ,L(\sigma )_{n})\quad {\text{حيث}}\quad L(\sigma )_{i}=\#\{j>i:\sigma _{j}<\sigma _{i}\},

بمعنى آخر، يحسب المصطلح L ( σ ) _i عدد الحدود في ( σ ₁ , ..., σ _n ) إلى يمين σ _i التي هي أصغر منها، وهو رقم بين 0 و $n - i$ ، مما يسمح بـ $n + 1 - i$ قيم مختلفة.

يُطلق على زوج المؤشرات ( $i$ , j ) حيث $i < j$ و $σi > σj$ اسم انعكاس لـ σ ، و L ( σ ) _i يحسب عدد الانعكاسات ( i , j ) مع تثبيت i وتغيير j . وبالتالي، فإن $L$ $(σ) 1 + L (σ) 2 + \dots + L (σ) n$ هو العدد الإجمالي لانعكاسات σ ، وهو أيضًا عدد عمليات النقل المتجاورة اللازمة لتحويل التبديل إلى تبديل الوحدة. تشمل الخصائص الأخرى لرمز ليمر أن الترتيب المعجمي لترميز تبديلين هو نفسه ترتيب تسلسلاتهما ( σ1 ، ...، _σn) _{، وأن أي قيمة} $0$ في الرمز تمثل الحد الأدنى من اليمين إلى اليسار في التبديل (أي أن $σi أصغر من أي σj$ $على$ يمينه $)$ ، وأن القيمة $n$ $-$ $i$ في الموضع i تشير بالمثل إلى الحد الأقصى من اليمين إلى اليسار، وأن رمز ليمر لـ σ يتطابق مع تمثيل نظام الأعداد العاملي لموضعه في قائمة تباديل n بالترتيب المعجمي (ترقيم المواضع بدءًا من 0).

يمكن الحصول على تنويعات لهذا الترميز عن طريق حساب الانعكاسات ( i , j ) لقيمة ثابتة لـ j بدلاً من قيمة ثابتة لـ i ، أو عن طريق حساب الانعكاسات بقيمة أصغر ثابتة $σj$ بدلاً من قيمة أصغر لـ i $،$ أو عن طريق حساب القيم غير المنعكسة بدلاً من القيم المنعكسة؛ ورغم أن هذا لا يُنتج نوعًا مختلفًا جوهريًا من الترميز، إلا أن بعض خصائص الترميز ستتغير تبعًا لذلك. على وجه الخصوص ، يُعطي حساب الانعكاسات بقيمة أصغر ثابتة $σj$ جدول انعكاسات $σ$ ، والذي يُمكن اعتباره رمز ليمر للتبديل العكسي.

التشفير وفك التشفير

الطريقة المعتادة لإثبات وجود n ! تبديلًا مختلفًا لـ n عنصرًا هي ملاحظة أنه يمكن اختيار العنصر الأول بـ $n$ طريقة مختلفة، والعنصر التالي بـ $n - 1$ طريقة مختلفة (لأن اختيار نفس رقم العنصر الأول ممنوع)، والعنصر الذي يليه بـ $n - 2$ طريقة مختلفة (لأن هناك الآن قيمتين ممنوعتين)، وهكذا. بترجمة حرية الاختيار هذه في كل خطوة إلى رقم، نحصل على خوارزمية ترميز، وهي خوارزمية تجد رمز ليمر لتبديل مُعطى. لا يُشترط افتراض أن العناصر المُبدَّلة هي أرقام، ولكن يلزم _ترتيب كلي لمجموعة العناصر. بما أن أرقام الترميز تبدأ من 0، فإن الرقم المناسب لترميز كل عنصر σᵢ هو عدد العناصر المتاحة في تلك النقطة (بحيث لا تظهر قبل الموضع i )، ولكنها أصغر من العنصر σᵢ _{المُختار} فعليًا. (لا بد أن تظهر مثل هذه الأشياء في موضع ما $j > i$ ، وسيكون ( i , j ) انعكاسًا، مما يدل على أن هذا الرقم هو بالفعل L ( σ ) _i .)

يمكن إيجاد هذا الرقم لترميز كل عنصر عن طريق العد المباشر، بعدة طرق (العد المباشر للانعكاسات، أو تصحيح العدد الإجمالي للعناصر الأصغر من عنصر معين، وهو رقم تسلسله بدءًا من 0 في المجموعة، بإضافة العناصر غير المتاحة في موضعه). وهناك طريقة أخرى، وإن كانت أقل كفاءة، وهي البدء بتبديل المجموعة {0، 1، ... $n - 1$ } المُحَصَّل عليه بتمثيل كل عنصر برقم تسلسله المذكور، ثم لكل عنصر x ، بالترتيب من اليسار إلى اليمين، تصحيح العناصر على يمينه بطرح 1 من جميع العناصر (التي لا تزال) أكبر من x (ليعكس ذلك حقيقة أن العنصر المقابل لـ x لم يعد متاحًا). فعلى سبيل المثال، سيعطي رمز ليمر لتبديل الأحرف B، F، A، G، D، E، C، مرتبة أبجديًا، أولًا قائمة أرقام التسلسل 1، 5، 0، 6، 3، 4، 2، والتي يتم تحويلها تباعًا.

{\begin{matrix}\mathbf {1} &5&0&6&3&4&2\\1&\mathbf {4} &0&5&2&3&1\\1&4&\mathbf {0} &4&2&3&1\\1&4&0&\mathbf {3} &1&2&0\\1&4&0&3&\mathbf {1} &2&0\\1&4&0&3&1&\mathbf {1} &0\\1&4&0&3&1&1&\mathbf {0} \\\end{matrix}}

حيث يكون السطر الأخير هو رمز ليمر (في كل سطر يتم طرح 1 من الإدخالات الأكبر الموجودة على يمين العنصر الغامق لتشكيل السطر التالي).

لفك تشفير رمز ليمر إلى تبديل لمجموعة معينة، يمكن عكس الإجراء السابق: لكل عنصر x ، بالترتيب من اليمين إلى اليسار، يتم تصحيح العناصر على يمينه بإضافة 1 إلى جميع العناصر (الحالية) الأكبر من أو تساوي x ؛ وأخيرًا، يتم تفسير التبديل الناتج {0، 1، ... $n - 1$ } كأرقام متسلسلة (وهو ما يعادل إضافة 1 إلى كل عنصر إذا كان المطلوب تبديل {1، 2، ... n }). بدلاً من ذلك، يمكن معالجة عناصر رمز ليمر من اليسار إلى اليمين، وتفسيرها كرقم يحدد الاختيار التالي لعنصر كما هو موضح أعلاه؛ وهذا يتطلب الاحتفاظ بقائمة بالعناصر المتاحة، والتي يتم منها إزالة كل عنصر مختار. في المثال، هذا يعني اختيار العنصر 1 من {A,B,C,D,E,F,G} (وهو B) ثم العنصر 4 من {A,C,D,E,F,G} (وهو F)، ثم العنصر 0 من {A,C,D,E,G} (مما يعطي A) وهكذا، لإعادة بناء التسلسل B,F,A,G,D,E,C.

تطبيقات في التوافقية والاحتمالات

استقلالية الرتب النسبية

يُعرّف رمز ليمر تقابلاً من المجموعة المتناظرة S _n إلى الضرب الديكارتي $[n]\times [n-1]\times \cdots \times [2]\times [1]$ ، حيث يشير [ k ] إلى مجموعة العناصر المكونة من k عنصر $\{0,1,\ldots ,k-1\}$ ونتيجة لذلك، في ظل التوزيع المنتظم على S _n ، فإن المكون L ( σ ) _i يحدد متغيرًا عشوائيًا موزعًا بشكل منتظم على $[n - i]$ ، وهذه المتغيرات العشوائية مستقلة عن بعضها البعض ، لأنها إسقاطات على عوامل مختلفة من حاصل ضرب ديكارتي .

عدد القيم الصغرى والعظمى من اليمين إلى اليسار

التعريف : في متتالية u = (uk ₎ 1≤k≤n _، يوجد حد أدنى (أو حد أقصى ) من اليمين إلى اليسار عند الرتبة k إذا كان u _k أصغر تمامًا (أو أكبر تمامًا) من كل عنصر u _i حيث i > k ، أي إلى يمينه.

ليكن B(k) (أو H(k) ) الحدث "يوجد حد أدنى (أو حد أقصى) من اليمين إلى اليسار عند الرتبة k "، أي أن B(k) هي مجموعة التباديل $\scriptstyle \ {\mathfrak {S}}_{n}$ والتي تُظهر حدًا أدنى (أو حدًا أقصى) من اليمين إلى اليسار عند الرتبة k . من الواضح أن لدينا

\{\omega \in B(k)\}\Leftrightarrow \{L(k,\omega )=0\}\quad {\text{and}}\quad \{\omega \in H(k)\}\Leftrightarrow \{L(k,\omega )=k-1\}.

وبالتالي، يمكن كتابة العدد N _b (ω) (على التوالي N _h (ω) ) للحد الأدنى (على التوالي الحد الأقصى) من اليمين إلى اليسار للتبديل ω كمجموع لمتغيرات عشوائية برنولي مستقلة ، كل منها بمعامل 1/k :

N_{b}(\omega )=\sum _{1\leq k\leq n}\ 1\!\!1_{B(k)}\quad {\text{and}}\quad N_{b}(\omega )=\sum _{1\leq k\leq n}\ 1\!\!1_{H(k)}.

في الواقع، بما أن L(k) يتبع القانون الموحد على $\scriptstyle \ [\![1,k]\!],$

\mathbb {P} (B(k))=\mathbb {P} (L(k)=0)=\mathbb {P} (H(k))=\mathbb {P} (L(k)=k-1)={\tfrac {1}{k}}.

الدالة المولدة للمتغير العشوائي برنولي $1\!\!1_{B(k)}$ يكون

G_{k}(s)={\frac {k-1+s}{k}},

وبالتالي فإن الدالة المولدة لـ N _b هي

G(s)=\prod _{k=1}^{n}G_{k}(s)\ =\ {\frac {s^{\overline {n}}}{n!}}

(باستخدام تدوين المضروب المتزايد )، مما يسمح لنا باستعادة صيغة المنتج للدالة المولدة لأعداد ستيرلينغ من النوع الأول (غير الموقعة).

مشكلة السكرتيرة

هذه مشكلة توقف مثالية، وهي مشكلة كلاسيكية في نظرية القرار والإحصاء والاحتمالات التطبيقية، حيث يتم الكشف تدريجياً عن تبديل عشوائي من خلال العناصر الأولى من رمز ليمر الخاص به، والهدف هو التوقف بالضبط عند العنصر k مثل σ(k)=n، في حين أن المعلومات المتاحة الوحيدة (القيم k الأولى من رمز ليمر) غير كافية لحساب σ(k).

بعبارة أبسط: يتم إجراء مقابلات مع سلسلة من المتقدمين (ن) واحداً تلو الآخر. يجب على القائم بالمقابلة اختيار أفضل متقدم، ولكن عليه اتخاذ قراره ("توظيف" أو "عدم توظيف") في الحال، دون مقابلة المتقدم التالي (وبالتالي دون مقابلة جميع المتقدمين).

وبالتالي، يعرف القائم بالمقابلة ترتيب المتقدم ^رقم k ، لذا، عند اتخاذ قراره رقم k ^، لا يعرف سوى العناصر k الأولى من كود ليمر، بينما يحتاج إلى معرفة جميعها لاتخاذ قرار مدروس. ولتحديد الاستراتيجيات المثلى (أي الاستراتيجية التي تزيد من احتمالية الفوز)، تُعد الخصائص الإحصائية لكود ليمر بالغة الأهمية.

يُزعم أن يوهانس كيبلر كشف بوضوح عن مشكلة السكرتيرة هذه لأحد أصدقائه في وقت كان يحاول فيه اتخاذ قراره واختيار واحدة من بين إحدى عشرة عروسًا محتملة لتكون زوجته الثانية. كان زواجه الأول تعيسًا، إذ تم ترتيبه دون استشارته، ولذلك كان قلقًا للغاية بشأن اتخاذ القرار الصحيح. ^{[ 3 ]}

مفاهيم مماثلة

تم استخدام العديد من البنى ذات الصلة. إحداها تُسمى غالبًا متجه الانعكاس، كما هو الحال في Wolfram Alpha . انظر أيضًا: الانعكاس (الرياضيات المتقطعة) § المتجهات المتعلقة بالانعكاس .

مراجع

↑ ليمر، د. هـ. (1960)، "تعليم الحاسوب حيلًا توافقية"، التحليل التوافقي ، وقائع الندوات في الرياضيات التطبيقية، المجلد 10، الصفحات 179-193 ، doi : 10.1090/psapm/010/0113289 ، ISBN 978-0-8218-1310-2، MR 0113289 {{citation}}عدم توافق رقم ISBN / التاريخ ( مساعدة )
^ Laisant، Charles-Ange (1888)، “Sur la numération Factorielle، application aux permutations” [ في الترقيم العاملي، التطبيق على التباديل ] ، Bulletin de la Société Mathématique de France (بالفرنسية)، 16 : 176–183 ، دوى : 10.24033/bsmf.378
↑ فيرغسون، توماس س. (أغسطس 1989)، "من حلّ مشكلة السكرتيرة؟" (ملف PDF) ، العلوم الإحصائية ، 4 (3): 282-289 ، doi : 10.1214/ss/1177012493 ، JSTOR 2245639

فهرس

مانتاشي، روبرتو؛ راكوتوندراجاو، فانجا (2001)، "تمثيل تبديل يعرف معنى "أويلري" ، الرياضيات المتقطعة وعلوم الحاسوب النظرية (4): 101-108 ، مؤرشف من الأصل في 16-11-2004
كنوت، دونالد ( 1981)، فن برمجة الحاسوب ، المجلد 3، ريدينغ: أديسون-ويسلي، الصفحات 12-13

[lehmer-1] ليمر، د. هـ. (1960)، "تعليم الحاسوب حيلًا توافقية"، التحليل التوافقي ، وقائع الندوات في الرياضيات التطبيقية، المجلد 10، الصفحات 179-193 ، doi : 10.1090/psapm/010/0113289 ، ISBN 978-0-8218-1310-2، MR 0113289 {{citation}}عدم توافق رقم ISBN / التاريخ ( مساعدة )

[laisant-2] Laisant، Charles-Ange (1888)، “Sur la numération Factorielle، application aux permutations” [ في الترقيم العاملي، التطبيق على التباديل ] ، Bulletin de la Société Mathématique de France (بالفرنسية)، 16 : 176–183 ، دوى : 10.24033/bsmf.378

[ferguson-3] فيرغسون، توماس س. (أغسطس 1989)، "من حلّ مشكلة السكرتيرة؟" (ملف PDF) ، العلوم الإحصائية ، 4 (3): 282-289 ، doi : 10.1214/ss/1177012493 ، JSTOR 2245639

[ 1 ]

[ 2 ]

[ 3 ]