Advanced book on Mathematics Olympiad

752 Combinatorics and Probability which can be interpreted as the characteristic equation of a recursive sequencexn+ 1 − (^4) √x ...

Combinatorics and Probability 753 = ∑n+^1 k= 0 (( n k ) + ( n k− 1 )) [x]k[y]n−k+ 1 = ∑n+^1 k= 0 ( n+ 1 k ) [x]k[y]n+ 1 −k. The ...

754 Combinatorics and Probability for someAandB. It follows thatyn=Aan+Bbn, and becausey 0 =1 andy 1 =a+b, A=aa−bandB=−ab−b. The ...

Combinatorics and Probability 755 1 x (( 1 +x)n+m+^1 −( 1 +x)n). We deduce that the sum is equal to (n+m+ 1 k+ 1 ) − (n k+ 1 ) f ...

756 Combinatorics and Probability Remark.This property is usually phrased as follows: Prove that the number of partitions ofnint ...

Combinatorics and Probability 757 ∫ 2 π 0 (2 cost)(2 cos 2t)···(2 cosnt)dt= 2 π S(n)+ 0 , whence the desired formula S(n)= 2 n−^ ...

758 Combinatorics and Probability anx= ∑∞ a= 1 caxa, withca=1ifa∈Anandca=0ifa/∈An.ToBnwe associate the functionbn(x)in a similar ...

Combinatorics and Probability 759 We emphasize again that this is to be considered modulo 2. In order forbn(x)to be identically ...

760 Combinatorics and Probability elect the president and then elect the other members of the committee from the remaining 2 n−1 ...

Combinatorics and Probability 761 ofC(this can be done in 2m−iways). Then choosek−iof then−mY’s (in (n−m k−i ) ways) and replace ...

762 Combinatorics and Probability 885.We count the points of integer coordinates in the rectangle 1 ≤x≤p′, 1 ≤y≤q′. Their total ...

Combinatorics and Probability 763 x 1 +x 2 +···+xm=n−xm+ 1. Asxm+ 1 ranges between 0 andn, the right-hand sides assumes all valu ...

764 Combinatorics and Probability 890.Leta<b<c<dbe the members of a connected setS. Becausea−1 does not belong to the s ...

Combinatorics and Probability 765 distinct subsets of cardinal 2 inAis 4950. By the pigeonhole principle, there exist distinct e ...

766 Combinatorics and Probability 895.(a) For fixedx ∈A, denote byk(x)the number of setsB ∈Fthat containx. List these sets asB 1 ...

Combinatorics and Probability 767 We can obtain one hundred polygons with twenty sides by making 1699 cuts in the following way. ...

768 Combinatorics and Probability paths pass through(r, s). To apply the inclusion–exclusion principle, we also need to count th ...

Combinatorics and Probability 769 |A 1 ∪A 2 ∪···∪An|= ( n 1 ) (n− 1 )!− ( n 2 ) (n− 2 )!+···+(− 1 )n ( n n ) 1 !. The number of ...

770 Combinatorics and Probability If the acute angle of them-gon isAkA 1 Ak+r, the condition that this angle is acute translates ...

Combinatorics and Probability 771 This number is equal to m^1989 −m^663 −m^153 −m^117 +m^51 +m^39 +m^9 −m^3 , since the−1’s in t ...