XXXIX OM - III - Zadanie 2

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:

\[<br />
(1) \qquad  p_i < p_s \ \textrm{dla wszystkich}\ i < s.<br />
\]

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

\[<br />
(2) \qquad  X_n(P)= X_{n-1}(P') +1.<br />
\]

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

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

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

\[<br />
p_i' < p_s' \Leftrightarrow p_i < p_s \quad   (\textrm{dla } i, s \in \{1, \ldots, n-1\}).<br />
\]

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

\[<br />
(3) \qquad  X_n(P)= X_{n-1}(P').<br />
\]

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:

\[<br />
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}.<br />
\]

Stąd - przez oczywistą indukcję -

\[<br />
E(x_n) = 1 + \frac{1}{2} + \ldots +\frac{1}{n}.<br />
\]

Komentarze

Dodaj nową odpowiedź