تسلسل ستانلي

في الرياضيات، متتالية ستانلي هي متتالية أعداد صحيحة يتم توليدها بواسطة خوارزمية جشعة تختار عناصر المتتالية لتجنب المتتابعات الحسابية .${\displaystyle S}$إذا كانت مجموعة منتهية من الأعداد الصحيحة غير السالبة لا تشكل فيها أي ثلاثة عناصر متتالية حسابية (أي مجموعة سالم-سبنسر )، فإن متتالية ستانلي المولدة من${\displaystyle S}$يبدأ من عناصر${\displaystyle S}$تُرتّب هذه المتتاليات ترتيبًا تصاعديًا، ثم تُختار بشكل متكرر كل عنصر لاحق من المتتالية ليكون عددًا أكبر من الأعداد المختارة مسبقًا، ولا تُشكّل معها أي متتابعة حسابية ثلاثية الحدود. سُمّيت هذه المتتاليات نسبةً إلى ريتشارد ب. ستانلي .

تتألف متتالية ستانلي، التي تبدأ من المجموعة الفارغة، من الأعداد التي لا تحتوي تمثيلاتها الثلاثية إلا على الرقمين 0 و1. ^{[ 1 ]} أي أنها، عند كتابتها بالنظام الثلاثي، تبدو كأعداد ثنائية . هذه الأعداد هي

0، 1، 3، 4، 9، 10، 12، 13، 27، 28، 30، 31، 36، 37، 39، 40، ... (التسلسل A005836 في OEIS )

بفضل بنائها كمتتالية ستانلي، تُعد هذه المتتالية أول متتالية خالية من التتابع الحسابي من الناحية المعجمية . عناصرها هي مجموع قوى مختلفة للعدد ثلاثة ، وهي الأعداد${\displaystyle n}$بحيث يكون${\displaystyle n}$معامل ذات الحدين المركزي هو 1 mod 3، والأعداد التي يكون تمثيلها الثلاثي المتوازن هو نفسه تمثيلها الثلاثي. ^{[ 2 ]}

إن بناء هذه المتتالية من الأعداد الثلاثية مماثل لبناء متتالية موزر-دي بروين ، وهي متتالية الأعداد التي لا تحتوي تمثيلاتها في النظام الرباعي إلا على الرقمين 0 و1، وبناء مجموعة كانتور كمجموعة جزئية من الأعداد الحقيقية في الفترة${\displaystyle [0,1]}$والتي تستخدم تمثيلاتها الثلاثية الأرقام 0 و 2 فقط. وبشكل أكثر عمومية، فهي متتالية منتظمة من الدرجة 2 ، وهي واحدة من فئة من المتتاليات الصحيحة المعرفة بعلاقة تكرار خطية مع مضاعف 2. ^{[ 3 ]}

تتضمن هذه المتتالية ثلاث قوى للعدد اثنين : 1، 4، و256 = 35 ⁺ 32 ⁺ 3 + 1. وقد افترض بول إيردوس أن هذه هي القوى الوحيدة للعدد اثنين التي تحتويها. ^{[ 4 ]}

لاحظ أندرو أودليزكو وريتشارد ب. ستانلي أن عدد العناصر يصل إلى عتبة معينة${\displaystyle n}$في التسلسل الثنائي الثلاثي، وفي تسلسلات ستانلي الأخرى التي تبدأ من${\displaystyle \{0,3^{k}\}}$أو${\displaystyle \{0,2\cdot 3^{k}\}}$ينمو بشكل متناسب مع${\displaystyle n^{\log _{2}3}\approx n^{0.631}}$للحصول على مجموعات بداية أخرى${\displaystyle \{0,s\}}$بدت متواليات ستانلي التي درسوها تنمو بشكل أكثر عشوائية، ولكنها في الوقت نفسه أكثر تباعدًا. ^{[ 1 ]} على سبيل المثال، الحالة غير المنتظمة الأولى هي${\displaystyle s=4}$، مما يؤدي إلى توليد التسلسل

0، 4، 5، 7، 11، 12، 16، 23، 26، 31، 33، 37، 38، 44، 49، 56، 73، 78، 80، 85، 95، 99، ... (التسلسل A005487 في OEIS )

افترض أودليزكو وستانلي أنه في مثل هذه الحالات، يكون عدد العناصر حتى أي عتبة${\displaystyle n}$يكون${\displaystyle O{\bigl (}{\sqrt {n\log n}}{\bigr )}}$أي أن هناك تباينًا في معدل نمو متواليات ستانلي بين تلك التي لها نمو مشابه للمتواليات الثنائية-الثلاثية، وتلك التي لها معدل نمو أقل بكثير؛ ووفقًا لهذا الافتراض، لا ينبغي أن تكون هناك متواليات ستانلي ذات نمو متوسط. ^{[ 1 ] [ 5 ]}

أثبت موي أن متتاليات ستانلي لا يمكن أن تنمو بشكل أبطأ بكثير من الحد المفترض لمتتاليات النمو البطيء. كل متتالية ستانلي لها${\displaystyle \Omega {\bigl (}{\sqrt {n}}{\bigr )}}$عناصر تصل إلى${\displaystyle n}$وبشكل أدق، أظهر موي أنه لكل تسلسل من هذا القبيل، كل${\displaystyle \varepsilon >0}$وجميعها كبيرة بما فيه الكفاية${\displaystyle n}$، عدد العناصر على الأقل${\displaystyle ({\sqrt {2}}-\varepsilon ){\sqrt {n}}}$[ ^{6 ] وفي} سياق متصل، أثبت داي وتشن أن عدد العناصر لا يقل عن${\displaystyle 1.77{\sqrt {n}}}$لعدد لا نهائي من${\displaystyle n}$[ ^{7 ]} كما أثبت رولنيك وفينكاتارامانا أن متواليات ستانلي التي تنمو على النحو ^التالي${\displaystyle n^{\log _{2}3}}$يمكن أن يكون العامل الثابت في معدلات نموهم أي عدد نسبي يكون مقامه قوة من قوى العدد ثلاثة. ^{[ 8 ]}

في عام 1936، قام بول إردوش وبال توران بدراسة شكل مختلف من المتتالية الثنائية الثلاثية (مع إضافة واحد إلى كل عنصر) ، ولاحظا أنها لا تحتوي على متتابعة حسابية ثلاثية الحدود، وافترضا (خطأً) أنها أكثر المتتاليات كثافةً التي لا تحتوي على متتابعة حسابية. ^{[ 9 ]}

في عمل غير منشور مع أندرو أودليزكو عام 1978، أجرى ريتشارد ب. ستانلي تجارب على الخوارزمية الجشعة لتوليد متواليات خالية من التتابع. وكانت المتواليات التي درسوها هي بالضبط متواليات ستانلي للمجموعات الأولية.${\displaystyle \{0,s\}}$[ ^{1 ]​}

تمت تسمية متواليات ستانلي، وتعميمها على مجموعات بداية أخرى غير${\displaystyle \{0,s\}}$، في ورقة بحثية نُشرت عام 1999 بواسطة إردوش (بعد وفاته) مع أربعة مؤلفين آخرين. ^{[ 5 ]}

• موي، ريتشارد أ. (2017)، متواليات ستانلي ذات الحرف الفردي ، arXiv : 1707.02037
• موي، ريتشارد أ.؛ رولنيك، ديفيد (2016)، "بنى جديدة في متواليات ستانلي"، الرياضيات المتقطعة ، 339 (2): 689-698 ، arXiv : 1502.06013 ، doi : 10.1016/j.disc.2015.10.017 ، MR 3431382 ، S2CID 6660477  
• رولنيك، ديفيد (2017)، "حول تصنيف متواليات ستانلي"، المجلة الأوروبية للتوافقية ، 59 : 51-70 ، arXiv : 1408.1940 ، doi : 10.1016/j.ejc.2016.06.004 ، MR 3546902 
• ساهني، مهتاب (2017)، قيم الأحرف في متواليات ستانلي ، arXiv : 1706.05444