vavilov_n_a_ne_sovsem_naivnaya_teoriya_mnozhestv

MNOVESTWA, OTOBRAVENIQ, OTNO[ENIQ: not entirely naive

361

4. sLOVENIE I KOMMUTIROWANIE WEKTORNYH POLEJ. pUSTX M — DIFFE-

RENCIRUEMOE MNOGOOBRAZIE (MOVNO DLQ PROSTOTY OGRANI^ITXSQ MNOGOOBRAZIQMI KLASSA s1). oBOZNA^IM ^EREZ Vect(M) MNOVESTWO DIFFERENCIRUEMYH WEKTORNYH POLEJ NA M. tOGDA NA Vect(M) OPREDELENY DWA BINARNYH ZAKONA KOMPOZICII: SLOVENIE I KOMMUTIROWANIE (SKOBKA lI) WEKTORNYH POLEJ. nAPOMNIM, ^TO \LEMENTY Vect(M) MOVNO MYSLITX KAK DIFFERENCIALXNYE OPERATORY PERWOGO PORQDKA W KOLXCE DIFFERENCIRUEMYH FUNKCIJ NA M. pRI \TOM, ESLI x1; : : : ; xn — LOKALXNYE KOORDINATY, A fi, gi — DIFFERENCIRUEMYE FUNKCII \TIH KOORDINAT, TO SKOBKA

lI WEKTORNYH POLEJ

@

I

@

OPISYWAETSQ SLEDU@]IM OBRA

X = Pfi @xi

Y =

Pgi @xi

-

ZOM159:

;

n

n

@gi

@fi

[X; Y ] = i=1 j=1 fj @xj

¡ gj @xj

X X

5. lINEJNAQ SWQZNOSTX (‘KOWARIANTNAQ PROIZWODNAQ’) I KRU^ENIE. pRED-

[ESTWU@]IJ PRIMER OTNOSITSQ K DIFFERENCIALXNOJ TOPOLOGII. sOBSTWENNO DIFFERENCIALXNAQ GEOMETRIQ NA^INAETSQ S WWEDENIQ E]E ODNOGO ZAKONA KOMPOZICII NA Vect(M). pUSTX, KAK I W PREDYDU]EM PRIMERE, M — DIFFERENCIRUEMOE MNOGOOBRAZIE. lINEJNOJ SWQZNOSTX@ NA M NAZYWAETSQ ZAKON KOMPOZICII

r : Vect(M) £ Vect(M) ¡! Vect(M);

UDOWLETWORQ@]IJ NEKOTORYM ESTESTWENNYM PREDPOLOVENIQM160. pRI \TOM WEKTORNOE POLE r(X; Y ) OBY^NO OBOZNA^AETSQ rX(Y ) I NAZYWAETSQ KOWARIANTNOJ PROIZWODNOJ POLQ Y WDOLX POLQ X. iMENNO OPERACII [X; Y ] I r(X; Y ) I SWQZYWA- @]IE IH TOVDESTWA PRIDA@T OSNOWAM RIMANOWOJ GEOMETRII OT^ETLIWO ALGEBRAI^E- SKIJ HARAKTER, ZATEMNQEMYJ W TRADICIONNYH IZLOVENIQH KOORDINATNYMI OBOZNA- ^ENIQMI. gROMADNU@ ROLX W GEOMETRII IGRA@T RAZLI^NYE PROIZWODNYE OPERACII, MNOGIE IZ KOTORYH IME@T SPECIALXNYE NAZWANIQ. nAPRIMER, ZAKON KOMPOZICII

T (X; Y ) = r(X; Y ) ¡ r(Y; X) ¡ [X; Y ]

IZWESTEN KAK TENZOR KRU^ENIQ (SM. TAKVE x ?, GDE WWODITSQ TENZOR KRIWIZNY).

159d.gROMOL, w.kLINGENBERG, w.mEJER rIMANOWA GEOMETRIQ W CELOM — 1971, x 1.9).

160ibid., x 2.1.

362	NIKOLAJ WAWILOW

tEMA 2: wavnej{ie tovdestwa

iSTINNOE OTLI^IE ALGEBRAI^ESKIH OPERACII OT WSEH PRO^IH OTOBRAVENIJ SOSTOIT W TOM, ^TO OBY^NO PREDPOLAGAETSQ, ^TO ONI UDOWLETWORQ@T ^REZWY^AJNO PROSTYM FUNKCIONALXNYM URAWNENIQM, KOTORYE W ALGEBRE OBY^NO NAZYWA@TSQ TOVDESTWAMI161. oSOBENNO PODROBNO RASSMOTRENY TOVDESTWA ASSOCIATIWNOSTI I KOMMUTATIWNOSTI, I DWA NAIBOLEE WAVNYH TOVDESTWA, W KOTORYE WHODQT DWE OPE-

RACII – DISTRIBUTIWNOSTX I TOVDESTWO qKOBI.

x 1. aSSOCIATIWNOSTX

mONTIROWAL s@ROPOW DINAMI^NO I BESKOMPROMISSNO. u NEGO W \TO WREMQ NA^INAL IZ WSEH (IZWINITE) INTELLEKTUALXNYH MEST HLESTATX POTOK SOZNANIQ. oN BYL BESSPORNYM NEPRIZNANNYM ASSOM ASSOCIATIWNOGO MONTAVA. pO\TOMU ON POWS@- DU ASSOCIIROWAL.

aLEKSANDR sOLOWXEW, ‘Sun-TEHNIKA’

nAIBOLEE WAVNYM WO WSEJ MATEMATIKE NESOMNENNO QWLQETSQ TOVDESTWO ASSOCIATIWNOSTI.

1. aSSOCIATIWNOSTX. sLEDU@]EE TOVDESTWO IZWESTNO NAM IZ NA- ^ALXNOJ [KOLY, GDE ONO OBY^NO NAZYWAETSQ SO^ETATELXNYM ZAKONOM, TERMIN ‘ASSOCIATIWNOSTX’ BYL WWEDEN gAMILXTONOM W 1843 GODU.

oPREDELENIE. oPREDELENNAQ NA MNOVESTWE X OPERACIQ ¤ NAZYWA- ETSQ ASSOCIATIWNOJ, ESLI (x¤y)¤z = x¤(y ¤z) DLQ L@BYH x; y; z 2 X

w PREFIKSNOJ ZAPISI \TO TOVDESTWO PRINIMAET WID SLEDU@]EGO FUNKCIONALXNOGO URAWNENIQ

f(f(x; y); z) = f(x; f(y; z));

ILI, W FORME lUKASEWI^A ffxyz = fxfyz.

161w \TOJ GLAWE OBSUVDA@TSQ LI[X NESKOLXKO PROSTEJ[IH TOVDESTW. kROME NIH W ALGEBRE ISPOLXZU@TSQ SOTNI DRUGIH TOVDESTW. ~ASTX \TIH TOVDESTW, KAK, SKAVEM, IZU^AEMYE W [KOLE FORMULY SOKRA]ENNOGO UMNOVENIQ, QWLQ@TSQ SLEDSTWIQMI RASSMOTRENNYH ZDESX OSNOWNYH TOVDESTW. nAPRIMER, BINOM nX@- TONA ESTX SLEDSTWIE ASSOCIATIWNOSTI I KOMMUTATIWNOSTI SLOVENIQ I UMNOVENIQ I DISTRIBUTIWNOSTI UMNOVENIQ OTNOSITELXNO SLOVENIQ. dRUGOJ TIP TOVDESTW

— \TO TOVDESTWA WYDELQ@CIE NE NOWYE TIPY ALGEBRAI^ESKIH SISTEM, A BOLEE UZKIE KLASSY SISTEM DANNOGO TIPA, KAK, SKAVEM \NGELEWO ILI BERNSAJDOWY TOVDESTWA W TEORII GRUPP. nUVNO IMETX NEKIJ NAWYK WY^ISLENIJ W TEORII GRUPP,

^TOBY BYTX W SOSTOQNII OCENITX, KAK MOVNO ISPOLXZOWATX TOVDESTWA NAPODOBIE xyx¡1y¡1z = zxyx¡1y¡1.

MNOVESTWA, OTOBRAVENIQ, OTNO[ENIQ: not entirely naive

363

pRIMERY ASSOCIATIWNYH OPERACIJ:

²SLOVENIE I UMNOVENIE ^ISEL,

²SLOVENIE I UMNOVENIE MNOGO^LENOW,

²SLOVENIE I UMNOVENIE MATRIC,

²KOMPOZICIQ FUNKCIJ ILI OTNO[ENIJ,

²OB_EDINENIE I PERESE^ENIE MNOVESTW,

²WZQTIE SUPREMUMA I INFIMUMA,

²SWERTKA.

w x ? MY OBSUDIM NEKOTORYE PROSTEJ[IE SLEDSTWIQ ASSOCIATIWNOSTI I PRIWEDEM MNOGO DALXNEJ[IH PRIMEROW ASSOCIATIWNYH OPERACIJ.

pRIMERY NEASSOCIATIWNYH OPERACIJ:

²WY^ITANIE I DELENIE ^ISEL,

²WOZWEDENIE W STEPENX,

²WEKTORNOE UMNOVENIE WEKTOROW,

²KOMMUTIROWANIE.

w SAMOM DELE, (x ¡ y) ¡ z, WOOB]E GOWORQ, NE RAWNO x ¡ (y ¡ z), A (x=y)=y, WOOB]E GOWORQ, NE RAWNO x=(y=z). |TO E]E ODIN O^ENX SERXEZNYJ ARGUMENT W POLXZU TOGO, ^TOBY NE RASSMATRIWATX WY^ITANIE I DELENIE W KA^ESTWE SAMOSTOQTELXNYH OPERACIJ! tAKVE I OPERACIQ WOZWEDENIQ W STEPENX NEASSOCIATIWNA, (zy)z =6 x(yz). iNTERESNO, ^TO W \TOM SLU^AE OBY^NYJ PORQDOK WYPOLNENIQ OPERACII W OTSUTSTWIE SKOBOK — PRAWONORMIROWANNYJ, T.E. xyz OZNA^AET x(yz) , A WOWSE NE (zy)z, KAK BYLO BY ESTESTWENNO OVIDATX, ^ITAQ FORMULY SLEWA NAPRAWO! oPERACIQ WEKTORNOGO UMNOVENIQ UDOWLETWORQET WAVNEJ[EMU ANALOGU ASSOCIATIWNOSTI — TOVDESTWU qKOBI.

zADA^A. pUSTX ¤ — ASSOCIATIWNAQ OPERACIQ NA X, A a 2 X. dOKAVITE, ^TO TOGDA OPERACIQ x ± y = x ¤ a ¤ y ASSOCIATIWNA.

zADA^A. pUSTX a = (ai) I b = (bi) — DWE BESKONE^NYE POSLEDOWATELXNOSTI, i 2 N. oPREDELIM PEREME[IWANIE \TIH POSLEDOWATELXNOSTEJ KAK POSLEDOWATELXNOSTX a]b = (a1; b1; a2; b2; : : : ). bUDET LI OPERACIQ ] ASSOCIATIWNOJ?

zADA^A. dOKAVITE, ^TO lORENCEWO SLOVENIE ASSOCIATIWNO. rE[ENIE. lEGKO WIDETX, ^TO KAK (u ¢ v) ¢ w, TAK I u ¢ (v ¢ w) RAWNY

u + v + w + uvw

1 + uv + uw + vw:

364	NIKOLAJ WAWILOW

zADA^A. dOKAVITE, ^TO PARALLELXNOE SLOVENIE ASSOCIATIWNO. rE[ENIE. lEGKO WIDETX, ^TO KAK (ukv)kw, TAK I uk(vkw) RAWNY

uvw

uv + uw + vw:

2. oBOB]ENNAQ ASSOCIATIWNOSTX. pREDPOLOVIM, ^TO ZADANNAQ NA

X OPERACIQ ASSOCIATIWNA. w \TOM SLU^AE MY MOVEM OPREDELITX PROIZWEDENIE L@BYH n ¸ 3 \LEMENTOW X PO INDUKCII. a IMENNO, ESLI

x1; : : : ; xn 2 X, TO POLOVIM x1 ¢ ¢ ¢ xn = (x1 ¢ ¢ ¢ xn¡1)xn. |TO OPREDELENIE RAWNOSILXNO LEWONORMIROWANNOJ RASSTANOWKE SKOBOK W PROIZWE-

DENII, T.E., NAPRIMER, DLQ n = 5 IMEEM x1x2x3x4x5 = (((x1x2)x3)x4)x5. zADA^A. gLQDQ NA OPREDELENIE lORENCEWA SLOVENIQ I PARALLELXNOGO SLOVENIQ I NA FORMULY DLQ u ¢ v ¢ w I ukvkw, POLU^ENNYE W PREDYDU]IH ZADA^AH, UGADAJTE FORMULY DLQ u1 ¢ : : : ¢ un I u1k : : : kun.

nO WEDX W PROIZWEDENII PQTI MNOVITELEJ MOVNO POSTAWITX SKOBKI I INA^E, SKAVEM, TAK: (x1x2)(x3(x4x5)). pOLU^ITSQ LI PRI \TOM TOT VE REZULXTAT, ^TO I PRI LEWONORMIROWANNNOJ RASSTANOWKE SKOBOK? aSSOCIATIWNOSTX UTWERVDAET, ^TO DLQ PROIZWEDENIQ TREH MNOVITELEJ \TO DEJSTWITELXNO TAK. oB]IJ SLU^AJ, NAZYWAEMYJ OBOB]ENNOJ ASSOCIATIWNOSTX@, LEGKO POLU^AETSQ OTS@DA PO INDUKCII.

tEOREMA (Allgemeine Klammerregel). pREDPOLOVIM, ^TO OPERA-

CIQ W X ASSOCIATIWNA. tOGDA REZULXTAT UMNOVENIQ n \LEMENTOW X NE ZAWISIT OT RASSTANOWKI SKOBOK.

dOKAZATELXSTWO. (SM. kOSTRIKIN, gL. 4, tEOREMA 1). dOKAZYWAEM PREDLOVENIE PO INDUKCII. dLQ n = 1; 2 UTWERVDENIE TEOREMY O^EWIDNO, A DLQ n = 3 \TO W TO^NOSTI OBY^NAQ ASSOCIATIWNOSTX. pREDPOLOVIM TEPERX, ^TO DLQ WSEH ZNA^ENIJ m < n PREDLOVENIE UVE DOKAZANO, TAK ^TO PRI L@BOJ RASSTANOWKE SKOBOK PROIZWEDENIE L@BYH m < n \LEMENTOW RAWNO IH LEWONORMIROWANNOMU PROIZWEDENI@. mY HOTIM DOKAZATX, ^TO TOGDA I L@BOE PROIZWEDENIE w \LEMENTOW x1; : : : ; xn RAWNO IH LEWONORMIROWANNOMU PROIZWEDENI@. ~TOBY PORQDOK DEJSTWIJ BYL POLNOSTX@ OPREDELEN, TAKOE PROIZWEDENIE DOLVNO SODERVATX ROWNO n ¡ 2 PARY SKOBOK. pOSMOTRIM NA TE PARY SKOBOK, W KOTORYE POPADAET xn, PRI^EM W PERWU@ O^EREDX NA SAMU@ WNE[N@@ IZ NIH. eSLI xn NE OHWATYWAETSQ NI ODNOJ PAROJ SKOBOK, TO w IMEET WID w = uxn, GDE u — NEKOTOROE PROIZWEDENIE x1; : : : ; xn¡1, I MOVNO WOSPOLXZOWATXSQ INDUKCIONNYM PREDPOLOVENIEM. eSLI VE WNE[NQQ PARA SKOBOK OHWATYWAET xn, TO w IMEET WID w = uv, GDE u ESTX NEKOTOROE PROIZWEDENIE x1; : : : ; xm, 1 · m · n ¡ 2, A v ESTX NEKOTOROE PROIZWEDENIE

MNOVESTWA, OTOBRAVENIQ, OTNO[ENIQ: not entirely naive

365

xm+1; : : : ; xn. pROIZWEDENIE v IMEET DLINU n ¡m < n I PO INDUKCIONNOMU PREDPOLOVENI@ EGO MOVNO PEREPISATX W WIDE v = yxn, GDE y ESTX NEKOTOROE PROIZWEDENIE xm+1; : : : ; xn¡1 (W DEJSTWITELXNOSTI y MOVNO S^ITATX LEWONORMIROWANNYM, NO \TO NE IMEET NIKAKOGO ZNA^ENIQ). tAKIM OBRAZOM, w = uv = u(yxn) = (uy)xn I MY SNOWA POPALI W PERWYJ SLU^AJ.

3.pROWERKA ASSOCIATIWNOSTI PO TABLICE k\LI. pROWERKA ASSOCIATIWNOSTI OPERACII PO EE TABLICE k\LI ZANQTIE ^REZWY^AJNO NEBLAGODARNOE. fAKTI^ESKI ONO SWODITSQ K SLEDU@]EMU. oBOZNA^IM OPERACI@, ASSOCIATIWNOSTX KOTOROJ MY HOTIM PROWERITX, UMNOVENIEM. fIKSIRUEM \LEMENT z MNOVESTWA X I WWEDEM NA X DWE PROIZWODNYE OPERACII: x¤z y = (xz)y I x±z y = x(zy). fAKTI^ESKI PROWERKA ASSOCIATIWNOSTI SWODITSQ K PROWERKE SOWPADENIQ TABLIC ¤z I ±z DLQ WSEH \LEMENTOW z 2 X, A \TO ^UDOWI]NO UTOMITELXNOE DELO DAVE DLQ SLU^AQ, KOGDA X SODERVIT 4

ILI 5 \LEMENTOW (SM., NAPRIMER, a.kLIFFORD, g.pRESTON “aLGEBRAI^ESKAQ TEORIQ POLUGRUPP”, 1972, x 1.2). w DEJSTWITELXNOSTI GORAZDO BOLEE INTELLIGENTNYM162 SPOSOBOM PROWERKI ASSOCIATIWNOSTI QWLQETSQ POSTROENIE PREDSTAWLENIJ, T.E. WLOVENIE RASSMATRIWAEMOJ SISTEMY W KAKU@-NIBUDX DRUGU@ SISTEMU (OTOBRAVENIQ, OTNO[ENIQ, MATRICY), ASSOCIATIWNOSTX KOTOROJ IZWESTNA IZ OB]IH SOOBRAVENIJ.

4.aSSOCIATIWNYE TROJKI. dAVE ESLI OPERACIQ NA MNOVESTWE X NEASSOCIATIWNA, MOGUT NAJTISX TROJKI x; y; z 2 X TAKIE, ^TO (xy)z = x(yz). tAKIE TROJKI OBY^NO NAZYWA@TSQ ASSOCIATIWNYMI, HOTQ BYLO BY PRAWILXNEE NAZYWATX IH

ASSOCIIRU@]IMI.

zADA^A. nAJTI WSE ASSOCIIRU@]IE TROJKI NATURALXNYH ^ISEL OTNOSITELXNO POTENCIROWANIQ: (mn)p = m(np).

oTWET. wOT WSE TAKIE TROJKI: (1; n; p), (m; n; 1) I (m; 2; 2).

a WOT BOLEE \KZOTI^ESKIJ I GORAZDO BOLEE TRUDNYJ PRIMER. rASSMOTRIM BI-

n	KAK BINARNU@ OPERACI@ NA N. dLQ KAKIH TROEK
NOMIALXNYJ KO\FFICIENT m
NATURALXNYH ^ISEL IMEET MESTO RAWENSTWO						1?
0	m 1		=	0	m
B	n	C		B	n	C
@	l	A		@	l	A

|TOT KURXEZNYJ WOPROS RASSMATRIWAL sOLOMON gOLOMB163. oN NA[EL PQTX TIPOW TAKIH TROEK (l; m; n), A IMENNO,

(1)(1; m; n), DLQ WSEH m; n;

(2)( mn ; m; n), PRI l > m;

(3)(l; m; n), PRI m > l; n;

(4)(l; l; l + 1), DLQ WSEH l > 1;

(5)(l; m; m), DLQ WSEH 1 < l < m ¡ 1.

sKOREE WSEGO, NE SU]ESTWUET NI ODNOJ ASSOCIIRU@]EJ TROJKI (l; m; n), DLQ KOTOROJ 1 < l < m < n, NO \TO NE DOKAZANO.

162Marked or characterised by intelligence.

163S.W.Golomb, Iterated binomial coe cients, – Amer. Math. Monthly, 1980, November, p.719–727.

366	NIKOLAJ WAWILOW

x 2. ~ISLA kATALANA I ^ISLA rODRIGESA

There is nothing new under the Sun, but there are a lot of old things we do not know.

Ambrose Bierce

eSTESTWENNO WOZNIKAET WOPROS, SKOLXKO PROIZWEDENIJ MOVNO SOSTAWITX IZ n + 1 \LEMENTOW, NE PREDPOLAGAQ, ^TO ZAKON KOMPOZICII ASSOCIATIWEN.

1. ~ISLA kATALANA. rASSTANOWKA n ¡ 1 PAR SKOBOK, PRI KOTOROJ NEASSOCIATIWNOE PROIZWEDENIE x1 : : : xn+1 STANOWITSQ ODNOZNA^NO OPREDELENNYM, NAZYWAETSQ PRAWILXNOJ. qSNO, ^TO DLQ 2 MNOVITELEJ IMEETSQ EDINSTWENNAQ PRAWILXNAQ RASSTANOWKA SKOBOK, A IMENNO, x1x2, DLQ 3 MNOVITELEJ TAKIH RASSTANOWOK DWE, A IMEN-

NO, (x1x2)x3 I x1(x2x3), A DLQ 4 MNOVITELEJ IH UVE PQTX, A IMENNO, ((x1x2)x3)x4, (x1(x2x3))x4, (x1x2)(x3x4), x1((x2x3)x4), x1(x2(x3x4)). ~ITATELX BEZ TRUDA UBE-

DITSQ, ^TO IMEETSQ 14 RAZLI^NYH PRAWILXNYH RASSTANOWOK SKOBOK DLQ 5 MNOVITELEJ I 42 DLQ 6 MNOVITELEJ. a KAKOW OTWET W OB]EM SLU^AE? sLEDU@]IJ REZULXTAT BYL DOKAZAN W 1838 GODU kATALANOM164.

tEOREMA. kOLI^ESTWO NEASSOCIATIWNYH PROIZWEDENIJ, KOTORYE MOVNO OBRA- ZOWATX IZ n + 1 SOMNOVITELQ W FIKSIROWANNOM PORQDKE, RAWNO n-MU ^ISLU kA-

TALANA	n	=	2n + 1		n	:
Cn = n + 1
1	2n		1		2n + 1

~ISLA Cn NAZYWA@TSQ ^ISLAMI kATALANA, ONI WOZNIKA@T W DESQTKAH SAMYH RAZLI^NYH ZADA^ ALGEBRY, TEORII ^ISEL, KOMBINATORIKI I KOMBINATORNOJ GEOMETRII. mY DOKAVEM \TU TEOREMU DWUMQ SPOSOBAMI, ^EREZ REKURRENTNYE SOOTNO[ENIQ I NEPOSREDSTWENNO.

w Mathematica ^ISLA kATALANA OPREDELQ@TSQ W PAKETE ‘kOMBINATORNYE FUNKCII’, KOTORYJ PODGRUVAETSQ KOMANDOJ

<<DiscreteMath`CombinatorialFunctions`:

pOSLE \TOGO OCENKA WYRAVENIQ CatalanNumber[n] WOZWRA]AET n-E ^ISLO kATALANA. uKAVEM NESKOLXKO PERWYH ^LENOW \TOJ POSLEDOWATELXNOSTI: C0 = 1, C1 = 1, C2 =

2, C3 = 5, C4 = 14, C5 = 42, C6 = 132, C7 = 429, C8 = 1430, C9 = 4862, C10 = 16796, C11 = 58786, C12 = 208012.

2. iNDUKCIONNOE DOKAZATELXSTWO. dLQ PEREHODA K ZAPISI lUKASEWI^A I PROWEDENIQ INDUKCII PO n NAM BUDET UDOBNO POSTAWITX DLQ KAVDOGO PROIZWEDENIQ E]E ODNU PARU SKOBOK, A IMENNO, SKOBKI WOKRUG WSEGO PROIZWEDENIQ. tAKIM OBRAZOM, MY S^ITAEM, ^TO W PRAWILXNOJ RASSTANOWKE SKOBOK W PROIZWEDENII n + 1 SOMNOVITELQ n PAR SKOBOK. nAPRIMER, DLQ n = 3 MY TEPERX ZAPI[EM PROIZWEDENIQ TAK:

(((x1x2)x3)x4), ((x1(x2x3))x4), ((x1x2)(x3x4)), (x1((x2x3)x4)), (x1(x2(x3x4))). tE-

PERX, ^TOBY PEREJTI K ZAPISI lUKASEWI^A, DOSTATO^NO UBRATX WSE PRAWYE, A, ^TOBY PEREJTI K OBRATNOJ ZAPISI lUKASEWI^A, – WSE LEWYE SKOBKI I ZAMENITX OSTAW[IESQ SKOBKI NA ZNAK OPERACII. kROME TOGO, POSKOLXKU NAS INTERESUET TOLXKO RASSTANOWKA SKOBOK, A NE SAMI OPERANDY, MY MOVEM OBOZNA^ITX WSE OPERANDY ^EREZ x.

164Eug`ene–Charles Catalan (1814-1894) BELXGIJSKIJ MATEMATIK

WOZMOVNYH SLOW, W KOTORYE BUKWA x WHO-

MNOVESTWA, OTOBRAVENIQ, OTNO[ENIQ: not entirely naive

367

nAPRIMER, ESLI OBOZNA^ITX OPERACI@ ^EREZ f, TO TE VE SAMYE PROIZWEDENIQ ZA-

PI[UTSQ KAK fffxxxx, ffxfxxx, ffxxfxx, fxffxxx, fxfxfxx DLQ ZAPISI lUKASEWI^A I KAK xxfxfxf, xxxffxf, xxfxxff, xxxfxff, xxxxfff DLQ OBRATNOJ ZAPISI lUKASEWI^A. w OBRATNOJ ZAPISI lUKASEWI^A PRAWILXNAQ RASSTANOWKA SKOBOK W PROIZWEDENII n + 1 MNOVITELQ SOOTWETSTWUET TAKOMU SLOWU DLINY 2n + 1 W ALFAWITE x; f, ^TO KAVDYJ NA^ALXNYJ FRAGMENT \TOGO SLOWA SODERVIT BOLX[E BUKW x, ^EM BUKW f. tAKIE SLOWA BUDUT NAZYWATXSQ PRAWILXNYMI (well-formed).

dOKAZATELXSTWO. wSEGO IMEETSQ 2n + 1 n

DIT n + 1 RAZ, A BUKWA f WHODIT n RAZ. pUSTX w – L@BOE TAKOE SLOWO. mY UTWERVDAEM, ^TO IMEETSQ ROWNO ODNA CIKLI^ESKAQ PERESTANOWKA SLOWA w QWLQ@]AQSQ PRAWILXNYM SLOWOM. tAKIM OBRAZOM, ^ISLO RAZLI^NYH RASSTANOWOK SKOBOK RAWNO

	1	2n + 1	, KAK I UTWERVDALOSX.
	n + 1	n
	|TO DOKAZYWAETSQ			INDUKCIEJ PO n. w SAMOM DELE, DLQ n = 1 \TO, O^EWIDNO, TAK:

IZ SLOW xxf, xfx, fxx ROWNO ODNO, A IMENNO xxf, QWLQETSQ PRAWILXNYM. pUSTX TEPERX w — SLOWO DLINY n > 2. pOKAVEM, PREVDE WSEGO, ^TO SU]ESTWUET PRAWILXNAQ CIKLI^ESKAQ PERESTANOWKA SLOWA. w SAMOM DELE, SAMO SLOWO w ILI, ESLI w = f : : : fx : : : x, TO SLOWO RotateRight[w] SODERVIT FRAGMENT WIDA xf. wY^ERKNEM PERWOE SLEWA WHOVDENIE xf (W SLU^AE w = f : : : fx : : : x WY^ERKNEM SAMOE LEWOE f I SAMOE PRAWOE x). mY POLU^AEM SLOWO z DLINY 2n ¡1, W KOTOROE x WHODIT n RAZ, A f WHODIT n ¡ 1 RAZ. pO INDUKCIONNOMU PREDPOLOVENI@ SU]ESTWUET CIKLI^ESKAQ PERESTANOWKA SLOWA z, QWLQ@]AQSQ PRAWILXNYM SLOWOM. wRISOWYWAQ W \TU PERESTANOWKU FRAGMENT xf NA TO MESTO, OTKUDA ON BYL WY^ERKNUT, MY POLU^AEM PRAWILXNU@ CIKLI^ESKU@ PERESTANOWKU ISHODNOGO SLOWA. nAPRIMER, DLQ w = fxxffxx, WY^ERKIWANIE PERWOGO FRAGMENTA xf DAET NAM SLOWO z = fx¡fxx = fxfxx. pRAWILXNOJ CIKLI^ESKOJ PERESTANOWKOJ \TOGO SLOWA QWLQETSQ xxfxf = xxfx¡f. sNOWA WRISOWYWAQ S@DA xf MY POLU^AEM SLOWO xxfxxff, QWLQ@]EESQ PRAWILXNOJ CIKLI- ^ESKOJ PERESTANOWKOJ ISHODNOGO SLOWA w.

dLQ DOKAZATELXSTWA EDINSTWENNOSTI ZAMETIM, ^TO PRAWILXNAQ CIKLI^ESKAQ PERESTANOWKA SLOWA w NE MOVET NA^INATXSQ NI S BUKWY x, NI S BUKWY f WY^ERKNUTOJ PARY. pO\TOMU WY^ERKIWANIE L@BOGO FRAGMENTA xf IZ PRAWILXNOGO SLOWA SNOWA DAET PRAWILXNOE SLOWO. eSLI BY U w BYLO DWE PRAWILXNYH CIKLI^ESKIH PERESTANOWKI, TO WY^ERKIWANIE ODNOGO I TOGO VE FRAGMENTA xf IZ KAVDOGO IZ NIH PRIWODILO BY K DWUM PRAWILXNYM CIKLI^ESKIM PERESTANOWKAM SLOWA z DLINY 2n ¡ 1, ^TO NEWOZMOVNO PO INDUKCIONNOMU PREDPOLOVENI@.

kOMMENTARIJ. |TO DOKAZATELXSTWO QWLQETSQ PARAFRAZOM DOKAZATELXSTWA IZ STATXI d\WIDA sINGMASTERA165, KOTORYJ, W SWO@ O^EREDX, OTME^AET, ^TO \TO SPECIALIZACIQ IDEI zILXBERGERA. pO SU]ESTWU TO VE SAMOE, NO ^UTX SLOVNEE OFORMLENNOE RASSUVDENIE ^UTX BOLEE OB]EGO FAKTA PRIWODITSQ W166 SO SSYLKOJ NA RABOTU dVORDVA rENI 1960 GODA. w DEJSTWITELXNOSTI, NAJTI PERWOISTO^NIK ZATRUDNITELXNO, TAK KAK \TO RASSUVDENIE DOLVNO BYTX HORO[O IZWESTNO SPECIALISTAM W OBLASTI MATEMATI^ESKOJ STATISTIKI. dELO W TOM, ^TO ^ISLA kATALANA PREDSTAWLQ@T SOBOJ

165D.Singmaster, An elementary evaluation of the Catalan numbers, — Amer. Math. Monthly, ???, p.366–368.

166r.gREH\M, d.kNUT, o.pATA[NIK, kONKRETNAQ MATEMATIKA, m., mIR, 1988, c.1–703, SM. STR.393–395.

368	NIKOLAJ WAWILOW

OTWET NA ^ASTNYJ SLU^AJ PROBLEMY bERTRANA167. a IMENNO, PROBLEMA bERTRANA (Bertrand ballot problem) SOSTOIT W SLEDU@]EM. pREDPOLOVIM, ^TO KANDIDATY POLU^A@T m I n GOLOSOW, SOOTWETSTWENNO, PRI^EM m > n, A GOLOSA S^ITA@TSQ PO ODNOMU. kAKOWA WEROQTNOSTX TOGO, ^TO POBEDITELX OKAZYWAETSQ WPEREDI NA KAVDOM \TAPE GOLOSOWANIQ? pRIWEDENNOE WY[E RASSUVDENIE RE[AET \TU PROBLEMU W ^ASTNOM SLU^AE m = n + 1. mY DOKAZALI, ^TO WEROQTNOSTX W \TOM SLU^AE RAWNA 1=(2n + 1). sOWER[ENNO ANALOGI^NOE RASSUVDENIE hILTONA I pEDERSEN168, SWQZANNOE S RASSTANOWKOJ SKOBOK W PROIZWEDENIQH WYS[IH ARNOSTEJ, POKAZYWAET, ^TO W OB]EM SLU^AE WEROQTNOSTX RAWNA (m ¡ n)=(m + n).

3. rEKURRENTNOE SOOTNO[ENIE DLQ ^ISEL kATALANA. w SAMOM DELE, PRI L@BOM n ¸ 2 ROWNO ODNO UMNOVENIE LEVIT WNE WSEH SKOBOK, PUSTX, SKAVEM, \TO UMNOVENIE MEVDU xm I xm+1, GDE m = 1; : : : ; n ¡ 1. tOGDA, TAK KAK SU]ESTWUET Cm¡1 SPOSOBOW RASSTAWITX SKOBKI W PROIZWEDENII PERWYH m MNOVITELEJ I Cn¡m SPOSOB RASSTAWITX SKOBKI W PROIZWEDENII POSLEDNIH n ¡ m MNOVITELEJ, TO

sn = s0sn¡1 + s1sn¡2 + : : : + sn¡1s0:

kAK HORO[O IZWESTNO, \TIM REKURRENTNYM SOOTNO[ENIEM OPREDELQETSQ POSLEDOWATELXNOSTX ^ISEL kATALANA, QWNU@ FORMULU DLQ KOTORYH LEGKO DOKAZATX, NAPRIMER, PRI POMO]I METODA PROIZWODQ]IH FUNKCIJ, SM.169;170;171;172. oBOZNA^IM ^EREZ f(x) PROIZWODQ]U@ FUNKCI@ DLQ ^ISEL kATALANA f = f(x) = C0 + C1x + C2x2 + : : : . rEKURRENTNOE SOOTNO[ENIE POKAZYWAET, ^TO xf2 = f ¡ 1. rE[AQ KWADRATNOE URAWNENIE xf2 ¡ f + 1 = 0, POLU^AEM

p

f(x) = 1 § 1 ¡ 4x : 2x

oDNAKO WYBOR ZNAKA + PERED KORNEM NEWOZMOVEN, TAK KAK ON PRIWODIT K RQDU lORANA,pNA^INA@]EMUSQ S 1=x. pO\TOMU f(x) = (1 ¡ p1 ¡ 4x)=2x. rASKLADYWAQ TEPERX 1 ¡ 4x PO FORMULE BINOMA nX@TONA, POLU^AEM ISKOMU@ FORMULU.

rASSTANOWKA SKOBOK W PROIZWEDENII x1; : : : ; xn NAZYWAETSQ WLOVENNOJ (nested), ESLI WSE OTKRYWA@]IE SKOBKI STOQT PERED ZAKRYWA@]IMI, T.E. ESLI POSLE STIRANIQ WSEH xi‘H OSTAETSQ (: : : () : : : ). nAPRIMER, RASSTANOWKA SKOBOK W PROIZWEDENII (x1x2)(x3x4) NE QWLQETSQ WLOVENNOJ, A WSE OSTALXNYE PRAWILXNYE RASSTANOWKI SKOBOK W PROIZWEDENII ^ETYREH \LEMENTOW WLOVENNYE.

zADA^A. sKOLXKO RASSTANOWOK SKOBOK QWLQ@TSQ WLOVENNYMI W USLOWIQH PREDYDU- ]EJ ZADA^I?

167w.fELLER, wWEDENIE W TEORI@ WEROQTNOSTEJ I EE PRILOVENIQ, T.I, m., mIR, 1967, S.1–498, T.I, gL.3, xx 1 — 2, ^ISLA kATALANA, PRAWDA BEZ NAZWANIQ, POQWLQ@TSQ W KNIGE fELLERA NA STRANICAH 86–88.

168P.Hilton, J.Pedersen, Catalan numbers, their generalization and their uses. — Mathematical Intelligencer, 1991, vol.13, N.2, p.64–75.

169r.gREH\M, d.kNUT, o.pATA[NIK, kONKRETNAQ MATEMATIKA, m., mIR, 1988, c.1–703, SM. STR.391–393

170s.k.lANDO, lEKCII O PROIZWODQ]IH FUNKCIQH, m., mcnmo, 2002, 143S. 171r.sT\NLI, pERE^ISLITELXNAQ KOMBINATORIKA, m., mIR, 1990

172q.gULXDEN, d.dVEKSON, pERE^ISLITELXNAQ KOMBINATORIKA, m., nAUKA, 1990

MNOVESTWA, OTOBRAVENIQ, OTNO[ENIQ: not entirely naive

369

4. ~ISLA rODRIGESA. w DEJSTWITELXNOSTI, GORAZDO BOLEE PROSTOJ PODHOD K WY- ^ISLENI@ ^ISEL kATALANA BYL PREDLOVEN W TOM VE SAMOM 1838 GODU o.rODRIGE-

SOM173 W EGO STATXE “Sur le nombre des mani`eres d’e ectuer un produit de n facteurs”.

tEOREMA. kOLI^ESTWO NEASSOCIATIWNYH PROIZWEDENIJ, KOTORYE MOVNO OBRA- ZOWATX IZ n + 1 SOMNOVITELQ W PROIZWOLXNOM PORQDKE, RAWNO n-MU ^ISLU rOD-

RIGESA

Rn = 2n ¢ 3 ¢ 5 ¢ : : : ¢ (2n ¡ 1):

dOKAZATELXSTWO. qSNO, ^TO SU]ESTWUET ROWNO ODNO PROIZWEDENIE ODNOGO MNOVITELQ, TAK ^TO R0 = 1. eSLI UVE IMEETSQ KAKOE-TO PROIZWEDENIE n MNOVITELEJ, TO n+ 1-J MNOVITELX MOVNO DORISOWATX SLEWA ILI SPRAWA OT L@BOGO IZ n MNOVITELEJ, LIBO SLEWA ILI SPRAWA OT L@BOGO IZ n ¡1 ^ASTI^NYH PROIZWEDENIJ. nAPRIMER, DOPISYWAQ z, IZ (xy) MOVNO IZGOTOWITX ((zx)y), ((xz)y), (x(zy)), (x(yz)), A TAKVE (z(xy))

I ((xy)z). dOPISYWAQ w K ((xy)z) POLU^AEM (((wx)y)z), (((xw)y)z), ((x(wy))z), ((x(yw))z), ((xy)(wz)), ((xy)(zw)), A TAKVE (w((xy)z)), (((xy)z)w), ((w(xy))z) I

(((xy)w)z). tAKIM OBRAZOM, KOLI^ESTWO PROIZWEDENIJ n + 1 MNOVITELQ, SODERVA- ]IH FIKSIROWANNOE PROIZWEDENIE n MNOVITELEJ, WSEGDA RAWNO 2(2n ¡ 1). |TO DAET NAM REKURRENTNOE SOOTNO[ENIE Rn = 2(2n ¡ 1)Rn¡1.

tEPERX MY MOVEM WY^ISLITX Rn = rodrigues[n] POSREDSTWOM

rodrigues[0]=1; rodrigues[n ]:=2*(2n-1)*rodrigues[n-1].

uKAVEM NESKOLXKO PERWYH ^LENOW \TOJ POSLEDOWATELXNOSTI:			R0 =	1, R1 = 2,
R2	= 12, R3 =	120, R4 = 1680, R5 = 30240, R6 = 665280, R7		= 17297280,
R8	= 518918400,	R9 = 17643225600, R10 = 670442572800, R11	= 28158588057600,

R12 = 1295295050649600.

oDNAKO SOWER[ENNO QSNO, ^TO ^ISLA kATALANA I ^ISLA rODRIGESA SWQZANY MEVDU SOBOJ SLEDU@]IM OBRAZOM: Cn = Rn=(n + 1)!. tAKIM OBRAZOM, MY POLU^ILI E]E ODIN, ZNA^ITELXNO BOLEE PROSTOJ SPOSOB WY^ISLENIQ ^ISEL kATALANA.

x 4. kOMMUTATIWNOSTX

And you know why four plus minus one Plus ten is fourteen minus one?

’Cause addition is commutative, right? Tom Lehrer

sLEDU@]IM PO ZNA^ENI@ TOVDESTWOM QWLQETSQ TOVDESTWO KOMMUTATIWNOSTI.

1. kOMMUTATIWNOSTX. sLEDU@]EE TOVDESTWO TOVE IZWESTNO NAM IZ NA^ALXNOJ [KOLY, GDE ONO OBY^NO NAZYWAETSQ PEREMESTITELXNYM ZAKONOM, TERMIN ‘KOMMUTATIWNOSTX’ BYL WWEDEN sERWUA W 1815 GODU.

173bOLEE IZWESTNYM W RUSSKOJ LITERATURE PO KOMBINATORIKE POD FRANCUZSKIM PSEWDONIMOM rODRIG (‘FORMULA rODRIGA’) — NU DA, KONE^NO, dON kI[OT, traduit librement de l’espagnol!

370	NIKOLAJ WAWILOW

oPREDELENIE. oPERACIQ ¤ NA MNOVESTWE X NAZYWAETSQ KOMMUTATIWNOJ, ESLI x ¤ y = y ¤ x DLQ L@BYH x; y 2 X

w PREFIKSNOJ ZAPISI \TO TOVDESTWO PRINIMAET WID f(x; y) = f(y; x). pRIMERY KOMMUTATIWNYH OPERACIJ:

²cLOVENIE I UMNOVENIE WE]ESTWENNYH I KOMPLEKSNYH ^ISEL,

²cLOVENIE I UMNOVENIE KARDINALXNYH ^ISEL,

²SLOVENIE I UMNOVENIE MNOGO^LENOW,

²SLOVENIE WEKTOROW I MATRIC,

²OB_EDINENIE I PERESE^ENIE MNOVESTW,

²WZQTIE SUPREMUMA I INFIMUMA.

pRIMERY NEKOMMUTATIWNYH OPERACIJ:

²SLOVENIE ORDINALXNYH ^ISEL: 1 + ! = ! =6 ! + 1,

²WOZWEDENIE W STEPENX: xy =6 yx,

²KOMPOZICIQ FUNKCIJ ILI OTNO[ENIJ,

²KOMPOZICIQ MNOGO^LENOW,

²WEKTORNOE UMNOVENIE WEKTOROW,

²UMNOVENIE KWATERNIONOW,

²UMNOVENIE MATRIC.

wOOB]E, HARAKTERNOJ ^ERTOJ MATEMATIKI NA^INAQ S XIX WEKA QWLQETSQ NEUKLONNYJ OTKAZ OT KOMMUTATIWNOSTI. sKORO MY POZNAKOMIMSQ SO MNOGIMI DRUGIMI OB_EKTAMI, UMNOVENIE KOTORYH NEKOMMUTATIWNO: OKTAWAMI, POLIWEKTORAMI I T.D. kONE^NO, SAMYMI PROSTYMI PRIMERAMI NEKOMMUTATIWNYH ZAKONOW KOMPOZICII QWLQ@TSQ WY^ITANIE I DELENIE: x ¡ y 6= y ¡ x, x=y 6= y=x, NO MY UVE DOGOWORILISX NE RASSMATRIWATX IH W KA^ESTWE SAMOSTOQTELXNYH OPERACIJ.

2. oBOB]ENNAQ KOMMUTATIWNOSTX. oKAZYWAETSQ, ESLI OPERACIQ ASSOCIATIWNA I KOMMUTATIWNA, TO KAK RASSTANOWKA SKOBOK, TAK I PORQDOK SOMNOVITELEJ W PROIZWEDENII L@BOGO KONE^NOGO ^ISLA \LEMENTOW NE IME@T ZNA^ENIQ. w SLEDU@]EM REZULXTATE Sn OBOZNA^AET SIMMETRI^ESKU@ GRUPPU, T.E. MNOVESTWO WSEH BIEKCIJ n = f1; : : : ; ng NA SEBQ OTNOSITELXNO KOMPOZICII, SM. gLAWU II.

tEOREMA. pREDPOLOVIM, ^TO OPERACIQ W X ASSOCIATIWNA I KOMMU- TATIWNA. tOGDA DLQ L@BYH x1; : : : ; xn 2 X I L@BOJ PERESTANOWKI ¾ 2 Sn IMEET MESTO RAWENSTWO

x¾(1) : : : x¾(n) = x1 : : : xn: