## Exercises and problems in Informatics |

## Please read The Conditions of the Problem Solving Competition.

**I. 79.** A *Pierce sequence of order* *N* is the monotonic increasing sequence of nonnegative fractions such that each denominator is at most *N*. (Fractions having the same value in the list are placed in order of decreasing denominators.) Write a program (i79.pas, ...) that computes a Pierce sequence of order *N* with terms not exceeding *M* (1\(\displaystyle \le\)*M* \(\displaystyle \le\)100, 1\(\displaystyle \le\)*N* \(\displaystyle \le\)100 with integer *N*).

*Example:* if *N*=2 and *M*=3, then the corresponding Pierce sequence is

\(\displaystyle \frac{0}{2},\ \frac{0}{1},\ \frac{1}{2},\ \frac{2}{2},\ \frac{1}{1},\ \frac{3}{2},\ \frac{4}{2},\ \frac{2}{1},\ \frac{5}{2},\ \frac{6}{2},\ \frac{3}{1}. \)

(*10 points*)

**I. 80.** Write a program (i80.pas, ...) that reads the coordinates of *N* vertices of a polygon (3\(\displaystyle \le\)*N*\(\displaystyle \le\)100 and all coordinates are integers between 0 and 500), then displays a triangulation of the polygon (using any method), see the *example* with *N*=12.

(*10 points*)

**I. 81.** Prepare a worksheet (i81.xls) that displays *Eulerian numbers* *E*(*n*,*k*) *of the second kind* in *n*+1 rows, if the value of *n* is written into cell A1.

*E*(*n*,*k*) can be computed in the following way. First take all permutations of the sequence {1,1,2,2,...,*n*,*n*} with the property that between the two occurrences of any number *m* there are no numbers below *m*. Then *E*(*n*,*k*) is the number of the permutations above containing exactly *k* increasing subsequences.

n\k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

0 | 1 | ||||||||||

1 | 1 | 0 | |||||||||

2 | 1 | 2 | 0 | ||||||||

3 | 1 | 8 | 6 | 0 | |||||||

4 | 1 | 22 | 58 | 24 | 0 | ||||||

5 | 1 | 52 | 328 | 444 | 120 | 0 | |||||

6 | 1 | 114 | 1452 | 4400 | 3708 | 720 | 0 | ||||

7 | 1 | 240 | 5610 | 32120 | 58140 | 33984 | 5040 | 0 |

(*10 points*)