\input style \chapnotrue\chapno=5\subchno=1\subsubchno=3 Óïðïóôá÷éí ó îåê äòõçõà ðåòåóôáîï÷ëõ ôïçï öå íõìøôéíîïöåóô÷á: $$ \pmatrix{ 1 & \ldots & 1 & 2 & \ldots & 2 & \ldots & m & \ldots & m \cr x'_{11} & \ldots & x'_{1p} & x'_{m1} & \ldots & x'_{mp} & \ldots & x'_{21} & \ldots & x'_{2p} \cr }, \eqno(33) $$ çäå~$x'=m+1-x$. Åóìé ðåòåóôáîï÷ëá~(32) óïäåòöéô $k$~óôïìâãï÷ ÷éäá~$y \atop x$, ôáëéè, þôï~$x1$, á îåòá÷åîóô÷ï~$xa_{i+1}$, òá÷îï ÷ ôïþîïóôé ðïìï÷éîå þéóìá óìõþáå÷, ëïçäá~$a_i \ne a_{i+1}$, é îåôòõäîï ÷éäåôø, þôï~$a_i=a_{i+1}=x_j$ òï÷îï ÷ $N n_j(n_j-1)/n(n-1)$~óìõþáñè, çäå~$N$---ïâýåå þéóìï ðåòåóôáîï÷ïë. Óìåäï÷áôåìøîï, $a_i=a_{i+1}$ òï÷îï ÷ $$ {N\over n(n-1)}(n_1(n_1-1)+\cdots+n_m(n_m-1))={N\over n(n-1)}(n_1^2+\cdots+n_m^2-n) $$ óìõþáñè, a~$a_i>a_{i+1}$ òï÷îï ÷ $$ {N\over 2n(n-1)}(n^2-(n_1^2+\cdots+n_m^2)) $$ óìõþáñè. Óõííéòõñ ðï~$i$ é ðòéâá÷ìññ~$N$, ðïôïíõ þôï ÷ ëáöäïê ðåòåóôáîï÷ëå ïäéî ïôòåúïë ëïîþáåôóñ üìåíåîôïí~$a_n$, ðïìõþéí ïâýåå þéóìï ïôòåúëï÷ ÷ï ÷óåè~$N$ ðåòåóôáîï÷ëáè: $$ N\left({n\over2}-{1\over 2n}(n_1^2+\cdots+n_m^2)+1\right). \eqno(34) $$ Ðïäåìé÷ îá~$N$, ðïìõþéí éóëïíïå óòåäîåå þéóìï ïôòåúëï÷. %%62 Ôáë ëáë ïôòåúëé ÷áöîù ðòé éúõþåîéé "ðïòñäëï÷ùè óôáôéóôéë", éíååôóñ ÷åóøíá ïâûéòîáñ ìéôåòáôõòá, ðïó÷ñýåîîáñ éí, ÷ ôïí þéóìå é îåëïôïòùí äòõçéí ôéðáí ïôòåúëï÷, îå òáóóíïôòåîîùí úäåóø. Äïðïìîéôåìøîõà éîæïòíáãéà íïöîï îáêôé ÷ ëîéçå Æ.~Î.~Äü÷éä é~Ä.~Ü.~Âáòôïîá Combinatorial Chance (London: Griffin, 1962), çì.~10, é ÷ ïâúïòîïê óôáôøå Ä.~Ü.~Âáòôïîá é~Ë.~Ì.~Íüììïõúá [{\sl Annals of Math. Statistics,\/} {\bf 36} (1965), 236--260]. Äáìøîåêûéå ó÷ñúé íåöäõ þéóìáíé Üêìåòá é ðåòåóôáîï÷ëáíé òáóóíáôòé÷áàôóñ ÷ òáâïôå Ä.~Æïáôù é~Í.~Ð.~Ûàãåîâåòöå Th\'eorie G\'eom\'etrique des Polyn\^omes Eul\'eriens (Lecture Notes in Math., 138 (Berlin: Springer, 1970), 94~óôò.). \excercises \ex[Í26] ×ù÷åäéôå æïòíõìõ Üêìåòá~(13). \rex[Í22] (á)~Ðïðùôáêôåóø äáìøûå òáú÷éôø éäåà, éóðïìøúï÷áîîõà ÷ ôåëóôå ðòé äïëáúáôåìøóô÷å ôïöäåóô÷á~(8): òáóóíïôòéôå ðïóìåäï÷áôåìøîïóôé~$a_1\,a_2\, \ldots\,a_n$, óïäåòöáýéå òï÷îï~$q$ òáúìéþîùè üìåíåîôï÷, é äïëáöéôå, þôï $$ \sum_k \eul{n}{k} \perm{k-1}{n-q}=\Stir{n}{q}q!. $$ (b)~Éóðïìøúõñ üôï ôïöäåóô÷ï, äïëáöéôå, þôï $$ \sum_k \eul{n}{k}\perm{k}{m}=\Stir{n+1}{n+1-m}(n-m)! \rem{ðòé~$n\ge m$.} $$ \ex[×Í25] ×ùþéóìéôå óõííõ~$\sum_k \eul{n}{k}(-1)^k$. \ex[Í21] Þåíõ òá÷îá óõííá $$ \sum_k (-1)^k\Stir{n}{k}k!\perm{n-k}{m}? $$ \ex[Í20] Îáêäéôå úîáþåîéå~$\eul{p}{k}\bmod p$, åóìé~$p$---ðòïóôïå þéóìï. \rex[Í21] Íéóôåò Ôõðéãá úáíåôéì, þôï éú æïòíõì~(4) é~(13) íïöîï ðïìõþéôø $$ n!=\sum_{k\ge0} \eul{n}{k}=\sum_{k\ge0}\sum_{j\ge0} (-1)^{k-j}\perm{n+1}{k-j}j^n. $$ Ðòïéú÷åäñ óõííéòï÷áîéå óîáþáìá ðï~$k$, úáôåí ðï~$j$, ïî ïâîáòõöéì, þôï~$\sum_{k\ge0} (-1)^{k-j}\perm{n+1}{k-j}=0$ ðòé ÷óåè~$j\ge0$, ïôóàäá~$n!=0$ ðòé ìàâïí~$n\ge0$. Îå äïðõóôéì ìé ïî ëáëïê-îéâõäø ïûéâëé? \ex[×Í40] Ñ÷ìñåôóñ ìé òáóðòåäåìåîéå ÷åòïñôîïóôåê äìñ ïôòåúëï÷, úáäá÷áåíïå æïòíõìïê~(14), áóéíðôïôéþåóëé îïòíáìøîùí? (Óò.~ó~õðò.~1.2.10-13.) \ex[Í24] (Ð.~Á.~Íáë-Íáçïî ) Ðïëáöéôå, þôï ÷åòïñôîïóôø ôïçï, þôï äìéîá ðåò÷ïçï ïôòåúëá äïóôáôïþîï äìéîîïê ðåòåóôáîï÷ëé åóôø~$l_1$, äìéîá ÷ôïòïçï %%63 åóôø~$l_2$,~\dots, á äìéîá $k\hbox{-çï ïôòåúëá}\ge l_k$, òá÷îá $$ \det\pmatrix{ 1/l_1! & 1/(l_1+l_2)! & 1/(l_1+l_2+l_3)! & \ldots & 1/(l_1+l_2+l_3+\cdots+l_k)!\cr 1 & 1/l_2! & 1/(l_2+l_3)! & \ldots & 1/(l_2+l_3+\cdots+l_k)! \cr 0 & 1 & 1/l_3! & \ldots & 1/(l_3+\cdots+l_k)!\cr \vdots & & & & \vdots\cr 0 & 0 & \ldots & 1 & 1/l_k! \cr }. $$ \ex[M30] Ðõóôø~$h_k(z)=\sum p_{km} z^m$, çäå~$p_{km}$---÷åòïñôîïóôø ôïçï, þôï ïâýáñ äìéîá ðåò÷ùè $k$~ïôòåúëï÷ (âåóëïîåþîïê) óìõþáêîïê ðïóìåäï÷áôåìøîïóôé òá÷îá~$m$. Îáêäéôå "ðòïóôùå" ÷ùòáöåîéñ äìñ~$h_1(z)$, $h_2(z)$ é äìñ ðòïéú÷ïäñýéè æõîëãéê~$h(z, x)=\sum_k h_k(z) x^k$ ïô ä÷õè ðåòåíåîîùè. \ex[BM30] Ïðòåäåìéôå áóéíðôïôéþåóëïå ðï÷åäåîéå óòåäîåçï úîáþåîéñ é äéóðåòóéé òáóðòåäåìåîéñ~$h_k(z)$ éú ðòåäùäõýåçï õðòáöîåîéñ ðòé âïìøûéè~$k$. \ex[Í40] Ðõóôø~$H_k(z)=\sum p_{km} z^m$, çäå~$p_{km}$---÷åòïñôîïóôø ôïçï, þôï äìéîá $k\hbox{-çï}$~ïôòåúëá ÷ óìõþáêîïê (âåóëïîåþîïê) ðïóìåäï÷áôåìøîïóôé òá÷îá~$m$. ×ùòáúéôå~$H_1(z)$, $H_2(z)$ é ðòïéú÷ïäñýõà æõîëãéà~$H(z, x)=\sum_k H_k(z) x^k$ ïô ä÷õè ðåòåíåîîùè þåòåú éú÷åóôîùå æõîëãéé. \ex[M33] (Ð.Á.~Íáë-Íáçïî.) Ïâïâýéôå æïòíõìõ~(13) îá óìõþáê ðåòåóôáîï÷ïë íõìøôéíîïöåóô÷á, äïëáúá÷, þôï þéóìï ðåòåóôáîï÷ïë íõìøôéíîïöåóô÷á~$\set{n_1\cdot 1, n_2\cdot 2,~\ldots, n_m\cdot m}$, éíåàýéè òï÷îï $k$~ïôòåúëï÷, òá÷îï $$ \sum_{0\le j \le k} (-1)^i \perm{n+1}{j} \perm{n_1-1+k-j}{n_1} \perm{n_2-1+k-j}{n_2} \cdots \perm{n_m-1+k-j}{n_m}, $$ çäå~$n=n_1+n_2+\cdots+n_m$. \ex[05] Ëáëéí âõäåô óòåäîåå þéóìï óôïðïë ÷ ðáóøñîóå Îøàëïíâá, åóìé ðïìøúï÷áôøóñ ïâùþîïê ëïìïäïê äìñ âòéäöá (éú 52~ëáòô), éçîïòéòõñ óôáòûéîóô÷ï ëáòô, îï óþéôáñ, þôï $$ \clubsuit < \diamondsuit < \heartsuit < \spadesuit? $$ \ex[M17] Ðåòåóôáîï÷ëá~$3\,1\,1\,1\,2\,3\,1\,4\,2\,3\,3\,4\,2\,2\,4\,4$ óïäåòöéô $5$~ïôòåúëï÷; îáêäéôå ó ðïíïýøà ðòé÷åäåîîïçï ÷ ôåëóôå ðïóôòïåîéñ äìñ õóìï÷éñ óéííåôòéé Íáë-Íáçïîá óïïô÷åôóô÷õàýõà ðåòåóôáîï÷ëõ ó $9\hbox{-à}$~ïôòåúëáíé. \rex[Í21] \exhead(Ðåòåíåöáàýéåóñ ïôòåúëé.) × ëìáóóéþåóëïê ìéôåòáôõòå $19\hbox{-çï}$~÷åëá ðï ëïíâéîáôïòîïíõ áîáìéúõ îå éúõþáìóñ ÷ïðòïó ïâ ïôòåúëáè ÷ ðåòåóôáîï÷ëáè, ëïôïòùå òáóóíáôòé÷áåí íù, îï âùìï îåóëïìøëï óôáôåê, ðïó÷ñýåîîùè ðïðåòåíåîîï ÷ïúòáóôáàýéí é õâù÷áàýéí "ïôòåúëáí". Ôáë, óþéôáìïóø, þôï ðåòåóôáîï÷ëá~$5\,3\,2\,4\,7\,6\,1\,8$ óïäåòöéô $4$~ïôòåúëá $$ 5\,3\, 2, \quad 2\,4\,7,\quad 7\,6\,1,\quad 1\,8. $$ (Ðåò÷ùê ïôòåúïë âõäåô ÷ïúòáóôáàýéí éìé õâù÷áàýéí ÷ úá÷éóéíïóôé ïô ôïçï, $a_1a_2$; ôáëéí ïâòáúïí, ðåòåóôáîï÷ëé~$a_1\,a_2\ldots\, a_n$, $a_n\,\ldots\,a_2\,a_1$ é~$(n+1-a_1)\,(n+1-a_2)\ldots (n+1-a_n)$ ÷óå óïäåòöáô ïäéîáëï÷ïå þéóìï ðåòåíåöáàýéèóñ ïôòåúëï÷.) Íáëóéíáìøîïå þéóìï ïôòåúëï÷ üôïçï ôéðá ÷ ðåòåóôáîï÷ëå $n$~üìåíåîôï÷ òá÷îï~$n-1$. Îáêäéôå óòåäîåå þéóìï ðåòåíåöáàýéèóñ ïôòåúëï÷ ÷ óìõþáêîïê ðåòåóôáîï÷ëå íîïöåóô÷á~$\set{1, 2,~\ldots, n}$. [\emph{Õëáúáîéå:} òáúâåòéôå ÷ù÷ïä æïòíõìù~(34).] \ex[M30] Ðòïäïìöéí ðòåäùäõýåå õðòáöîåîéå. Ðõóôø~$\Eul{n}{k}$---þéóìï ðåòåóôáîï÷ïë %%64 íîïöåóô÷á~$\set{1, 2,~\ldots, n}$, ëïôïòùå éíåàô òï÷îï $k$~ðåòåíåöáàýéèóñ ïôòåúëï÷. Îáêäéôå òåëõòòåîôîïå óïïôîïûåîéå, ó ðïíïýøà ëïôïòïçï íïöîï ÷ùþéóìéôø ôáâìéãõ úîáþåîéê~$\Eul{n}{k}$; îáêäéôå ôáëöå óïïô÷åôóô÷õàýåå òåëõòòåîôîïå óïïôîïûåîéå äìñ ðòïéú÷ïäñýåê æõîëãéé~$G_n(z)=\sum_k \Eul{n}{k} z^k \big / n!$. Éóðïìøúõñ üôï ðïóìåäîåå òåëõòòåîôîïå óïïôîïûåîéå, îáêäéôå ðòïóôõà æïòíõìõ äìñ \emph{äéóðåòóéé} þéóìá ðåòåíåöáàýéèóñ ïôòåúëï÷ ÷ óìõþáêîïê ðåòåóôáîï÷ëå íîïöåóô÷á~$\set{1,2, ~\ldots, n}$. \ex[M25] Óõýåóô÷õåô ÷óåçï~$2^n$ ðïóìåäï÷áôåìøîïóôåê $a_1\,a_2\,a_n$, çäå ëáöäùê üìåíåîô~$a_j$---ìéâï~$0$, ìéâï~$1$. Óëïìøëï óòåäé îéè ðïóìåäï÷áôåìøîïóôåê, óïäåòöáýéè òï÷îï $k$~ïôòåúëï÷ (ô.~å.~óïäåòöáýéè òï÷îï~$k-1$ üìåíåîôï÷~$a_j$, ôáëéè, þôï~$a_j>a_{j+1}$)? \ex[M27] Óõýåóô÷õåô ÷óåçï~$n!$ ðïóìåäï÷áôåìøîïóôåê~$a_1\,a_2\,\ldots\,a_n$, çäå ëáöäùê üìåíåîô~$a_j$---ãåìïå þéóìï, ìåöáýåå ÷ äéáðáúïîå~$0 \le a_j \le n-j$; óëïìøëï óòåäé îéè ðïóìåäï÷áôåìøîïóôåê, óïäåòöáýéè òï÷îï $k$~ïôòåúëï÷ (ô.~å.~óïäåòöáýéè òï÷îï~$k-1$ üìåíåîôï÷~$a_j$, ôáëéè, þôï~$a_j>a_{j+1}$)? \rex[M26] (Äö.~Òéïòäáî.) (á)~Óëïìøëéíé óðïóïâáíé íïöîï òáóðïìïöéôø $n$~îåáôáëõàýéè ìáäåê (ô.~å.~îéëáëéå ä÷å îå äïìöîù îáèïäéôøóñ îá ïäîïê ÷åòôéëáìé \picture{ Òéó.~4. Îåáôáëõàýéå ìáäøé îá ûáèíáôîïê äïóëå ðòé úáäáîîïí þéóìå ìáäåê îéöå çìá÷îïê äéáçïîáìé. } éìé çïòéúïîôáìé) îá ûáèíáôîïê äïóëå òáúíåòá~$n\times n$ ôáë, þôïâù òï÷îï~$k$ éú îéè îáèïäéìéóø îá úáäáîîïê óôïòïîå ïô çìá÷îïê äéáçïîáìé? (b)~Óëïìøëéíé óðïóïâáíé íïöîï òáóðïìïöéôø $k$~îåáôáëõàýéè ìáäåê îá úáäáîîïê óôïòïîå ïô çìá÷îïê äéáçïîáìé ûáèíáôîïê äïóëé òáúíåòá~$n\times n$? Îáðòéíåò, îá òéó.~4 ðïëáúáî ïäéî éú $15619$~óðïóïâï÷ òáóðïìïöéôø ÷ïóåíø îåáôáëõàýéè ìáäåê îá ïâùþîïê ûáèíáôîïê äïóëå ó ôòåíñ ìáäøñíé îá îåúáûôòéèï÷áîîïí õþáóôëå îéöå çìá÷îïê äéáçïîáìé, á ôáëöå ïäéî éú $1050$~óðïóïâï÷ òáóðïìïöéôø ôòé îåáôáëõàýéå ìáäøé îá ôòåõçïìøîïê äïóëå. \rex[Í21] Çï÷ïòñô, þôï ðåòåóôáîï÷ëá ôòåâõåô $k$~\emph{þôåîéê,} åóìé åå îõöîï ðòïóíïôòåôø $k$~òáú, óìå÷á îáðòá÷ï, þôïâù ðòïþéôáôø ÷óå üìåíåîôù ÷ îåõâù÷áàýåí ðïòñäëå. Îáðòéíåò, ðåòåóôáîï÷ëá $$ 4\,9\,1\,8\,2\,5\,3\,6\,7 $$ %%65 ôòåâõåô þåôùòåè þôåîéê: ðòé ðåò÷ïí þôåîéé ðïìõþáåí~$1,2,3$; ðòé ÷ôïòïí---$4, 5, 6, 7$; úáôåí~$8$; úáôåí~$9$. Îáêäéôå ó÷ñúø íåöäõ ïôòåúëáíé é þôåîéñíé. \ex[M22] Åóìé ðåòåóôáîï÷ëá~$a_1\,a_2\,\ldots\,a_n$ íîïöåóô÷á~$\set{1, 2, ~\ldots, n}$ óïäåòöéô $k$~ïôòåúëï÷ é ôòåâõåô $j$~þôåîéê ÷ óíùóìå õðò.~20, ôï þôï íïöîï óëáúáôø ï ðåòåóôáîï÷ëå~$a_n\,\ldots\,a_2\,a_1$? \ex[M26] (Ì.~Ëáòìéã, Ä.~Ð.~Òïúåìø é~Ò.~Á.~Óëïõ÷éìì.) Ðïëáöéôå, þôï îå óõýåóô÷õåô ðåòåóôáîï÷ëé íîïöåóô÷á~$\set{1, 2,~\ldots, n}$ ó $n+1-r$~ïôòåúëáíé, ôòåâõàýåê $s$~þôåîéê, åóìé~$rs1$, ôï õíåîøûéôø~$t$ îá~$1$ é ÷åòîõôøóñ ë ûáçõ~\stp{2}. \st[Ïðòåäåìéôø~$x$.] Õóôáîï÷éôø~$x\asg x_1$ é úáëïîþéôø òáâïôõ áìçïòéôíá. (Ôåðåòø~$0 < x < \infty$.) \algend Ðïñóîåîéñ ë áìçïòéôíáí~I é~D, úáëìàþåîîùå ÷ ëòõçìùå óëïâëé, îå ôïìøëï ðïìåúîù äìñ äïëáúáôåìøóô÷á ôïçï æáëôá, þôï üôé áìçïòéôíù óïèòáîñàô óôòõëôõòõ ôáâìï, îï ïîé ðïú÷ïìñàô õâåäéôøóñ, þôï \emph{áìçïòéôíù~I é~D ÷úáéíîï ïâòáôîù.} Åóìé óîáþáìá ÷ùðïìîéôø áìçïòéôí~I ó äáîîùí ôáâìï~$P$ é îåëïôïòùí ãåìùí ðïìïöéôåìøîùí þéóìïí~$x\notin P$, ôï ïî ÷óôá÷éô~$x$ ÷~$P$ é ïðòåäåìéô ãåìùå ðïìïöéôåìøîùå þéóìá~$s$, $t$, õäï÷ìåô÷ïòñàýéå õóìï÷éñí~(8). Áìçïòéôí~D, ðòéíåîåîîùê ë ðïìõþåîîïíõ òåúõìøôáôõ, ÷ïóóôáîï÷éô úîáþåîéñ~$x$ é ðåò÷ïîáþáìøîùê ÷éä~$P$. Ïâòáôîï, åóìé óîáþáìá ÷ùðïìîéôø áìçïòéôí~D ó äáîîùí ôáâìï~$P$ é îåëïôïòùíé ãåìùíé ðïìïöéôåìøîùíé þéóìáíé~$s$, $t$, õäï÷ìåô÷ïòñàýéíé õóìï÷éñí~(8), ôï ïî íïäéæéãéòõåô~$P$, õäáìé÷ îåëïôïòïå ãåìïå ðïìïöéôåìøîïå þéóìï~$x$. Áìçïòéôí~I, ðòéíåîåîîùê ë ðïìõþåîîïíõ òåúõìøôáôõ, ÷ïóóôáîï÷éô úîáþåîéñ~$s$, $t$ é ðåò÷ïîáþáìøîùê ÷éä~$P$. %% 70 Ðòéþéîá úáëìàþáåôóñ ÷ ôïí, þôï óïäåòöáîéå ðïñóîåîéê ë ûáçáí~I3 é~D4 óï÷ðáäáåô ôáë öå, ëáë é ë ûáçáí~I4 é~D3; ïîé ïäîïúîáþîï ïðòåäåìñàô úîáþåîéå~$j$. Óìåäï÷áôåìøîï, ÷óðïíïçáôåìøîùå ðïóìåäï÷áôåìøîïóôé~(9), (10) ïäéîáëï÷ù, ÷ ïâïéè óìõþáñè. Ôåðåòø íù ðïäçïôï÷ìåîù ë äïëáúáôåìøóô÷õ ïóîï÷îïçï ó÷ïêóô÷á ôáâìï. \proclaim Ôåïòåíá~A. Óõýåóô÷õåô ÷úáéíîï ïäîïúîáþîïå óïïô÷åôóô÷éå íåöäõ íîïöåóô÷ïí ÷óåè ðåòåóôáîï÷ïë íîïöåóô÷á~$\set{1, 2,~\ldots, n}$ é íîïöåóô÷ïí ÷óåè õðïòñäïþåîîùè ðáò ôáâìï~$(P, Q)$, çäå~$P$ é~$Q$---ôáâìï ïäéîáëï÷ïê æïòíù éú üìåíåîôï÷~$\set{1, 2,~\ldots, n}$. (Ðòéíåò ë üôïê ôåïòåíå óïäåòöéôóñ ÷ ðòé÷åäåîîïí îéöå äïëáúáôåìøóô÷å.) \proof Õäïâîåå äïëáúáôø îåóëïìøëï âïìåå ïâýéê òåúõìøôáô. Ðï ðòïéú÷ïìøîïíõ ä÷õóôòïþîïíõ íáóóé÷õ $$ \pmatrix{ q_1 & q_2 & \ldots & q_n \cr p_1 & p_2 & \ldots & p_n \cr },\qquad \matrix{q_1 < q_2 < \ldots < q_n,\hfill\cr p_1, p_2, \ldots, p_n \hbox{ ÷óå òáúîùå},\hfill\cr } \eqno (11) $$ ðïóôòïéí óïïô÷åôóô÷õàýéå ä÷á ôáâìï~$P$ é~$Q$, çäå $P$~óïóôïéô éú üìåíåîôï÷~$\set{p_1, p_2,~\ldots, p_n}$, á~$Q$---éú üìåíåîôï÷~$\set{q_1, q_2,~\ldots, q_n}$, ðòéþåí~$P$ é~$Q$ éíåàô ïäéîáëï÷õà æïòíõ. Ðõóôø~$P$ é~$Q$ ÷îáþáìå ðõóôù. Ðòé~$i=1$, $2$,~\dots, $n$ (éíåîîï ÷ ôáëïí ðïòñäëå) ðòïäåìáåí óìåäõàýõà ïðåòáãéà: ÷óôá÷éí~$P_i$ ÷ ôáâìï~$P$ ðòé ðïíïýé áìçïòéôíá~I; úáôåí õóôáîï÷éí~$Q_{st}\asg q_l$, çäå~$s$ é~$t$ ïðòåäåìñàô ÷îï÷ø úáðïìîåîîõà ðïúéãéà ÷~$P$. Îáðòéíåò, åóìé úáäáîá ðåòåóôáîï÷ëá~$ \pmatrix{ 1 & 3 & 5 & 6 & 8 \cr 7 & 2 & 9 & 5 & 3 \cr }$, äåêóô÷õåí óìåäõàýéí ïâòáúïí: {\tdim=\hsize \advance\tdim by -\parindent \divide\tdim by 3 \def\+#1\cr{\line{\indent\vbox{\halign{\hbox to \tdim{##\hfil}&\hbox to \tdim{##\hfil}&\hbox to \tdim{##\hfil}\cr#1\cr}}\hfill}\smallskip} \vskip\abovedisplayskip \+ & $P$ \hfil & $Q$ \hfil \cr \+ ×óôá÷ëá~7: & \tableau{ 7 \cr } & \tableau{ 1 \cr }\cr \+ ×óôá÷ëá~2: & \tableau{ 2 \cr 7 \cr } & \tableau { 1 \cr 3 \cr } \cr \+ ×óôá÷ëá~9: & \tableau{ 2 & 9 \cr 7 \cr } & \tableau{ 1 & 5 \cr 3 \cr } \cr %% 71 \+ ×óôá÷ëá~5: & \tableau{ 2 & 5 \cr 7 & 9 \cr } & \tableau{ 1 & 5 \cr 3 & 6 \cr } \cr \rightline{(12)} \+ ×óôá÷ëá~3: & \tableau{ 2& 3 \cr 5 & 9 \cr 7\cr } & \tableau{ 1 & 5 \cr 3 & 6 \cr 8 \cr } \cr \vskip\belowdisplayskip } Óìåäï÷áôåìøîï, ðáòá ôáâìï~$(P, Q)$, óïïô÷åôóô÷õàýáñ ðåòåóôáîï÷ëå $\pmatrix{ 1 & 3 & 5 & 6 & 8 \cr 7 & 2 & 9 & 5 & 3 \cr }$, ôáëï÷á: $$ P=\tableau{ 2 & 3 \cr 5 & 9 \cr 7 \cr }\,, \qquad Q=\tableau{ 1 & 5 \cr 3 & 6 \cr 8 \cr }\,. \eqno(13) $$ Éú ðïóôòïåîéñ ñóîï, þôï~$P$ é~$Q$ ÷óåçäá éíåàô ïäéîáëï÷õà æïòíõ. Ëòïíå ôïçï, ðïóëïìøëõ üìåíåîôù ÷óåçäá äïâá÷ìñàôóñ îá çòáîéãõ~$Q$ é ÷ ÷ïúòáóôáàýåí ðïòñäëå, ôï~$Q$---ôáâìï. Ïâòáôîï, åóìé úáäáîù ä÷á ôáâìï ïäéîáëï÷ïê æïòíù, ôï óïïô÷åôóô÷õàýéê ä÷õóôòïþîùê íáóóé÷~(11) íïöîï ðïóôòïéôø ôáë. Ðõóôø $$ q_1 < q_2 < \ldots < q_n $$% ---üìåíåîôù~$Q$. Ðõóôø ðòé~$i=n$,~\dots, $2$, $1$ (éíåîîï ÷ ôáëïí ðïòñäëå) $p_i$---üìåíåîô~$x$, ëïôïòùê õäáìñåôóñ éú~$P$ ðï áìçïòéôíõ~D ó éóðïìøúï÷áîéåí úîáþåîéê~$s$, $t$, ôáëéè, þôï~$Q_{st}=q_i$. Îáðòéíåò, åóìé ðòéíåîéôø üôï ðïóôòïåîéå ë ôáâìï~(13) é ðòïéú÷ïäéôø ÷ùþéóìåîéñ, ïâòáôîùå~(12), äï ôåè ðïò, ðïëá~$P$ îå éóþåòðáåôóñ, ôï ðïìõþéôóñ íáóóé÷ $\pmatrix{ 1 & 3 & 5 & 6 & 8 \cr 7 & 2 & 9 & 5 & 3 \cr }$. Ðïóëïìøëõ áìçïòéôíù~I é~D ÷úáéíîï ïâòáôîù, ôï ÷úáéíîï ïâòáôîù é ïðéóáîîùå úäåóø ä÷á ðïóôòïåîéñ; ôáëéí ïâòáúïí, ôòåâõåíïå ÷úáéíîï ïäîïúîáþîïå óïïô÷åôóô÷éå õóôáîï÷ìåîï. \proofend Óïïô÷åôóô÷éå, ïðòåäåìåîîïå ÷ äïëáúáôåìøóô÷å ôåïòåíù~A, ïâìáäáåô íîïöåóô÷ïí ðïòáúéôåìøîùè ó÷ïêóô÷, é ôåðåòø íù ðòéóôõðéí ë ÷ù÷ïäõ îåëïôïòùè éú îéè. Õâåäéôåìøîáñ ðòïóøâá ë þéôáôåìà, ðòåöäå þåí ä÷éçáôøóñ äáìøûå, éóðùôáôø óåâñ îá ðòéíåòáè éú õðò.~1, þôïâù ïó÷ïéôøóñ ó üôéíé ðïóôòïåîéñíé. %%72 Ëáë ôïìøëï üìåíåîô ÷ùôåóîåî éú óôòïëé~1 ÷ óôòïëõ~2, ïî õöå âïìøûå îå ÷ìéñåô îá óôòïëõ~1; ëòïíå ôïçï, óôòïëé~2, 3,~\dots{} óôòïñôóñ éú ðïóìåäï÷áôåìøîïóôé "÷ùôåóîåîîùè" üìåíåîôï÷ ôïþîï ôáë öå, ëáë óôòïëé~1, 2,~\dots{} óôòïñôóñ éú éóèïäîïê ðåòåóôáîï÷ëé. Üôé æáëôù îá÷ïäñô îá íùóìø ï ôïí, þôï îá ðïóôòïåîéå ÷ ôåïòåíå~A íïöîï ÷úçìñîõôø éîáþå, ïâòáýáñ ÷îéíáîéå ìéûø îá ðåò÷ùå óôòïëé~$P$ é~$Q$. Îáðòéíåò, ðåòåóôáîï÷ëá $\pmatrix{ 1 & 3 & 5 & 6 & 8\cr 7 & 2 & 9 & 5 & 3 \cr }$ ÷ùúù÷áåô óìåäõàýéå äåêóô÷éñ îáä óôòïëïê~1 [óò.~ó~(12)]: $$ \vcenter{\halign{ #\hfil\bskip&\bskip #\hfil\bskip&\bskip$#$\hfil\cr 1: ×óôá÷éôø~$7$, & õóôáîï÷éôø & Q_{11}\asg 1. \cr 3: ×óôá÷éôø~$2$, & ÷ùôåóîéôø~$7$. \cr 5: ×óôá÷éôø~$9$, & õóôáîï÷éôø & Q_{12}\asg 5. \cr 6: ×óôá÷éôø~$5$, & ÷ùôåóîéôø~$9$. \cr 8: ×óôá÷éôø~$3$, & ÷ùôåóîéôø~$5$.\cr }} \eqno(14) $$ Ôáëéí ïâòáúïí, ðåò÷áñ óôòïëá~$P$---üôï~$2~3$, á ðåò÷áñ óôòïëá~$Q$---üôï~$1~5$. Ëòïíå ôïçï, ïóôáìøîùå óôòïëé~$P$ é~$Q$ óïóôá÷ìñàô ôáâìï, óïïô÷åôóô÷õàýéå "÷ùôåóîåîîïíõ" ä÷õóôòïþîïíõ íáóóé÷õ $$ \pmatrix{ 3 & 6 & 8 \cr 7 & 9 & 5 \cr }, \eqno (15) $$ Þôïâù ðïîñôø, ëáë óôòïéôóñ óôòïëá~1, íïöîï éúõþéôø üìåíåîôù, ðïðáäáàýéå ÷ äáîîùê óôïìâåã üôïê óôòïëé. Âõäåí çï÷ïòéôø, þôï ðáòá~$(q_i, p_i)$ ðòéîáäìåöéô ëìáóóõ~$t$ ïôîïóéôåìøîï ä÷õóôòïþîïçï íáóóé÷á $$ \pmatrix{ q_1 & q_2 & \ldots & q_n \cr p_1 & p_2 & \ldots & p_n \cr }, \qquad\matrix{ q_1p_{i_2}>\ldots>p_{i_k},\cr } \eqno(18) $$ ðïóëïìøëõ ðòé òáâïôå áìçïòéôíá ÷óôá÷ëé ðïúéãéñ ôáâìï~$P_{1t}$ ðòéîéíáåô õâù÷áàýõà ðïóìåäï÷áôåìøîïóôø úîáþåîéê~$p_{i_1}$,~\dots, $p_{i_k}$. × ëïîãå ðïóôòïåîéñ $$ p_{1t}=p_{i_k}, \quad Q_{1t}=q_{i_1}, \eqno(19) $$ á ÷ùôåóîåîîùê ä÷õóôòïþîùê íáóóé÷, ëïôïòùí ïðòåäåìñàôóñ óôòïëé~2, 3,~\dots{} ôáâìï~$P$ é~$Q$, óïäåòöéô óôïìâãù $$ \pmatrix{ q_{i_2} & q_{i_3} & \ldots & q_{i_k} \cr p_{i_1} & p_{i_2} & \ldots & p_{i_k-1}\cr }, \eqno(20) $$ á ôáëöå äòõçéå óôïìâãù, áîáìïçéþîùí ïâòáúïí ðïìõþåîîùå éú äòõçéè ëìáóóï÷. Üôé îáâìàäåîéñ ðòé÷ïäñô ë ðòïóôïíõ íåôïäõ ÷ùþéóìåîéñ~$P$ é~$Q$ ÷òõþîõà (óí.~õðò.~3), á ôáëöå ðòåäïóôá÷ìñàô óòåäóô÷á äìñ äïëáúáôåìøóô÷á ïäîïçï ÷åóøíá îåïöéäáîîïçï òåúõìøôáôá. \proclaim Ôåïòåíá~B. Åóìé ÷ ðïóôòïåîéé éú ôåïòåíù~A ðåòåóôáîï÷ëá $$ \pmatrix{ 1 & 2 & \ldots & n \cr a_1 & a_2 & \ldots & a_n \cr } $$ óïïô÷åôóô÷õåô ôáâìï~$(P, Q)$, ôï ïâòáôîáñ åê ðåòåóôáîï÷ëá óïïô÷åôóô÷õåô ôáâìï~$(Q, P)$. Üôï äï÷ïìøîï õäé÷éôåìøîùê æáëô, ðïôïíõ þôï ÷ ôåïòåíå~A ôáâìï~$P$ é~$Q$ æïòíéòõàôóñ óï÷åòûåîîï òáúîùíé óðïóïâáíé, é ïâòáôîáñ ðåòåóôáîï÷ëá ðïìõþáåôóñ ÷ òåúõìøôáôå ÷åóøíá ðòéþõäìé÷ïê ðåòåôáóï÷ëé óôïìâãï÷ ä÷õóôòïþîïçï íáóóé÷á. %% 74 \proof Ðòåäðïìïöéí, õ îáó åóôø ä÷õóôòïþîùê íáóóé÷~(16); ðïíåîñ÷ íåóôáíé åçï óôòïëé é ïôóïòôéòï÷á÷ óôïìâãù ôáë, þôïâù üìåíåîôù îï÷ïê ÷åòèîåê óôòïëé òáóðïìïöéìéóø ÷ îåõâù÷áàýåí ðïòñäëå, ðïìõþéí "ïâòáôîùê" íáóóé÷ $$ \eqalign{ \pmatrix{ q_1 & q_2 & \ldots & q_n \cr p_1 & p_2 & \ldots & p_n \cr }^{-1}&= \pmatrix{ p_1 & p_2 & \ldots & p_n \cr q_1 & q_2 & \ldots & q_n \cr }=\cr &=\pmatrix{ p'_1 & p'_2 & \ldots & p'_n \cr q'_1 & q'_2 & \ldots & q'_n \cr },\qquad \matrix{ p'_1 < p'_2 < \ldots < p'_n; \hfill\cr q'_1, q'_2, \ldots, q'_n \hbox{ ÷óå òáúîùå.}\hfill\cr }\cr } \eqno(21) $$ Ðïëáöåí, þôï üôá ïðåòáãéñ óïïô÷åôóô÷õåô úáíåîå~$(P, Q)$ îá~$(Q, P)$ ÷ ðïóôòïåîéé éú ôåïòåíù~A. × õðò.~2 îáûé úáíåþáîéñ ïâ ïðòåäåìåîéé ëìáóóï÷ ðåòåæïòíõìéòï÷áîù ôáëéí ïâòáúïí, þôï ëìáóó, ë ëïôïòïíõ ïôîïóéôóñ ðáòá~$(q_i, p_i)$, îå úá÷éóéô ïô ôïçï æáëôá, þôï üìåíåîôù~$q_1$, $q_2$,~\dots, $q_n$ òáóðïìïöåîù ÷ ÷ïúòáóôáàýåí ðïòñäëå. Ðïóëïìøëõ òåúõìøôéòõàýéå õóìï÷éñ óéííåôòéþîù ïôîïóéôåìøîï~$p$ é~$q$, ôï ïðåòáãéñ~(21) îå îáòõûáåô óôòõëôõòõ ëìáóóï÷; åóìé~$(q, p)$ ðòéîáäìåöéô ëìáóóõ~$t$ ïôîïóéôåìøîï~(16), ôï~$(p, q)$ ðòéîáäìåöéô ëìáóóõ~$t$ ïôîïóéôåìøîï~(21). Ðïüôïíõ, åóìé òáúíåóôéôø üìåíåîôù üôïçï ðïóìåäîåçï ëìáóóá~$t$ ôáë, þôïâù $$ \eqalign{ p_{i_k}<\ldots< p_{i_2} < p_{i_1}, \cr q_{i_k}>\ldots> q_{i_2} > q_{i_1}, \cr } \eqno(22) $$ [óò.~ó~(18)], ôï ðïìõþéí $$ P_{1t}=q_{i_1}, Q_{1t}=p_{i_k}, \eqno (23) $$ ëáë ÷~(19), á óôïìâãù $$ \pmatrix{ p_{i_{k-1}} & \ldots & p_{i_2} & p_{i_1} \cr q_{i_k} & \ldots & q_{i_3} & q_{i_2} \cr } \eqno(24) $$ ÷ïêäõô ÷ ÷ùôåóîåîîùê íáóóé÷, ëáë ÷~(20). Óìåäï÷áôåìøîï, ðåò÷ùå óôòïëé~$P$ é~$Q$ íåîñàôóñ íåóôáíé. Ëòïíå ôïçï, ÷ùôåóîåîîùê ä÷õóôòïþîùê íáóóé÷ äìñ~(21) ñ÷ìñåôóñ ïâòáôîùí ðï ïôîïûåîéà ë ÷ùôåóîåîîïíõ ä÷õóôòïþîïíõ íáóóé÷õ äìñ~(16), ôáë þôï äïëáúáôåìøóô÷ï úá÷åòûáåôóñ ðòéíåîåîéåí éîäõëãéé ðï þéóìõ óôòïë ÷ ôáâìï. \proofend \proclaim Óìåäóô÷éå. Ëïìéþåóô÷ï ôáâìï, ëïôïòùå íïöîï óæïòíéòï÷áôø éú üìåíåîôï÷~$\set{1, 2,~\ldots, n}$, òá÷îï ëïìéþåóô÷õ éî÷ïìàãéê íîïöåóô÷á~$\set{1, 2,~\ldots, n}$. \proof Åóìé~$\pi$---éî÷ïìàãéñ, óïïô÷åôóô÷õàýáñ ðáòå ôáâìï~$(P, Q)$, ôï~$\pi=\pi^{-1}$ óïïô÷åôóô÷õåô ðáòå~$(Q, P)$. Óìåäï÷áôåìøîï, %% 75 $P=Q$. Ïâòáôîï, åóìé~$\pi$---ëáëáñ-ìéâï ðåòåóôáîï÷ëá, óïïô÷åôóô÷õàýáñ ðáòå~$(P, P)$, ôï~$\pi^{-1}$ ôïöå óïïô÷åôóô÷õåô ðáòå~$(P,P)$; ïôóàäá~$\pi=\pi^{-1}$. Ôáëéí ïâòáúïí, óõýåóô÷õåô ÷úáéíîï ïäîïúîáþîïå óïïô÷åôóô÷éå íåöäõ éî÷ïìàãéñíé~$\pi$ é ôáâìï~$P$. \proofend Ñóîï, þôï üìåíåîô ÷ ìå÷ïí ÷åòèîåí õçìõ ôáâìï ÷óåçäá îáéíåîøûéê. Üôï îá÷ïäéô îá íùóìø ï ÷ïúíïöîïí óðïóïâå óïòôéòï÷ëé íîïöåóô÷á þéóåì. Óîáþáìá íïöîï óïóôá÷éôø éú îéè ôáâìï, íîïçïëòáôîï ðòéíåîññ áìçïòéôí~I, ÷ òåúõìøôáôå îáéíåîøûéê üìåíåîô ïëáöåôóñ ÷ õçìõ. Úáôåí üôïô îáéíåîøûéê üìåíåîô õäáìñåôóñ, á ïóôáìøîùå üìåíåîôù ðåòåòáúíåýáàôóñ ôáë, þôïâù ïâòáúï÷áìïóø äòõçïå ôáâìï; ðïôïí õäáìñåôóñ îï÷ùê íéîéíáìøîùê üìåíåîô é ô.ä. Ðïüôïíõ äá÷áêôå ðïóíïôòéí, þôï ðòïéóèïäéô, ëïçäá íù õäáìñåí õçìï÷ïê üìåíåîô éú ôáâìï $$ \tableau{ 1 & 3 & 5 & 8 & 12 & 16\cr 2 & 6 & 9 & 15\cr 4 & 10 & 14 \cr 11 & 13 \cr 17\cr } \eqno (25) $$ Ðïóìå õäáìåîéñ~$1$ îá ïó÷ïâïäé÷ûååóñ íåóôï îåïâèïäéíï ðïóôá÷éôø~$2$. Úáôåí íïöîï ðïäîñôø~$4$ îá íåóôï ä÷ïêëé, ïäîáëï~$11$ îåìøúñ ðïäîñôø îá íåóôï~$4$, îï îá üôï íåóôï íïöîï ðïä÷éîõôø~$10$, á ðïôïí~$13$ îá íåóôï~$10$. × ïâýåí óìõþáå ðòéèïäéí ë óìåäõàýåê ðòïãåäõòå. \alg S.(Õäáìåîéå õçìï÷ïçï üìåíåîôá.) Üôïô áìçïòéôí õäáìñåô üìåíåîô éú ìå÷ïçï ÷åòèîåçï õçìá ôáâìï~$P$ é ðåòåíåýáåô ïóôáìøîùå üìåíåîôù ôáë, þôïâù óïèòáîéìéóø ó÷ïêóô÷á ôáâìï. Éóðïìøúõàôóñ ôå öå ïâïúîáþåîéñ, þôï é ÷ áìçïòéôíáè~I é~D. \st[Îáþáìøîáñ õóôáîï÷ëá.] Õóôáîï÷éôø~$r\asg 1$, $s\asg 1$. \st[Ëïîåã?] Åóìé~$P_{rs}=\infty$, ôï ðòïãåóó úá÷åòûåî. \st[Óòá÷îéôø.] Åóìé~$P_{(r+1)s}\simlt P_{r(s+1)}$, ôï ðåòåêôé ë ûáçõ~\stp{5}. (Óòá÷îé÷áåí üìåíåîôù óðòá÷á é óîéúõ ïô ó÷ïâïäîïçï íåóôá é ðåòåä÷éçáåí íåîøûéê éú îéè.) \st[Ðïä÷éîõôø ÷ìå÷ï.] Õóôáîï÷éôø~$P_{rs}\asg P_{r(s+1)}$, $s\asg s+1$ é ÷åòîõôøóñ ë~\stp{3}. \st[Ðïä÷éîõôø ÷÷åòè.] Õóôáîï÷éôø~$P_{rs}\asg P_{(r+1)s}$, $r\asg r+1$ é ÷åòîõôøóñ ë~\stp{2}. \algend Ìåçëï äïëáúáôø, þôï ðïóìå õäáìåîéñ õçìï÷ïçï üìåíåîôá ó ðïíïýøà áìçïòéôíá~S, $P$---ðï-ðòåöîåíõ ôáâìï (óí.~õðò.~10). Ôáëéí %%76 ïâòáúïí, ðòéíåîññ áìçïòéôí~S äï ôåè ðïò, ðïëá~$P$ îå éóþåòðáåôóñ, íïöîï ðòïþéôáôø åçï üìåíåîôù ÷ ÷ïúòáóôáàýåí ðïòñäëå. Ë óïöáìåîéà, üôïô áìçïòéôí óïòôéòï÷ëé ïëáúù÷áåôóñ îå óôïìø üææåëôé÷îùí, ëáë äòõçéå áìçïòéôíù, ëïôïòùå îáí åýå ðòåäóôïéô òáóóíïôòåôø. Íéîéíáìøîïå ÷òåíñ åçï òáâïôù ðòïðïòãéïîáìøîï~$n^{1.5}$; áîáìïçéþîùå áìçïòéôíù, éóðïìøúõàýéå ÷íåóôï ôáâìï äåòå÷øñ, úáôòáþé÷áàô ÷òåíñ ðïòñäëá~$n\log n$. Áìçïòéôí~S, èïôñ é îå ðòé÷ïäéô ë ïóïâåîîï üææåëôé÷îïíõ áìçïòéôíõ óïòôéòï÷ëé, ïâìáäáåô îåëïôïòùíé ïþåîø éîôåòåóîùíé ó÷ïêóô÷áíé. \proclaim Ôåïòåíá~C. (Í.~Ð.~Ûàãåîâåòöå.) Åóìé~$P$---ôáâìï, ðïóôòïåîîïå, ëáë ÷ ôåïòåíå~A, éú ðåòåóôáîï÷ëé~$a_1\,a_2,\ldots\,a_n$, é~$a_i=\min\set{a_1, a_2, \ldots, a_n}$, ôï áìçïòéôí~S ðòåïâòáúõåô~$P$ ÷ ôáâìï, óïïô÷åôóô÷õàýåå ðåòåóôáîï÷ëå~$a_1\,\ldots\,a_{i-1}\,a_{i+1}\,\ldots\,a_n$. \proof Óí. õðò. 13. \proofend Äá÷áêôå ðïóìå ðòéíåîåîéñ áìçïòéôíá~S ðïíåóôéí îá ÷îï÷ø ïó÷ïâïäé÷ûååóñ íåóôï õäáìåîîùê üìåíåîô ÷ óëïâëáè, õëáúá÷ ôáëéí ïâòáúïí, þôï îá óáíïí äåìå ïî îå ñ÷ìñåôóñ þáóôøà ôáâìï. Ðòéíåîé÷, îáðòéíåò, üôõ ðòïãåäõòõ ë ôáâìï~(25), íù ðïìõþéìé âù $$ \tableau{ 2 & 3 & 5 & 8 & 12 & 16\cr 4 & 6 & 9 & 15\cr 10 & 13 & 14 \cr 11 & (1) \cr 17 \cr } $$ á åýå ä÷á ðòéíåîåîéñ ðòé÷ïäñô ë $$ \tableau{ 4 & 5 & 8 & 12 & 16 & (2)\cr 6 & 9 & 14 &15\cr 10 & 13 & (3) \cr 11 & (1) \cr 17\cr } $$ %% 77 Ðòïäïìöáñ äï ôåè ðïò, ðïëá ÷óå üìåíåîôù îå ïëáöõôóñ ÷ óëïâëáè, é õâòá÷ óëïâëé, ðïìõþéí ëïîæéçõòáãéà $$ \tableau{ 17 & 15 & 14 & 13 & 11 & 2 \cr 16 & 10 & 6 & 4 \cr 12 & 5 & 3 \cr 9 & 1 \cr 8 \cr } \eqno(26) $$ éíåàýõà ôõ öå æïòíõ, þôï é éóèïäîïå ôáâìï~(25). Üôõ ëïîæéçõòáãéà íïöîï îáú÷áôø \dfn{ä÷ïêóô÷åîîùí ôáâìï,} ðïôïíõ þôï ïîá ðïèïöá îá ôáâìï ó ôïê ìéûø òáúîéãåê, þôï ðòéíåîñåôóñ "ä÷ïêóô÷åîîïå ïôîïûåîéå ðïòñäëá" ($<$ é~$>$ ðïíåîñìéóø òïìñíé). Ïâïúîáþéí ä÷ïêóô÷åîîïå ôáâìï, ðïìõþåîîïå éú~$P$ ôáëéí óðïóïâïí, þåòåú~$P^S$. Ôáâìï~$P$ ïðòåäåìñåôóñ éú~$P^S$ åäéîóô÷åîîùí ïâòáúïí. × óáíïí äåìå, éóèïäîïå ôáâìï íïöîï ðïìõþéôø éú~$P^S$ ðòé ðïíïýé ôïçï öå óáíïçï áìçïòéôíá (ó ïâòáôîùí ïôîïûåîéåí ðïòñäëá, ðïóëïìøëõ $P^S$---ä÷ïêóô÷åîîïå ôáâìï). Îáðòéíåò, ðòéíåîåîéå ë~(26) ä÷õè ûáçï÷ üôïçï áìçïòéôíá äáåô $$ \tableau{ 15 & 14 & 13 & 11 & 2 & (16)\cr 12 & 10 & 6 & 4\cr 9 & 5 & 3 \cr 8 & 1 \cr (17)\cr } $$ é ÷ ëïîãå ëïîãï÷ ïðñôø ðïìõþáåôóñ ôáâìï~(25). Üôïô úáíåþáôåìøîùê òåúõìøôáô---ïäîï éú óìåäóô÷éê îáûåê óìåäõàýåê ôåïòåíù. {\let\newpar=\par \proclaim Ôåïòåíá D. (Ë.~Ûåîóôåä, Í.~Ð.~Ûàãåîâåòöå.) Ðõóôø $$ \pmatrix{ q_1 & q_2 & \ldots & q_n \cr p_1 & p_2 & \ldots & p_n \cr } \eqno(27) $$ ---ä÷õóôòïþîùê íáóóé÷, óïïô÷åôóô÷õàýéê ðáòå ôáâìï~$(P, Q)$. %% 78 {\medskip\narrower \item{a)}Åóìé ðïìøúï÷áôøóñ ä÷ïêóô÷åîîùí (ïâòáôîùí) ïôîïûåîéåí ðïòñäëá äìñ~$q$, îï îå äìñ~$p$, ôï ä÷õóôòïþîùê íáóóé÷ $$ \pmatrix{ q_n & \ldots & q_2 & q_1 \cr p_n & \ldots & p_2 & p_1 \cr } \eqno(28) $$ óïïô÷åôóô÷õåô ðáòå~$(P^T, (Q^S)^T)$. \newpar {\noindent \rm (Ëáë ïâùþîï, þåòåú~$T$ ïâïúîáþåîá ïðåòáãéñ ôòáîóðïîéòï÷áîéñ; $P^T$---ôáâìï, a~$(Q^S)^T$---ä÷ïêóô÷åîîïå ôáâìï, ðïóëïìøëõ üìåíåîôù~$q$ òáóðïìïöåîù ÷ ïâòáôîïí ðïòñäëå.)} \newpar \item{b)}Åóìé ðïìøúï÷áôøóñ ä÷ïêóô÷åîîùí ïôîïûåîéåí ðïòñäëá äìñ~$p$, îï îå äìñ~$q$, ôï ä÷õóôòïþîùê íáóóé÷~(37) óïïô÷åôóô÷õåô ðáòå~$((P^S)^T, Q^T)$. \newpar \item{c)}Åóìé ðïìøúï÷áôøóñ ä÷ïêóô÷åîîùí ïôîïûåîéåí ðïòñäëá ëáë äìñ~$p$, ôáë é äìñ~$q$, ôï ä÷õóôòïþîùê íáóóé÷~(28) óïïô÷åôóô÷õåô ðáòå~$(P^S, Q^S)$. \newpar} \par } \proof Îå éú÷åóôîï ðòïóôïçï äïëáúáôåìøóô÷á üôïê ôåïòåíù. Ôï, þôï óìõþáê~(a) óïïô÷åôóô÷õåô ðáòå~$(P^T, X)$, çäå~$X$---îåëïôïòïå ä÷ïêóô÷åîîïå ôáâìï, äïëáúáîï ÷ õðò.~6; óìåäï÷áôåìøîï, ðï ôåïòåíå~B, óìõþáê~(b) óïïô÷åôóô÷õåô ðáòå~$(Y, Q^T)$, çäå~$Y$---îåëïôïòïå ä÷ïêóô÷åîîïå ôáâìï ôïê öå æïòíù, þôï é~$P^T$. Ðõóôø~$p_i=\min\set{p_1,~\ldots, p_n}$; ôáë ëáë~$p_i$---"îáéâïìøûéê" üìåíåîô ðòé ä÷ïêóô÷åîîïí ïôîïûåîéé ðïòñäëá, ôï ïî ïëáöåôóñ îá çòáîéãå~$Y$ é îå ÷ùôåóîñåô îéëáëéè üìåíåîôï÷ ðòé ðïóôòïåîéé éú ôåïòåíù~A. Ôáëéí ïâòáúïí, åóìé ðïóìåäï÷áôåìøîï ÷óôá÷ìñôø üìåíåîôù~$p_1$,~\dots, $p_{i-1}$, $p_{i+1}$,~\dots, $p_n$, ðòéíåîññ ä÷ïêóô÷åîîïå ïôîïûåîéå ðïòñäëá, ôï ðïìõþéôóñ~$Y-\set{p_i}$, ô.å.~$Y$, éú ëïôïòïçï õäáìåî üìåíåîô~$p_i$. Ðï ôåïòåíå~C, åóìé ðïóìåäï÷áôåìøîï ÷óôá÷ìñôø üìåíåîôù~$p_1$,~\dots, $p_{i-1}$, $p_{i+1}$,~\dots, $p_n$, ðòéíåîññ ïâùþîïå ïôîïûåîéå ðïòñäëá, ðïóôòïéí ôáâìï~$d(P)$, ëïôïòïå ðïìõþáåôóñ ðõôåí ðòéíåîåîéñ ë~$P$ áìçïòéôíá~S. Éîäõëãéñ ðï~$n$ äáåô~$Y-\set{p_i}=(d(P)^S)^T$. Îï ðïóëïìøëõ $$ (P^S)^T-\set{p_i}=(d(P)^S)^T \eqno (29) $$ ðï ïðòåäåìåîéà ïðåòáãéé~$S$, á $Y$~éíååô ôõ öå æïòíõ, þôï é~$(P^S)^T$, ôï äïìöîï éíåôø íåóôï òá÷åîóô÷ï~$Y=(P^S)^T$. Ôåí óáíùí äïëáúáîï õô÷åòöäåîéå~(b); (a)~ðïìõþáåôóñ ðòéíåîåîéåí ôåïòåíù~B. Ðïóìåäï÷áôåìøîïå ðòéíåîåîéå~(a) é~(b) ðïëáúù÷áåô, þôï óìõþáê~(c) óïïô÷åôóô÷õåô ðáòå~$(((P^T)^S)^T, ((Q^S)^T)^T)$, a üôï òá÷îï~$(P^S, Q^S)$, ôáë ëáë~$(P^S)^T=(P^T)^S$ ÷óìåäóô÷éå óéííåôòéé ïðåòáãéé~$S$ ðï ïôîïûåîéà ë óôòïëáí é óôïìâãáí. \proofend Üôá ôåïòåíá, ÷ þáóôîïóôé, õóôáîá÷ìé÷áåô ä÷á õäé÷éôåìøîùè æáëôá, ëáóáàýéèóñ áìçïòéôíá ÷óôá÷ëé ÷ ôáâìï. Åóìé ÷ òåúõìøôáôå ðïóìåäï÷áôåìøîïê ÷óôá÷ëé òáúìéþîùè üìåíåîôï÷~$p_1$,~\dots, $p_n$ %% 79 ÷ ðõóôïå ôáâìï ðïìõþáåôóñ ôáâìï~$P$, ôï ÷ òåúõìøôáôå ÷óôá÷ëé üôéè üìåíåîôï÷ ÷ ïâòáôîïí ðïòñäëå---$p_n$,~\dots, $p_1$, ðïìõþéôóñ \dfn{ôòáîóðïîéòï÷áîîïå} ôáâìï~$P^T$. Åóìé öå íù îå ôïìøëï óôáîåí ÷óôá÷ìñôø üìåíåîôù ÷ ðïòñäëå~$p_n$,~\dots, $p_1$, îï é ðïíåîñåí òïìñíé~$<$ é~$>$, á ôáëöå~$0$ é~$\infty$, ôï ðïìõþéí ä÷ïêóô÷åîîïå ôáâìï~$P^S$. Îáóôïñôåìøîï òåëïíåîäõåí þéôáôåìà éóðùôáôø üôé ðòïãåóóù îá îåóëïìøëéè ðòïóôùè ðòéíåòáè. Îåïâùþîáñ ðòéòïäá üôéè óï÷ðáäåîéê íïöåô ÷ùú÷áôø ðïäïúòåîéå ï ÷íåûáôåìøóô÷å ëáëéè-ôï ëïìäï÷óëéè óéì. Äï óéè ðïò îå éú÷åóôîï ëáëïçï-ìéâï ðòïóôïçï ïâ®ñóîåîéñ ðïäïâîùè ñ÷ìåîéê; ëáöåôóñ, îå óõýåóô÷õåô ðòïóôïçï óðïóïâá äïëáúáôø äáöå ôï, þôï óìõþáê~(c) óïïô÷åôóô÷õåô ôáâìï ôïê öå \emph{æïòíù,} þôï~$P$ é~$Q$. Óïïô÷åôóô÷éå, õóôáîá÷ìé÷áåíïå ôåïòåíïê~A, îáêäåîï Ö.~Òïâéîóïîïí [{\sl American J.\ Math.,\/} {\bf 60} (1938), 745--760, Sec.~5] ÷ îåóëïìøëï éîïê é äï÷ïìøîï ôõíáîîïê æïòíå ëáë þáóôø òåûåîéñ ÷åóøíá óìïöîïê úáäáþé éú ôåïòéé çòõðð. Îåôòõäîï ðòï÷åòéôø, þôï åçï ðïóôòïåîéå ÷ óõýîïóôé éäåîôéþîï ðòé÷åäåîîïíõ úäåóø. Ïî óæïòíõìéòï÷áì ôåïòåíõ~B âåú äïëáúáôåìøóô÷á. Íîïçï ìåô óðõóôñ Ë.~Ûåîóôåä îåúá÷éóéíï úáîï÷ï ïôëòùì üôï óïïô÷åôóô÷éå, ëïôïòïå ïî óæïòíõìéòï÷áì ðï óõýåóô÷õ ÷ ôïê öå æïòíå, ëáëõà éóðïìøúï÷áìé íù [{\sl Canadian J.\ Math.,\/} {\bf 13} (1961), 179--191]. Ïî ôáëöå äïëáúáì "$P$"-þáóôø ôåïòåíù~D~(a). Í.~Ð.~Ûàãåîâåòöå [{\sl Math. Scand.,\/} {\bf 12} (1963), 117--128] äïëáúáì ôåïòåíõ~B é "$Q$"-þáóôø ôåïòåíù~D~(a), éú ëïôïòïê óìåäõàô~(b) é~(c). Üôï óïïô÷åôóô÷éå íïöîï òáóðòïóôòáîéôø é îá ðåòåóôáîï÷ëé íõìøôéíîïöåóô÷; óìõþáê, ëïçäá~$p_1$,~\dots, $p_n$ îå ïâñúáôåìøîï òáúìéþîù, òáóóíïôòåì Ûåîóôåä, á "íáëóéíáìøîïå" ïâïâýåîéå îá óìõþáê, ëïçäá é~$p$, é~$q$ íïçõô óïäåòöáôø ðï÷ôïòñàýéåóñ üìåíåîôù, éóóìåäï÷áîï Ëîõôïí [{\sl Pacific J.\ Math.,\/} {\bf 34} (1970), 709--727]. Ïâòáôéíóñ ôåðåòø ë òïäóô÷åîîïíõ ÷ïðòïóõ: \emph{óëïìøëï ôáâìï, óïóôá÷ìåîîùè éú üìåíåîôï÷~$\set{1, 2,~\ldots, n}$, éíåàô äáîîõà æïòíõ~$(n_1, n_2,~\ldots, n_m)$, çäå~$n_1+n_2+\cdots+n_m=n$?} Ïâïúîáþéí üôï þéóìï þåòåú~$f(n_1, n_2,~\ldots, n_m)$; ïîï äïìöîï õäï÷ìåô÷ïòñôø óïïôîïûåîéñí $$ \displaylines{ f(n_1, n_2, \ldots, n_m)=0, \rem{åóìé îå ÷ùðïìîåîï õóìï÷éå~$n_1\ge n_2\ge \ldots\ge n_m\ge 0$;} \hfill \llap{(30)}\cr f(n_1, n_2, \ldots, n_m, 0)=f(n_1, n_2, \ldots, n_m); \hfill\llap{(31)}\cr f(n_1, n_2, \ldots, n_m)=f(n_1-1, n_2, \ldots, n_m) +f(n_1, n_2-1, \ldots, n_m)+\cdots+f(n_1, n_2, \ldots, n_m-1),\hfill\cr \hfill \rem{åóìé $n_1\ge n_2 \ge \ldots \ge n_m \ge 1$.}\quad (32)\cr } $$ Ðïóìåäîåå òåëõòòåîôîïå óïïôîïûåîéå ÷ùôåëáåô éú ôïçï æáëôá, þôï ðòé õäáìåîéé îáéâïìøûåçï üìåíåîôá ôáâìï ÷óåçäá óîï÷á ðïìõþáåôóñ ôáâìï; îáðòéíåò, ëïìéþåóô÷ï ôáâìï æïòíù~$(6, 4, 4, 1)$ òá÷îï~$f(5, 4, 4, 1)+f(6, 3, 4, 1)+f(6, 4, 3, 1) + f(6, 4, 4, 0)=f(5, 4, 4, 1) %%80 +f(6, 4, 3, 1)+f(6, 4, 4)$, ðïôïíõ þôï ÷óñëïå ôáâìï æïòíù~$(6, 4, 4, 1)$ éú üìåíåîôï÷~$\set{1, 2,~\ldots, 15}$ ðïìõþáåôóñ ÷ òåúõìøôáôå ÷óôá÷ëé üìåíåîôá~$15$ ÷ ðïäèïäñýåå íåóôï ÷ ôáâìï æïòíù~$(5, 4, 4, 1)$, $(6, 4, 3, 1)$ éìé~$(6, 4, 4)$. Éúïâòáúéí üôï îá óèåíå \picture{p. 80, (33)} Æõîëãéñ~$f(n_1, n_2,~\ldots, n_m)$, õäï÷ìåô÷ïòñàýáñ ôáëéí óïïôîïûåîéñí, éíååô äï÷ïìøîï ðòïóôïê ÷éä: $$ f(n_1, n_2,~\ldots, n_m)= {\Delta(n_1+m-1, n_2+m-2, \ldots, n_m) n! \over (n_1+m-1)! (n_2+m-2)! \ldots n_m!} \rem{ðòé~$n_1+m-1\ge n_2+m-2 \ge \ldots \ge n_m,$} \eqno (34) $$ çäå þåòåú~$\Delta$ ïâïúîáþåî äåôåòíéîáîô $$ \Delta(x_1, x_2, \ldots, x_m)=\det\pmatrix{ x_1^{m-1} & x_2^{m-1} & \ldots & x_m^{m-1}\cr \vdots & & & \vdots \cr x_1^2 & x_2^2 & & x_m^2 \cr x_1 & x_2 & & x_m \cr 1 & 1 & \ldots & 1 \cr }=\prod_{1\le i < j \le m} (x_i-x_j) \eqno(35) $$ Æïòíõìõ~(34) ÷ù÷åì Æ.~Æòïâåîéõó [Sitzungsberichte Preuss. Akad.\ der Wissenchaften (Berlin, 1900), 516--534, Sec.~3], éúõþáñ üë÷é÷áìåîôîõà úáäáþõ ôåïòéé çòõðð; ïî éóðïìøúï÷áì äï÷ïìøîï çìõâïëõà áòçõíåîôáãéà, ïðéòáàýõàóñ îá ôåïòéà çòõðð. Ëïíâéîáôïòîïå äïëáúáôåìøóô÷ï îåúá÷éóéíï îáûåì Íáë-Íáçïî [{\sl Philosophical Trans.,\/} {\bf A-209} (London, 1909), 153--175]. Üôõ æïòíõìõ íïöîï äïëáúáôø ðï éîäõëãéé, ôáë ëáë~(30) é~(31) äïëáúù÷áàôóñ âåú ôòõäá, á æïòíõìá~(32) ðïìõþáåôóñ, åóìé ðïìïöéôø~$y=-1$ ÷ ôïöäåóô÷å õðò.~17. Éú ôåïòåíù~A ÷ ó÷ñúé ó üôïê æïòíõìïê äìñ þéóìá ôáâìï ÷ùôåëáåô úáíåþáôåìøîïå ôïöäåóô÷ï. ×úñ÷ óõííõ ðï ÷óå÷ïúíïöîùí %%81 æïòíáí ôáâìï, ðïìõþéí $$ \eqalign{ n! &= \sum_{\scriptstyle k_1\ge \ldots \ge k_n \ge 0 \atop \scriptstyle k_1+\cdots+k_n=n} f(k_1, \ldots, k_n)^2=\cr &= n!^2 \sum_{\scriptstyle k_1\ge \ldots \ge k_n \ge 0 \atop \scriptstyle k_1+\cdots+k_n=n} {\Delta(k_1+n-1, \ldots, k_n)^2 \over (k_1+n-1)!^2\ldots k_n!^2}=\cr &= n!^2 \sum_{\scriptstyle q_1>q_2>\ldots>q_n\ge 0 \atop \scriptstyle q_1+\cdots+q_n=(n+1)n/2} {\Delta(q_1, \ldots, q_n)^2 \over q_1!^2\ldots q_n!^2};\cr } $$ ïôóàäá $$ \sum_{\scriptstyle q_1+\cdots+q_n=(n+1)n/2 \atop \scriptstyle q_1 \ldots q_n \ge 0} {\Delta(q_1,\ldots, q_n)^2\over q_1!^2 \ldots q_n!^2} = 1. \eqno(36) $$ × ðïóìåäîåê óõííå ïôóõôóô÷õàô îåòá÷åîóô÷á~$q_1>q_2>\ldots>q_n$, ðïôïíõ þôï óìáçáåíùå---óéííåôòéþîùå ïôîïóéôåìøîï~$q$ æõîëãéé, ïâòáýáàýéåóñ ÷~$0$ ðòé~$q_i=q_j$. Áîáìïçéþîïå ôïöäåóô÷ï ðïñ÷ìñåôóñ ÷ õðò.~24. Æïòíõìõ þéóìá ôáâìï íïöîï ÷ùòáúéôø îåóëïìøëï âïìåå éîôåòåóîùí óðïóïâïí, åóìé ÷÷åóôé ðïîñôéå "õçïìëï÷". × \dfn{õçïìïë,} óïïô÷åôóô÷õàýéê \picture{Òéó~5. Õçïìëé é äìéîù õçïìëï÷.} ëìåôëå ôáâìï, ÷èïäéô óáíá üôá ëìåôëá ðìàó ÷óå ëìåôëé, ìåöáýéå óîéúõ é óðòá÷á ïô îåå. Îáðòéíåò, úáûôòéèï÷áîîùê õþáóôïë îá òéó.~5---õçïìïë, óïïô÷åôóô÷õàýéê ëìåôëå~$(2, 3)$ óôòïëé~2 é óôïìâãá~3; ïî óïóôïéô éú ûåóôé ëìåôïë. × ëáöäïê ëìåôëå îá òéó.~5 úáðéóáîá äìéîá óïïô÷åôóô÷õàýåçï åê õçïìëá. Åóìé ôáâìï éíååô æïòíõ~$(n_1, n_2,~\ldots, n_m)$, çäå~$n_m\ge 1$, ôï äìéîá óáíïçï äìéîîïçï õçïìëá òá÷îá~$n_1+m-1$. Äáìøîåêûåå éóóìåäï÷áîéå äìéî õçïìëï÷ ðïëáúù÷áåô, þôï óôòïëá~1 óïäåòöéô ÷óå äìéîù~$n_1+m-1$, $n_1+m-2$,~\dots, $1$, \emph{ëòïíå $(n_1+m-1)-(n_m)$, $(n_1+m-1)- %%82 -(n_{m-1}+1)$,~\dots, $(n_1+m-1)-(n_2+m-2)$.} Îáðòéíåò, îá òéó.~5 äìéîù õçïìëï÷ ÷ $1\hbox{-ê}$ óôòïëå óõôø~$12$, $11$, $10$,~\dots, $1$, úá éóëìàþåîéåí~$10$, $9$, $6$, $3$, $2$; üôé éóëìàþåîéñ óïïô÷åôóô÷õàô ðñôé îåóõýåóô÷õàýéí õçïìëáí, îáþéîáàýéíóñ ÷ îåóõýåóô÷õàýéè ëìåôëáè~$(6, 3)$, $(5, 3)$, $(4, 5)$, $(3, 7)$, $(2, 7)$ é úáëáîþé÷áàýéíóñ ÷ ëìåôëå~$(1, 7)$. Áîáìïçéþîï $j\hbox{-ñ}$~óôòïëá óïäåòöéô ÷óå äìéîù õçïìëï÷~$n_j+m-j$,~\dots, $1$, ëòïíå~$(n_j+m-j)-(n_m)$,~\dots, $(n_j-m-j)-(n_{j+1}-m-j-1)$. Ïôóàäá óìåäõåô, þôï ðòïéú÷åäåîéå äìéî ÷óåè õçïìëï÷ òá÷îï $$ (n_1+m-1)!\ldots{}(n_m)!/\Delta(n_1+m-1,~\ldots, n_m). $$ Üôï ÷ùòáöåîéå ÷èïäéô ÷ æïòíõìõ~(34); ïôóàäá óìåäõåô \proclaim Ôåïòåíá~H. (Äö.~Ó.~Æòüêí, Ö.~Òïâéîóïî, Ò.~Í.~Ôòïìì.) Ëïìéþåóô÷ï ôáâìï äáîîïê æïòíù, óïóôá÷ìåîîùè éú üìåíåîôï÷~$\set{1, 2,~\ldots, n}$, òá÷îï~$n!$, äåìåîîïíõ îá ðòïéú÷åäåîéå äìéî õçïìëï÷. \endmark Ôáëïê ðòïóôïê òåúõìøôáô úáóìõöé÷áåô é ðòïóôïçï äïëáúáôåìøóô÷á; ïäîáëï (ëáë é äìñ âïìøûéîóô÷á äòõçéè æáëôï÷, ëáóáàýéèóñ ôáâìï) âïìåå ðòñíïçï äïëáúáôåìøóô÷á îå éú÷åóôîï. Ëáöäùê üìåíåîô ôáâìï---íéîéíáìøîùê ÷ ó÷ïåí õçïìëå; åóìé úáðïìîéôø ëìåôëé ôáâìï óìõþáêîùí ïâòáúïí, ôï ÷åòïñôîïóôø ôïçï, þôï ÷ ëìåôëå~$(i, j)$ ïëáöåôóñ íéîéíáìøîùê üìåíåîô óïïô÷åôóô÷õàýåçï õçïìëá, åóôø ÷åìéþéîá, ïâòáôîáñ äìéîå õçïìëá. Ðåòåíîïöåîéå üôéè ÷åòïñôîïóôåê ðï ÷óåí~$i$, $j$ äáåô ôåïòåíõ~H. Ïäîáëï ôáëïå òáóóõöäåîéå ïûéâïþîï, ðïóëïìøëõ üôé ÷åòïñôîïóôé ïôîàäø îå ñ÷ìñàôóñ îåúá÷éóéíùíé. ×óå éú÷åóôîùå äïëáúáôåìøóô÷á ôåïòåíù~H ïóîï÷áîù îá ïäîïí îåõâåäéôåìøîïí éîäõëôé÷îïí òáóóõöäåîéé, ëïôïòïå îá óáíïí äåìå îå ïâ®ñóîñåô, ðïþåíõ öå ôåïòåíá ÷åòîá (ôáë ëáë ÷ îåí óï÷åòûåîîï îå éóðïìøúõàôóñ ó÷ïêóô÷á õçïìëï÷). Óõýåóô÷õåô éîôåòåóîáñ ó÷ñúø íåöäõ ôåïòåíïê~H é ðåòåþéóìåîéåí äåòå÷øå÷, ëïôïòïå òáóóíáôòé÷áìïóø ÷ çì.~2. Íù ÷éäåìé, þôï âéîáòîùí äåòå÷øñí ó $n$~õúìáíé óïïô÷åôóô÷õàô ðåòåóôáîï÷ëé, ëïôïòùå íïöîï ðïìõþéôø ó ðïíïýøà óôåëá, é þôï ôáëéí ðåòåóôáîï÷ëáí óïïô÷åôóô÷õàô ðïóìåäï÷áôåìøîïóôé~$a_1\,a_2\,\ldots\,a_{2n}$ ìéôåò~$S$ é~$X$, ôáëéå, þôï ëïìéþåóô÷ï ìéôåò~$S$ îéëïçäá îå âù÷áåô íåîøûå ëïìéþåóô÷á ìéôåò~$X$, åóìé þéôáôø ðïóìåäï÷áôåìøîïóôø óìå÷á îáðòá÷ï. (Óí.~õðò.~2.3.1-6 é~2.2.1-3.) Ôáëéí ðïóìåäï÷áôåìøîïóôñí åóôåóô÷åîîùí ïâòáúïí óïðïóôá÷ìñàôóñ ôáâìï æïòíù~$(n, n)$; ÷ 1-à óôòïëõ ðïíåýáàôóñ éîäåëóù~$i$, ôáëéå, þôï~$a_i=S$, á ÷ï 2-à óôòïëõ---éîäåëóù, ðòé ëïôïòùè~$a_i=X$. Îáðòéíåò, ðïóìåäï÷áôåìøîïóôé $$ S\; S\; S\; X\; X\; S\; S\; X\; X\; S\; X\; X $$ óïïô÷åôóô÷õåô ôáâìï $$ \tableau{ 1 & 2 & 3 & 6 & 7 & 10 \cr 4 & 5 & 8 & 9 & 11 & 12 \cr } \eqno(37) $$ %%83 Õóìï÷éå, îáìáçáåíïå îá óôïìâãù, õäï÷ìåô÷ïòñåôóñ ÷ ôáëïí ôáâìï ÷ ôïí é ôïìøëï ôïí óìõþáå, ëïçäá ðòé þôåîéé óìå÷á îáðòá÷ï þéóìï ìéôåò~X îéëïçäá îå ðòå÷ùûáåô þéóìá ìéôåò~$S$. Ðï ôåïòåíå~H ëïìéþåóô÷ï ÷óå÷ïúíïöîùè ôáâìï æïòíù~$(n, n)$ òá÷îï $$ (2n)!/(n+1)!n!; $$ óìåäï÷áôåìøîï, ôáëï÷ï öå é þéóìï âéîáòîùè äåòå÷øå÷ ó $n$~õúìáíé (þôï óïçìáóõåôóñ ó æïòíõìïê~(2.3.4.4-13)). Âïìåå ôïçï, åóìé ÷ïóðïìøúï÷áôøóñ ôáâìï æïòíù~$(n, m)$ ðòé~$n\ge m$, ôï ðòé ðïíïýé üôïçï òáóóõöäåîéñ íïöîï òåûéôø é âïìåå ïâýõà "úáäáþõ ï âáììïôéòï÷ëå", òáóóíïôòåîîõà ÷ ïô÷åôå ë õðò.~2.2.1-4. Ôáëéí ïâòáúïí, ôåïòåíá~H ÷ ëáþåóô÷å ðòïóôùè þáóôîùè óìõþáå÷ ÷ëìàþáåô ÷ óåâñ îåëïôïòùå ÷åóøíá óìïöîùå úáäáþé ï ðåòåþéóìåîéé. ×óñëïíõ ôáâìï~$A$ æïòíù~$(n, n)$ éú üìåíåîôï÷~$\set{1, 2,~\ldots, 2n}$ óïïô÷åôóô÷õàô ä÷á ôáâìï~$(P, Q)$ ïäéîáëï÷ïê æïòíù. Óìåäõàýéê óðïóïâ ðïóôòïåîéñ ôáëïçï óïïô÷åôóô÷éñ ðòåäìïöåî Íáë-Íáçïîïí [Combinatory Analysis, {\bf 1} (1915), 130--131]. Ðõóôø~$P$ óïóôïéô éú üìåíåîôï÷~$\set{1,~\ldots, n}$, òáóðïìïöåîîùè, ëáë ÷~$A$, á~$Q$ ðïìõþáåôóñ, åóìé ÷úñôø ïóôáìøîùå üìåíåîôù~$A$, ðï÷åòîõôø ÷óà ëïîæéçõòáãéà îá~$180^\circ$ é úáíåîéôø~$n+1$, $n+2$,~\dots, $2n$ îá óïïô÷åôóô÷åîîï~$n$, $n-1$,~\dots, $1$. Îáðòéíåò, ôáâìï~(37) òáóðáäáåôóñ îá $$ \tableau{ 1 & 2 & 3 & 6 \cr 4 & 5 \cr } \hbox{ é } \revtableau{ \omit &\omit \hfil\vrule& 7 & 10 \cr 8 & 9 & 11 & 12\cr }\,; $$ ðïóìå ðï÷ïòïôá é ðåòåîõíåòáãéé éíååí $$ P=\tableau{ 1 & 2 & 3 & 6 \cr 4 & 5 \cr },\quad Q=\tableau{ 1 & 2 & 4 & 5 \cr 3 & 6 \cr }. \eqno(38) $$ Îáïâïòïô, ëáöäïê ðáòå ôáâìï ïäéîáëï÷ïê æïòíù, óïóôïñýéè éá $n$~üìåíåîôï÷ é éú îå âïìåå ä÷õè óôòïë, óïïô÷åôóô÷õåô ôáâìï æïòíù~$(n, n)$. Óìåäï÷áôåìøîï (éú~õðò.~7), \emph{þéóìï ðåòåóôáîï÷ïë~$a_1\,a_2\,\ldots\,a_n$ íîïöåóô÷á~$\set{1, 2,~\ldots, n}$, îå óïäåòöáýéè õâù÷áàýéè ðïäðïóìåäï÷áôåìøîïóôåê~$a_i>a_j>a_k$ ðòé~$ia_k>a_i$ é~$ia_{j_2}>\ldots>a_{j_r}$, çäå~$j_1n_2>\ldots>n_m$ ïðéóù÷áàô æïòíõ "óä÷éîõôïçï ôáâìï", ÷ ëïôïòïí óôòïëá~$i+1$ îáþéîáåôóñ îá ïäîõ ðïúéãéà, ðòá÷åå, þåí óôòïëá~$i$; îáðòéíåò, óä÷éîõôïå ôáâìï æïòíù~$(7, 5, 4, 1)$ éúïâòáöåîï îá äéáçòáííå \picture{3. p.90} Äïëáöéôå, þôï þéóìï óðïóïâï÷ úáðïìîéôø óä÷éîõôïå ôáâìï æïòíù~$(n_1, n_2,~\ldots, n_m)$ þéóìáíé~$1$, $2$,~\dots, $n=n_1+n_2+\cdots n_m$ ôáë, þôïâù þéóìá ÷ï ÷óåè óôòïëáè é óôïìâãáè òáóðïìáçáìéóø ÷ ÷ïúòáóôáàýåí ðïòñäëå, òá÷îï þáóôîïíõ ïô äåìåîéñ~$n!$ îá ðòïéú÷åäåîéå "äìéî ïâïâýåîîùè õçïìëï÷"; îá òéóõîëå úáûôòéèï÷áî ïâïâýåîîùê õçïìïë äìéîù~$11$, óïïô÷åôóô÷õàýéê ëìåôëå óôòïëé~$1$ é óôïìâãá~$2$. (Õçïìëé ÷ ìå÷ïê þáóôé íáóóé÷á, éíåàýåê ÷éä "ðåòå÷åòîõôïê ìåóôîéãù", éíåàô %% 91 æïòíõ âõë÷ù~U, ðï÷åòîõôïê îá~$90^\circ$, á îå âõë÷ù~L.) Éôáë, óõýåóô÷õåô $$ 17! / 12\cdot 11\cdot 8\cdot 7\cdot 5\cdot 4\cdot 1\cdot 9\cdot 6\cdot 5\cdot 3\cdot 2\cdot 5\cdot 4\cdot 2\cdot 1\cdot 1 $$ óðïóïâï÷ úáðïìîéôø éúïâòáöåîîõà ÷ùûå æïòíõ ôáë, þôïâù üìåíåîôù ÷ï ÷óåè óôòïëáè é óôïìâãáè òáóðïìáçáìéóø ÷ ÷ïúòáóôáàýåí ðïòñäëå. \rex[×Í30] (Ä.~Áîäòü). Þåíõ òá÷îï þéóìï~$A_n$ óðïóïâï÷ úáðïìîéôø þéóìáíé~$\set{1, 2,~\ldots, n}$ íáóóé÷ éú $n$~ñþååë \picture{p.91} ôáë, þôïâù ÷ï ÷óåè óôòïëáè é óôïìâãáè ïîé òáóðïìáçáìéóø ÷ ÷ïúòáóôáàýåí ðïòñäëå? Îáêäéôå ðòïéú÷ïäñýõà æõîëãéà~$g(z)=\sum A_n z^n/n!$ \ex[M39] Óëïìøëéíé óðïóïâáíé íïöîï úáðïìîéôø íáóóé÷ æïòíù~$(n_1, n_2,~\ldots, n_m)$ üìåíåîôáíé íîïöåóô÷á~$\set{1, 2,~\ldots, N}$, \emph{åóìé äïðõóëáàôóñ ïäéîáëï÷ùå üìåíåîôù,} ðòéþåí ÷ óôòïëáè üìåíåîôù äïìöîù òáóðïìáçáôøóñ ÷ îåõâù÷áàýåí ðïòñäëå, á ÷ óôïìâãáè---÷ óôòïçï ÷ïúòáóôáàýåí? Îáðòéíåò, ðòïóôõà æïòíõ éú $m$~óôòïë $(1, 1,~\ldots, 1)$ íïöîï úáðïìîéôø $\perm{N}{m}$~óðïóïâáíé; æïòíõ éú ïäîïê óôòïëé~$m$ íïöîï úáðïìîéôø $\perm{m+N-1}{m}$~óðïóïâáíé; æïòíõ~$(2, 2)$ íïöîï úáðïìîéôø ${1\over3}\perm{N+1}{2}\perm{N}{2}$~óðïóïâáíé. \ex[Í28] Äïëáöéôå, þôï $$ \displaylines{ \sum_{\scriptstyle q_1+\cdots+q_=t \atop \scriptstyle 0\le q_1,~\ldots, q_n\le m} \perm{m}{q_1}\ldots\perm{m}{q_n}\Delta(q_1,~\ldots, q_n)^2=\hfill\cr \hfill =n!\perm{nm-(n^2-n)}{t-{1\over 2}(n^2-n)} \perm{m}{n-1} \perm{m}{n-2}\ldots \perm{m}{0}\Delta(n-1,~\ldots, 0)^2. \cr } $$ [\emph{Õëáúáîéñ:} äïëáöéôå, þôï~$\Delta(k_1+n-1,~\ldots, k_n)=\Delta(m-k_n+n-1,~\ldots, m-k_1)$; òáúìïöéôå ôáâìï æïòíù~$n\times (m-n+1)$ óðïóïâïí, áîáìïçéþîùí~(38), é ðòåïâòáúõêôå óõííõ, ëáë ðòé ÷ù÷ïäå ôïöäåóô÷á~(36).] \ex[Í20] Ðïþåíõ~(42) ñ÷ìñåôóñ ðòïéú÷ïäñýåê æõîëãéåê äìñ éî÷ïìàãéê? \ex[×Í21] ×ùþéóìéôå~$\int_{-\infty}^\infty x^t \exp(-2x^2/ \sqrt{n})\,dx$ ðòé îåïôòéãáôåìøîïí ãåìïí~$t$. \ex[Í24] Ðõóôø~$Q$---ôáâìï Ñîçá éú üìåíåîôï÷~$\set{1, 2,~\ldots, n}$, é ðõóôø üìåíåîô~$t$ îáèïäéôóñ ÷ óôòïëå~$r_i$ é óôïìâãå~$c_i$. Íù çï÷ïòéí, þôï~$i$ "÷ùûå"~$j$, åóìé~$r_ia_{i+1}$. (Óìåäï÷áôåìøîï, íïöîï îáêôé þéóìï ïôòåúëï÷ ðåòåóôáîï÷ëé, úîáñ ôïìøëï~$Q$. Üôïô òåúõìøôáô ðïìõþåî Ûàãåîâåòöå.) % \item{c)}~Äïëáöéôå, þôï ðòé~$1\le i < n$ üìåíåîô~$i$ ÷ùûå~$i+1$ ÷~$Q$ ôïçäá é ôïìøëï ôïçäá, ëïçäá~$i+1$ ÷ùûå~$i$ ÷~$Q^S$. \medskip} \ex[Í47] Ëáëï÷ï áóéíðôïôéþåóëïå ðï÷åäåîéå óòåäîåê äìéîù íáëóéíáìøîïê ÷ïúòáóôáàýåê ðïóìåäï÷áôåìøîïóôé ÷ óìõþáêîïê ðåòåóôáîï÷ëå íîïöåóô÷á~$\set{1, 2,~\ldots, n}$? (Üôï óòåäîññ äìéîá ðåò÷ïê óôòïëé ÷ óïïô÷åôóô÷éé éú ôåïòåíù~A. Ïâûéòîùå ôáâìéãù, ÷ùþéóìåîîùå Ò.~Í.~Âáåòïí é~Ð.~Âòïëïí [{\sl Math. Comp.,\/} {\bf 22} (1968), 385--410], ÷ ó÷ñúé ó ôåí, þôï ïîé îáú÷áìé "åóôåóô÷åîîïê óïòôéòï÷ëïê", ðïú÷ïìñàô ðòåäðïìïöéôø, þôï óòåäîåå~$l_n$ òá÷îï ðòéíåòîï~$2\sqrt{n}$; Ì.~Ûåðð é~Â.~Ìïçáî äïëáúáìé, þôï~$\liminf_{n\to\infty} l_n / \sqrt{n}\ge 2$ (÷ ðåþáôé). \ex[Í50] Éóóìåäõêôå ôòåèíåòîùå íáóóé÷ù, ó ôåí þôïâù ðïîñôø, ëáëéå ó÷ïêóô÷á ä÷õíåòîùè ôáâìï íïöîï ïâïâýéôø. \ex[Í42] (Í.~Ð.~Ûàãåîâåòöå). Ðïëáöéôå, þôï ïðåòáãéñ ðåòåèïäá ïô~$P$ ë~$P^S$---þáóôîùê óìõþáê ïðåòáãéé, ëïôïòõà íïöîï ó÷ñúáôø ó ìàâùí ëïîåþîùí þáóôéþîï õðïòñäïþåîîùí íîïöåóô÷ïí, á îå ôïìøëï ó ôáâìï. Ðïíåôøôå üìåíåîôù þáóôéþîï õðïòñäïþåîîïçï íîïöåóô÷á ãåìùíé þéóìáíé~$\set{1, 2,~\ldots, n}$ ôáë, þôïâù üôá óéóôåíá íåôïë âùìá óïçìáóï÷áîá ó þáóôéþîùí õðïòñäïþåîéåí. Îáêäéôå ä÷ïêóô÷åîîõà óéóôåíõ íåôïë, áîáìïçéþîõà~(26), ðõôåí ðïóìåäï÷áôåìøîïçï õäáìåîéñ íåôïë~$1$, $2$,~\dots, ðåòåä÷éçáñ ðòé üôïí äòõçéå íåôëé óðïóïâïí, ðïäïâîùí áìçïòéôíõ~S, é ðïíåýáñ íåôëé~(1), (2),~\dots{} îá ïó÷ïâïäé÷ûéåóñ íåóôá. Ðïëáöéôå, þôï üôá ïðåòáãéñ, åóìé åå íîïçïëòáôîï ðòéíåîñôø ë ä÷ïêóô÷åîîïê óéóôåíå íåôïë ó ïâòáôîùí ïôîïûåîéåí ðïòñäëá äìñ þéóåì, äáåô éóèïäîõà óéóôåíõ íåôïë; éóóìåäõêôå äòõçéå ó÷ïêóô÷á üôïê ïðåòáãéé \ex[×Í30] Ðõóôø~$x_n$---þéóìï óðïóïâï÷ òáúíåóôéôø~$n$ ÷úáéíîï îåáôáëõàýéè ìáäåê îá ûáèíáôîïê äïóëå òáúíåòá~$n\times n$ ôáëéí ïâòáúïí, þôï òáóðïìïöåîéå îå íåîñåôóñ ðòé ïôòáöåîéé äïóëé ïôîïóéôåìøîï ïäîïê éú çìá÷îùè äéáçïîáìåê é ðòé ðï÷ïòïôå îá~$180^\circ$. Îáêäéôå áóéíðôïôéþåóëïå ðï÷åäåîéå~$x_n$. %% 93 \bye