

Exercises and problems in Informatics December 2003 
I. 64. The Farey sequence F_{N} for any positive integer N is the sequence of irreducible rational numbers between 0 and 1 for which the denominator is at most N and they are arranged in increasing order. For example, \(\displaystyle F_6=\left\{\frac{0}{1},\,
\frac{1}{6},\,\frac{1}{5},\,\frac{1}{4},\,\frac{1}{3},\,
\frac{2}{5},\,\frac{1}{2},\,\frac{3}{5},\,\frac{2}{3},\,
\frac{3}{4},\,\frac{4}{5},\,\frac{5}{6},\,\frac{1}{1}
\right\}.\)
For any given N (1\(\displaystyle \le\)N \(\displaystyle \le\)100), your program (i64.pas, ...) should display the Farey sequence F_{N}.
(10 points)
I. 65. Given N+1 points (x_{i},y_{i}) in the plane, a Bézier curve nicely approximating them is given by its coordinatefunctions x and y in the following parametric form (with 0\(\displaystyle \le\)u \(\displaystyle \le\)1 being a real parameter):
\(\displaystyle
x(u)=\sum_{i=0}^nx_i{n\choose i}u^i(1u)^{ni},\quad y(u)=\sum_{i=0}^ny_i{n\choose i}u^i(1u)^{ni}.
\)
Write your program (i65.pas, ...) which reads the coordinates of the N+1 points then draws them together with the corresponding Bézier curve.
Example.:
N=14 
The points: 
(0,0),(16,40),(25,45), 
(36,65),(49,70),(64,80), 
(81,90),(100,100),(121,120), 
(144,120),(169,120),(196,140), 
(225,150),(256,160),(289,170)
(10 points)
I. 66. Euler's number triangle is similar to Pascal's triangle, but instead of the binomial coefficients, it contains the Eulerian numbers E(n,k). For 0\(\displaystyle \le\)n \(\displaystyle \le\)15 and 0\(\displaystyle \le\)k \(\displaystyle \le\)n, E(n,k) is defined as the number of permutations of {1,2,...,n} having exactly k permutation ascents (i.e. having k pairs of adjacent positions in the permutation that are out of order).
Prepare your sheet (i66.xls) that  on entering the value of m (0\(\displaystyle \le\)m\(\displaystyle \le\)15) into cell <<\texttt>>A1  displays the Eulerian numbers E(n,k) (n=0,1,...,m) in the first n+1 rows of the sheet. Numbers should only appear in valid cells.
Example for m=10:
10 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
0 
1 










1 
1 
0 









2 
1 
1 
0 








3 
1 
4 
1 
0 







4 
1 
11 
11 
1 
0 






5 
1 
26 
66 
26 
1 
0 





6 
1 
57 
302 
302 
57 
1 
0 




7 
1 
120 
1191 
2416 
1191 
120 
1 
0 



8 
1 
247 
4293 
15619 
15619 
4293 
247 
1 
0 


9 
1 
502 
14608 
88234 
156190 
88234 
14608 
502 
1 
0 

10 
1 
1013 
47840 
455192 
1310354 
1310354 
455192 
47840 
1013 
1 
0 

 (10 points)
Send your solutions to the following email address:
Deadline: 13 January 2004

