التبديل المتناوب

في الرياضيات التوافقية ، يُعرف التبديل المتناوب (أو التبديل المتعرج ) للمجموعة {1، 2، 3، ...، ن } بأنه تبديل (ترتيب) لهذه الأعداد بحيث يكون كل عنصر أكبر أو أصغر بالتناوب من العنصر السابق له. على سبيل المثال، التبديلات المتناوبة الخمسة للمجموعة {1، 2، 3، 4} هي:

• 1، 3، 2، 4 لأن 1 < 3 > 2 < 4،              
• 1، 4، 2، 3 لأن 1 < 4 > 2 < 3،              
• ٢، ٣، ١، ٤ لأن ٢ < ٣ > ١ < ٤،              
• ٢، ٤، ١، ٣ لأن ٢ < ٤ > ١ < ٣، و              
• 3، 4، 1، 2 لأن 3 < 4 > 1 < 2.              

تمت دراسة هذا النوع من التبديل لأول مرة من قبل ديزيريه أندريه في القرن التاسع عشر. ^{[ 1 ]}

يستخدم المؤلفون المختلفون مصطلح التبديل المتناوب بشكل مختلف قليلاً: فبعضهم يشترط أن يكون العنصر الثاني في التبديل المتناوب أكبر من الأول (كما في الأمثلة أعلاه)، والبعض الآخر يشترط أن يكون التناوب معكوسًا (بحيث يكون العنصر الثاني أصغر من الأول، ثم الثالث أكبر من الثاني، وهكذا)، بينما يطلق آخرون على كلا النوعين اسم التبديل المتناوب.

تُعرف مسألة تحديد عدد التباديل المتناوبة A_{_n} للمجموعة {1, ..., n _} بمسألة أندريه . تُعرف هذه الأعداد بأعداد أويلر ، أو أعداد الزجزاج ، أو أعداد الصعود/الهبوط . عندما يكون n زوجيًا ، يُعرف العدد A_{_n} بعدد القاطع ، بينما يُعرف بعدد المماس إذا كان n فرديًا . هذه التسميات الأخيرة مستمدة من دراسة الدالة المولدة لهذه المتتالية.

يُقال إن التبديل c₁ _, ..., cₙ _متناوب إذا كانت عناصره تتناوب بين الارتفاع والانخفاض. وبالتالي، يجب أن يكون كل عنصر، باستثناء الأول والأخير، إما أكبر أو أصغر من العنصرين المجاورين له. يستخدم بعض المؤلفين مصطلح "متناوب" للإشارة فقط إلى التبديلات "التصاعدية-التنازلية" التي تحقق _c₁ < _c₂ > c₃ < ... ، بينما يُطلقون على التبديلات "التنازلية-التصاعدية" التي تحقق c₁ _> c₂ < c₃ _> ... اسم " _{التناوب} العكسي " . بينما يعكس مؤلفون آخرون هذا الاصطلاح، أو يستخدمون كلمة "متناوب" للإشارة إلى كل من التبديلات التصاعدية-التنازلية والتنازلية-التصاعدية _.

هناك تطابق بسيط واحد لواحد بين التبديلات من أسفل إلى أعلى ومن أعلى إلى أسفل: استبدال كل إدخال c _i بـ n + 1 - c _i يعكس الترتيب النسبي للإدخالات.

بحسب الاصطلاح، في أي نظام تسمية ، تعتبر التبديلات الفريدة ذات الطول 0 (تبديل المجموعة الفارغة ) و1 (التبديل المكون من عنصر واحد 1) متناوبة.

تُعرف مسألة تحديد عدد التباديل المتناوبة A _{_n} للمجموعة {1, ..., n } بمسألة أندريه . وتُعرف هذه الأعداد بأسماء مختلفة، منها أعداد أويلر ، وأعداد الزجزاج ، وأعداد الصعود/الهبوط ، أو بمزيج من هذه الأسماء. ويُستخدم مصطلح " أعداد أويلر" أحيانًا للإشارة إلى متتالية وثيقة الصلة. القيم القليلة الأولى من A _{_n} هي: 1، 1، 1، 2، 5، 16، 61، 272، 1385، 7936، 50521، ... (المتتالية A000111 في OEIS ) .

تُحقق هذه الأرقام علاقة تكرارية بسيطة، مشابهة لتلك الخاصة بأعداد كاتالان : من خلال تقسيم مجموعة التباديل المتناوبة (سواءً كانت من أعلى إلى أسفل أو من أعلى إلى أسفل) للمجموعة {  1،  2،  3،  ...، n ، n + 1 } وفقًا للموضع k لأكبر عنصر n + 1 ، يمكن إثبات أن     

${\displaystyle 2A_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}A_{k}A_{nk}}$

لكل n ≥ 1. استخدم أندريه (1881) هذه العلاقة التكرارية لإعطاء معادلة تفاضلية تحققها الدالة المولدة الأسية

${\displaystyle A(x)=\sum _{n=0}^{\infty }A_{n}{\frac {x^{n}}{n!}}}$

بالنسبة للمتتالية A _n . في الواقع، تعطي العلاقة التكرارية ما يلي:

${\displaystyle 2\sum _{n\geq 1}A_{n+1}{\frac {x^{n+1}}{(n+1)!}}=\sum _{n\geq 1}\sum _{k=0}^{n}{\frac {A_{k}}{k!}}{\frac {A_{n-k}}{(n-k)!}}{\frac {x^{n+1}}{n+1}}=\int \left(\sum _{k\geq 0}A_{k}{\frac {x^{k}}{k!}}\right)\left(\sum _{j\geq 0}A_{j}{\frac {x^{j}}{j!}}\right)\,dx-x}$

حيث نستبدل${\displaystyle j=n-k}$و${\displaystyle {\frac {x^{n+1}}{n+1}}=\int x^{k+j}\,dx}$وهذا يعطي المعادلة التكاملية

${\displaystyle 2(A(x)-1-x)=\int A(x)^{2}\,dx-x,}$

والتي تصبح بعد التفاضل${\displaystyle 2{\frac {dA}{dx}}-2=A^{2}-1}$يمكن حل هذه المعادلة التفاضلية بفصل المتغيرات (باستخدام الشرط الابتدائي) .${\displaystyle A(0)=A_{0}/0!=1}$)، ثم تم تبسيطها باستخدام صيغة نصف الزاوية الظلية ، مما أعطى النتيجة النهائية

${\displaystyle A(x)=\tan \left({\frac {\pi }{4}}+{\frac {x}{2}}\right)=\sec x+\tan x}$،

مجموع دالتي القاطع والمماس . تُعرف هذه النتيجة بنظرية أندريه . ويمكن تقديم تفسير هندسي لهذه النتيجة باستخدام تعميم لنظرية يوهان برنولي . ^{[ 2 ]}

ويترتب على نظرية أندريه أن نصف قطر تقارب المتسلسلة A ( x ) هو π /2. وهذا يسمح بحساب التوسع التقاربي ^{[ 3 ]} 

${\displaystyle A_{n}\sim 2\left({\frac {2}{\pi }}\right)^{n+1}n!\,.}$

في عام 1877 نشر فيليب لودفيج فون سيدل خوارزمية تجعل من السهل حساب A _n . ^{[ 4 ]}

${\displaystyle {\begin{array}{crrrcc}{}&{}&{\color {red}1}&{}&{}&{}\\{}&{\rightarrow }&{\color {blue}1}&{\color {red}1}&{}\\{}&{\color {red}2}&{\color {blue}2}&{\color {blue}1}&{\leftarrow }\\{\rightarrow }&{\color {blue}2}&{\color {blue}4}&{\color {blue}5}&{\color {red}5}\\{\color {red}16}&{\color {blue}16}&{\color {blue}14}&{\color {blue}10}&{\color {blue}5}&{\leftarrow }\end{array}}}$

خوارزمية سايدل لـ A _n

1. ابدأ بوضع الرقم 1 في الصف 0، وليكن k هو رقم الصف الذي يتم ملؤه حاليًا.
2. إذا كان k فرديًا، فضع الرقم الموجود في الطرف الأيسر من الصف k − 1 في الموضع الأول من الصف k ، واملأ الصف من اليسار إلى اليمين، بحيث يكون كل عنصر هو مجموع الرقم الموجود على اليسار والرقم الموجود في الأعلى.
3. في نهاية الصف، كرر الرقم الأخير.
4. إذا كان k زوجيًا، فتابع بنفس الطريقة في الاتجاه الآخر.

إن خوارزمية سايدل في الواقع أكثر عمومية بكثير (انظر شرح دومينيك دومونت ^{[ 5 ]} ) وتم إعادة اكتشافها عدة مرات بعد ذلك.

على غرار منهج سايدل، قدم كل من دي إي كنوت وتي جيه بوكهولتز معادلة تكرارية للأعداد A _{2 n} وأوصوا بهذه الطريقة لحساب أعداد برنولي B _{2 n} وأعداد أويلر E _{2 n} "على أجهزة الكمبيوتر الإلكترونية باستخدام عمليات بسيطة فقط على الأعداد الصحيحة". ^{[ 6 ]}

أعاد VI Arnold ^{[ 7 ]} اكتشاف خوارزمية Seidel، وفي وقت لاحق قام Millar وSloane وYoung بنشر خوارزمية Seidel تحت اسم تحويل boustrophedon .

الشكل المثلثي:

						1
					1		1
				2		2		1
			2		4		5		5
		16		16		14		10		5
	16		32		46		56		61		61
272		272		256		224		178		122		61

يوجد فقط OEIS : A000657  ، مع 1 واحد، و OEIS : A214267  ، مع 1ين، في OEIS .

توزيع مع إضافة 1 و 0 في الصفوف التالية:

						1
					0		1
				-1		-1		0
			0		-1		-2		-2
		5		5		4		2		0
	0		5		10		14		16		16
-61		-61		-56		-46		-32		-16		0

هذه هي OEIS : A239005  ، وهي نسخة مُوقّعة من OEIS : A008280  . القطر الرئيسي هو OEIS : A122045  . القطر الرئيسي هو OEIS : A155585  . العمود المركزي هو OEIS : A099023  . مجاميع الصفوف: 1، 1، -2، -5، 16، 61... انظر OEIS : A163747  . انظر المصفوفة التي تبدأ بـ 1، 1، 0، -2، 0، 16، 0 أدناه.

خوارزمية Akiyama-Tanigawa المطبقة على OEIS : A046978  ( n + 1 ) / OEIS : A016116  ( n ) تنتج:

1	1	١/٢​​​​	0	- 1/4​​​​	- 1/4​​​​	- 1 / 8​​
0	1	3 / 2​​	1	0	- 3/4​​​​
-1	-1	3 / 2​​	4	15 / 4​​
0	-5	- 15 / 2​​	1
5	5	- 51/2​​​​
0	61
-61

1. العمود الأول هو OEIS : A122045  . تحويله الثنائي يؤدي إلى:

1	1	0	-2	0	16	0
0	-1	-2	2	16	-16
-1	-1	4	14	-32
0	5	10	-46
5	5	-56
0	-61
-61

الصف الأول من هذه المصفوفة هو OEIS : A155585  . القيم المطلقة للعناصر القطرية المتزايدة هي OEIS : A008280  . مجموع العناصر القطرية هو − OEIS : A163747  ( n + 1 ).

2. العمود الثاني هو 1 1 −1 −5 5 61 −61 −1385 1385... . تحويله الثنائي يعطي:

1	2	2	-4	-16	32	272
1	0	-6	-12	48	240
-1	-6	-6	60	192
-5	0	66	32
5	66	66
61	0
-61

الصف الأول من هذه المصفوفة هو 1 2 2 −4 −16 32 272 544 −7936 15872 353792 −707584... . القيم المطلقة للتقسيم الثاني هي ضعف القيم المطلقة للتقسيم الأول.

خذ بعين الاعتبار خوارزمية Akiyama-Tanigawa المطبقة على OEIS : A046978  ( n ) / ( OEIS : A158780  ( n + 1 ) =  abs( OEIS : A117575  ( n )) + 1 = 1, 2, 2, ⁠ 3 / 2 ⁠ , 1, ⁠ 3 / 4 ⁠ , ⁠ 3 / 4 ⁠ , ⁠ 7 / 8 ⁠ , 1, ⁠ 17 / 16 ⁠ , ⁠ 17 / 16 ⁠ , ⁠ 33 / 32 ⁠ ... .

1	2	2	3 / 2​​	1	3 / 4​​	3 / 4​​
-1	0	3 / 2​​	2	5 / 4​​	0
-1	-3	- 3 / 2​​	3	25 / 4​​
2	-3	− ⁠ 27 / 2 ⁠	-13
5	21	- 3 / 2​​
-16	45
-61

العمود الأول الذي تكون قيمه المطلقة OEIS : A000111  يمكن أن يكون بسط دالة مثلثية.

OEIS : A163747  هو تسلسل تلقائي من النوع الأول (القطر الرئيسي هو OEIS : A000004  ). المصفوفة المقابلة هي:

0	-1	-1	2	5	-16	-61
-1	0	3	3	-21	-45
1	3	0	-24	-24
2	-3	-24	0
-5	-21	24
-16	45
-61

أول قطرين علويين هما −1 3 −24 402... = (−1) ^{n + 1}  × OEIS : A002832 . مجموع الأقطار السفلية هو 0 −2 0 10... = 2 × OEIS : A122045 ( n + 1).       

- OEIS : A163982  هو تسلسل تلقائي من النوع الثاني، مثل OEIS : A164555  / OEIS : A027642  على سبيل المثال . ومن ثم المصفوفة:

2	1	-1	-2	5	16	-61
-1	-2	-1	7	11	-77
-1	1	8	4	-88
2	7	-4	-92
5	-11	-88
-16	-77
-61

القطر الرئيسي، هنا 2 −2 8 −92... ، هو ضعف القطر العلوي الأول، هنا OEIS : A099023  . مجموع الأقطار الفرعية هو 2 0 −4 0... = 2  × OEIS : A155585 ( n + 1). OEIS : A163747 − OEIS : A163982 = 2 × OEIS : A122045 .          

ترتبط أعداد الزجزاج ذات الفهارس الفردية (أي أعداد المماس) ارتباطًا وثيقًا بأعداد برنولي . وتُعطى هذه العلاقة بالصيغة التالية:

${\displaystyle B_{2n}=(-1)^{n-1}{\frac {2n}{4^{2n}-2^{2n}}}A_{2n-1}}$

لـ n > 0.   

إذا كان Z _n يمثل عدد التباديل للمجموعة {1، ...، n } التي تكون إما لأعلى-لأسفل أو لأسفل-لأعلى (أو كليهما، لـ n < 2)، فإنه يتبع من الاقتران المذكور أعلاه أن Z _n =  2 A _n لـ n  ≥  2. القيم القليلة الأولى لـ Z _n هي 1، 1، 2، 4، 10، 32، 122، 544، 2770، 15872، 101042، ... (المتتالية A001250 في OEIS ) .

ترتبط أعداد أويلر المتعرجة بأعداد إنترينجر، والتي يمكن حساب أعداد الزجزاج منها. ويمكن تعريف أعداد إنترينجر بشكل تكراري كما يلي: ^{[ 8 ]}

${\displaystyle E(0,0)=1}$

${\displaystyle E(n,0)=0\qquad {\mbox{for }}n>0}$

${\displaystyle E(n,k)=E(n,k-1)+E(n-1,n-k)}$.

الرقم المتعرج ^رقم n يساوي رقم Entringer E ( n , n ).

تُسمى الأعداد A _{2 n} ذات الأسس الزوجية بأعداد القاطع أو أعداد الزيج : بما أن دالة القاطع زوجية ودالة الظل فردية ، فإنه يترتب على نظرية أندريه المذكورة أعلاه أنها تمثل البسط في متسلسلة ماكلورين لـ sec x . القيم القليلة الأولى هي 1، 1، 5، 61، 1385، 50521، ... (المتتالية A000364 في OEIS ) .

ترتبط أعداد القاطع بأعداد أويلر الموقعة (معاملات تايلور للقاطع الزائدي) بالصيغة E _{2 n}  =  ( − 1) ⁿ A _{2 n} . ( E _n  =  0 عندما يكون n فرديًا.)

وبالمثل، تُسمى الأعداد A _{2 n +1 ذات المؤشرات الفردية} بالأعداد المماسية أو الأعداد المتعرجة . القيم القليلة الأولى هي 1، 2، 16، 272، 7936، ... (التسلسل A000182 في OEIS ) .

يمكن استخدام العلاقات بين أعداد أويلر المتعرجة وأعداد أويلر وأعداد برنولي لإثبات ما يلي ^{[ 9 ] [ 10 ]}

${\displaystyle A_{r}=-{\frac {4^{r}}{a_{r}}}\sum _{k=1}^{r}{\frac {(-1)^{k}\,S(r,k)}{k+1}}\left({\frac {3}{4}}\right)^{(k)}}$

أين

${\displaystyle a_{r}={\begin{cases}(-1)^{\frac {r-1}{2}}(1+2^{-r})&{\mbox{if r is odd}}\\(-1)^{\frac {r}{2}}&{\mbox{if r is even}}\end{cases}},}$

${\displaystyle (x)^{(n)}=(x)(x+1)\cdots (x+n-1)}$يرمز إلى العامل التصاعدي ، و${\displaystyle S(r,k)}$يشير إلى أعداد ستيرلينغ من النوع الثاني .

• أطول سلسلة فرعية متناوبة
• تحويل بوستروفيدون
• السياج (في الرياضيات) ، مجموعة مرتبة جزئيًا لها تباديل متناوبة كامتدادات خطية لها

• أندريه، ديزيريه (1879)، “Développements de séc x et de tang x” ، Comptes rendus de l'Académie des Sciences ، 88 : 965– 967.

• André, Désiré (1881)، “Sur les permutations Alternées” (PDF) ، Journal de mathématiques pures et appliquées ، 3e série، 7 : 167– 184، مؤرشفة من الأصلي (PDF) في 22 نوفمبر 2021.

• هنري، فيليب؛ وانر، جيرهارد (2019). “خطوط متعرجة مع بورجي، بيرنولي، أويلر ومثلث سايدل – إنترينجر – أرنولد”. عنصر الرياضيات . 74 (4): 141– 168. دوى : 10.4171/م/393 ..

• ستانلي، ريتشارد ب. (2011). التوافقية العددية . المجلد  الأول (الطبعة الثانية  ). مطبعة جامعة كامبريدج .

• وايسشتاين، إريك دبليو. "التباديل المتناوبة" . عالم الرياضيات .
• روس تانغ، "صيغة صريحة لأعداد أويلر المتعرجة (أعداد لأعلى/لأسفل) من متسلسلات القوى" صيغة صريحة بسيطة لـ A _n .
• "دراسة استقصائية للتباديل المتناوبة" ، نسخة أولية من تأليف ريتشارد ب. ستانلي