Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/materials/spivak-04-1.pdf Дата изменения: Wed Mar 30 20:59:46 2005 Дата индексирования: Sat Dec 22 17:39:10 2007 Кодировка: Поисковые слова: m 2

.
. , . n - .

­­­­­­ ­

, . , n - , n . n = 3 : (. 1). n = 4 , (. 2). n = 5 -- , 5 (. 3). n = 6 : 14 (. 4). , ? ? , , . 5 (. 5). 14, . . . , 2 · 2 = 4 . , 14 +5+2 · 2 + 5 + 14 = 42 . , 42 + 14 + 2 · 5+ 5 · 2 + 14 + 42 = 132 . 132 + 42 + 2 · 14 + 5 · 5+14 · 2 + 42 + 132 = 429 , -- 429 + 132 + 2 · 42 + 5 · 14 + 14 · 5+42 · 2 + 132 + 429 = 1430 . . : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, ... 1


1. 18 . , ? ( 6 ,, , , 2, 4 6 .) 1430. . , , . 2. 7 6 , , , .) 10 ? 42. 3. 8 5 6-, , (, 0) , . 14-? 1430. 4. 9 5 , , , . , ? 429. 5. 10 5 , , , , , , ( , ), , -- . 7 ? 132. 6. 11 5 , , , , . ( ) . 10 ? 4862.


-- -- . abc : (ab)c a(bc) . (, , . -- !) abcd : ((ab)c)d , (a(bc))d , a((bc)d), a(b(cd)) (ab)(cd) . abcde -- .
. , .
)

2


, . , 5 a(bcde) , 2 (ab)(cde) , 2 (abc)(de) 5 (abcd)e . , ) Cn -- n . ( ) . , . x1 x2 ··· xn : x1 x2 ··· xn = (x1 ··· xr ) · (xr
+1

··· xn ).

r Cr , n - r -- Cn-r . , Cn = C1 Cn
-1

+ C2 Cn

-2

+ ··· + Cn

-1

C1 .

, , , C10 , , -- ; , C10 = 4862 . 1 1 2 5 14 42 132 429 1430 1430 429 132 42 14 5 2 1 1 , , , . , n - n - 2 Cn-1 . -- - ( , ) ? ! , 1961 , (n + 1) - , , <> , - , ( 12 13 n = 2 3 , 14 429 n = 8 ).
7. Cn , n , , n = 2k , k -- . . . , , C2n+1 , n > 0 . C2n , Cn .
)

(1814-1894) -- .

3



- , . . ? -, , . -, . (, )( ((())))( -- .) , , . . : (). -- : ()() (()). -- : ()()(), ()(()), (())(), (()()) ((())). , ,-- . , , , . : . (, 0 .) , , 14 . , , 5 . -- , . , , , 2 · 2 = 4 . 14 +5+2 · 2 + 5 + 14 = 42 . , ?
8. ((((ab)(cd))(ef))(gh)) . , : (((())())())(). , . ( 15 16 .) , . (ab) () ((ab)c) (()) (((ab)c)d) ((())) ((a(bc))d) (()()) (a(bc)) ()() (a(b(cd))) ()()() ((ab)(cd)) (())() (a((bc)d)) ()(())


(. 17) , < , > ( -- ). . . , . , (. 18). -- ! , ?

4


. -, , 18 , , : 275 + 110 + 35 + 8 + 1 = 429. (!) -, , , , : 14 + 28 + 48 + 75 = 165. ( : 5 !) , : 14 +28 + 48 +75 = 42 +48 + 75 = 90+75 = 165. , - , . , - , , ? . -, -- -. , . , . -- -- . ( 19, 20 21 1, 2 3 .) , ; , .
9. , a1-h8? ( 22, 23 24 2 в 2 , 3 в 3 4 в 4 .) 10. 1 2n 2 n , ? . n , , -- .


. ( < >, TeX, < > < >, ) , n , 5


. , n = 1 . n = 2 : 21, 12. n = 3 123, (. 25). n = 4 , 26. ( ! , .) : 26 1, 3, 5 5 . C5 = 14 , . , : n , n k - , , k - n - , 18. . . k - 1 -- n a b , a < b a , b , b , n , a < b < n . n c . n c ? , ( 26!). , n . , n , c , n c . -- . , c - d > c , n c d . , c + 1 n - 1 n . , , n , . , n - 1, n - 2, ... , c + 1 . n -- c , c , n . n = 9 , k = 4 . . 9 ( ) 275 -- 9 , 9 4- . , 9 , . . , c = 1 . c = 2 , 3 8 , . -- c = 3 , 4 5. c = 6 : 87 96 . 7, 8 9, 6 , ( . ) 42 . , c = 7 8 97 . 6


8 9, 7 ; 90 . , c = 8 9, . 8 165 . : 275 + (42 + 90 + 165) = = 297 + 275 = 572 .

n
15 16 . 27 9- ) 9 . , Cn n ) , ) 1 3. ( 28, 29 30 3, 4 5 .) , . , , , 3 -- (. 31). , , ( !). , , . , 31 ((()))()()(), (((ab)c)(d(e(fg)))) .

n
1964 , n Cn . n - 1 ; . (. 32): -- , ( ) , . -- -- n , 1 3, n . n = 2 , 3 4 33, 34 35 . , ( ) .
11. , , , , , : , ; , , , -- .
) -- . <> , . <> -- , , -- . 27 . ) -- , ; 27 . ) ( ) -- .

7


12. 36, 37 38 , 3, , , 2, 3 4. , n - 1 Cn . . , n , 1 3, .


n - . , n n - ( 39, 40 41 n = 2 , 3 4). , 15 ( -- ). 14- 190 899 322 ( 14- ). , 1970 , , , . , -- !


, . . . . < > . . . , -- , 5 -- . , n - · , -- n - 1 (. 43); · 44 n - 1 , ; · ( , , , -- ), , n - 1 ( , n - 2 ) (. 45); · , (2n; 0) , ( ) 2 (. 46); · , (2n; 0) , <-> (. 47);

8


· n (. 48); · 4(2n - 1) (. 49); · 2n (. 50); · a1 6 a2 6 ... 6 an-1 , ak 6 k , 1 6 k < n , , n = 4 1 6 1 6 1, 1 6 1 6 2, 1 6 1 6 3, 1 6 2 6 2, 1 6 2 6 3; · a1 < a2 < ... < an-2 , ak 6 2k , 1 6 k < n - 1 ( n = 4 1 < 2, 1 < 3, 1 < 4, 2 < 3, 2 < 4); · n - 1 , i < j < k , (j) < (k) < (i) ( n = 4 123, 132, 213, 231 321); · n - 1 , (. 51); , S , S() = S(ukv) = S(u)S(v)k , u v -- , k ( n = 4 123, 132, 213, 312 321); · n - 1 , ( , , . 52, n = 4 123, 132, 213, 231 312); , , ( ). x1 , x2 , ... , xn A1 (1; x1 ), A2 (2; x2 ), ... , An (n; xn ) , , A1 A2 ... An , Cn /(n!)2 . . n , . , , . , , а # n , Cn /(n - 1)!!2 .


-1 Cn = n=1 Ck Cn-k n - k Cn C1 , C2 , ... , Cn-1 . , Cn n . : 1) ; 2) ; 3) .



9



, , - . , , ((1 - 2) + (3 + 4)) : ((5 - 6) · 7 - 8 · 9). , , : . 1 - 2 12- . , a b ab . (1 - 2) + (3 + 4) 12 - 34 + + , 12 - 34 + +56 - 7 · 89 ·- : . : . , , ! , , (!) . . a p : , a ; U V u v , U · V uvp . H,

ab (ab)c a(bc) ((ab)c)d - ((aap)c)d a(b(cd)) (a(bc))(de)

- - - - - -

aap, aaapp, aaapp, (aapap)d - aapapap, aaaappp, aaappaapp.

, n a n - 1 p . : , ppaaa apaap . . H . , :











, ak+1 ... an a1 ... ak a1 ... ak ak+1 ... an . , A -- n a n - 1 p , A . 10


n . A , p , . , , . A -- -- aap . a . , n - 1 a n - 2 p , . ( 53 n = 9 .) -1 Cn . 2n - 1 Cnn-1 2 -1 n - 1 p . Cnn-1 2n - 1, 2 : 1 Cn-1 = (2n - 2)! . Cn = 2n - 1 2n-1 (n - 1)!n!
13. Cn+1 =
4n-2 n+1

Cn .


, Cn n - 1 n - 1 , . <(> < +1 >, <)> < -1 >, , Cn n - 1 n - 1 , . ( 1 , 2 , ... , n ), i = ±1 , , , i - (i = 1,... ,n) i , (i - 1, 1 + + ··· + i-1 ) (i, 1 + ··· + i-1 + i ). Nn,s , (n, s) . , ( 1 ,... , n ) p q , s = p - q . p i p n = p + q , Np+q,p-q = Cp+q . A B -- , B , B -- , B (. ??). . A B , , , B . : T -- , , AT . 1878 . 1887 . : P p , Q q , , P Q , p-q . p+q s , n s -- , n Nn,s (n, s) , , , . . , (1, 1) (n, s), , Nn
-1,s-1

- Nn

-1,s+1

= Cp+q

p-1 -1

- Cp+q

p

-1

.

11


, Nn,s p-q . p+q , Cn , p = n , q = n - 1.


-- . , <> . 1, 1, 2, 5, 14, 42, 132, ... -- f(x) = 1 = x +2x2 +5x3 +14x4 +42x5 + 132x6 + 429x7 +1430x8 + ... , x : , . f(x) · f(x) = C2 x2 +(C1 C2 + C2 C1 )x3 +(C1 C3 + C2 C2 + C3 C1 )x4 + ... + 1 +(C1 Cn f2 (x) = -x + f(x). (!) f(x), 1 - 1 - 4x f(x) = . 2 ( , f(x) |x| < 1 . , .) 4 , f(x) . x , ( 1 )(- 1 ) ··· ( 2 Cn = - 1 2 2 n!
3-2n 2 -1

+ C2 Cn

-2

+ ... + Cn

-1

C1 )xn + ... ,

)

(-4)n .
(2n-2)! n!(n-1)!

, Cn =
14.

.
n n=1

F(x) = 1 + x +2x2 +3x3 +5x4 +8x5 +13x6 +21x7 + ... =

xn-1 ,

n - , 1 = 2 = 1 n+2 = n+1 + n .

12


, F(x) · (1 - x - x2 ) = 1 . F(x) = 2 -1 =# x +x-1 x +
1+ 2

-# а1 5! ! x +

1- 5 2

# 1- 1 1 а= ! ! 5 x + 1+ 5 x+ 1 2 а ! ! ! !. ! ! !

1 1-x-x2

: а ! ! ! != ! ! !

-5 2

# 5+1 5-1 1 2 2 = + - 5 1+ x 52 1 1 - x 5+1 2



# аk # # 5+ ! 5 - 1 1 - 5! 1 ! + 5+ 1 ! F(x) = x ! x 2 2 2 2 5 k=0 k=0 ## # аk+1 аk+1 а ! ! ! ! 5+ 1 ! 1 - 5! ! 1 ! ! k !. ! ! x - ! = ! ! ! 2 2 5 k=0 :
n

1 1-t

= 1 + t + t2 + t3 + t4 + ... , : аk а !! 1! ! ! != !! !! !

## # аn аn а !! ! 5+ 1 ! 1 ! - 1 - 5! ! . !! ! !! = ! !! 2 2 5

13