XXXIX OM - III - Zadanie 2

Zawody matematyczne:

XXXIX OM, 1987-1988

Etap:

III

Dla permutacji $P=(p_1, \ldots, p_n)$ zbioru $\{1,2,\ldots, n\}$ definiujemy $X(P)$ jako liczbę wyrazów $p_s$ permutacji $P$ mających następującą własność: dla każdego $i < s$ zachodzi nierówność $p_i < p_s$ . Zakładając, że wszystkie permutacje są jednakowo prawdopodobnymi zdarzeniami losowymi, obliczyć wartość oczekiwaną zmiennej losowej $X$ .

Rozpatrywana zmienna losowa zależy od $n$ . Oznaczmy ją więc przez $X_n$ . Oczywiście $E(X_1) = 1$ . Znajdziemy zależność między $E(X_{n-1})$ a $E(X_n)$ .

Ustalmy liczby naturalne $n > 2$ oraz $k \in \{1, \ldots, n\}$ . Weźmy pod uwagę
dowolną permutację $P = (p_1, \ldots , p_n)$ zbioru $\{1, \ldots, n\}$ taką, że $p_n = k$ . Interesują nas wyrazy $p_s$ o własności:

$ (1) \qquad p_i < p_s \ \textrm{dla wszystkich}\ i < s. $

Rozpatrzymy dwa przypadki.

1. $k = n$ . Wówczas $p_n = n$ i jest to największy wyraz w ciągu $(p_1, \ldots,p_n)$ ; ma więc omawianą własność (tzn. (1) zachodzi dla $s = n$ ). Po odrzuceniu tego wyrazu otrzymujemy permutację $P' = (p_1, \ldots, p_{n-1})$ zbioru $\{1, \ldots, n - 1\}$ , w której jest $X_{n-1}(P')$ wyrazów $p_s$ spełniających warunek (1). Zatem w tym przypadku

$ (2) \qquad X_n(P)= X_{n-1}(P') +1. $

2. $k < n$ . Wyraz $p_n$ nie ma własności (1) (bo dla pewnego $i<n$ jest $??????? n>k$ ). Układ liczb $(p_1, \ldots, p_{n-1})$ stanowi permutację zbioru $\{1, \ldots, n\} \setminus \{k \}$ ; zatem układ $P' = (p_1', \ldots, p_{n-1}')$ , gdzie

$ p_i' = \left\{\begin{array}{ll} p_i & \textrm{gdy} \ p_i<k \\ p_i-1 & \textrm{gdy} \ p_i>k \end{array} \right. $

stanowi permutację zbioru $\{1, \ldots, n - 1\}$ , a przy tym mamy równoważność

$ p_i' < p_s' \Leftrightarrow p_i < p_s \quad (\textrm{dla } i, s \in \{1, \ldots, n-1\}). $

Wobec tego w całym układzie $P$ jest tyle samo wyrazów $p_s$ o własności (1), co w układzie $P'$ . Tak więc w tym przypadku

$ (3) \qquad X_n(P)= X_{n-1}(P'). $

Dla dowolnie ustalonej wartości $k \in \{1, \ldots, n\}$ odpowiedniość między permutacjami $P$ , w których $p_n = k$ , a permutacjami $P'$ zbioru $\{1, \ldots, n\} \setminus \{k\}$ określonymi powyżej (w każdym z przypadków) jest wzajemnie jednoznaczna. Ponieważ prawdopodobieństwo zajścia przypadku 1 wynosi $1/n$ , a przypadku 2 - $(1-1/n)$ , zatem z równości (2) i (3) wynika poszukiwana zależność rekurencyjna:

$ E(X_n) =\frac{1}{2}(E(X_{n-1}) + 1) + \left( 1 - \frac{1}{n} \right) E(X_{n-1}) = E(x_{n-1}) + \frac{1}{n}. $

Stąd - przez oczywistą indukcję -

$ E(x_n) = 1 + \frac{1}{2} + \ldots +\frac{1}{n}. $