Глава 2. Сложность в среднем

вопрос о среднем числе неподвижных точек перестановок длины n: найдем математическое ожидание определенной на Π_n случайной ве­личины ξ_n, равной числу неподвижных точек перестановки a. Допол­нительно определим случайные величины

_v 1, если a_v =v, ζ=

0, если a_v =v,

v = 1, 2,..., п. Мы видим, что P_П(С„ = 1) = P_П(В^) = -, откуда E<^ = - и

E£_п = E(C¹ + Й + ... + О = Ц1 + EЙ + ... + EГ = п • - = 1.

Итак, среднее число неподвижных точек равно 1.¹ Неподвижные точки перестановки соответствуют элементам мас­сива, которые при сортировке не нуждаются в перемещениях на дру­гие места, они и так находятся именно там, где должны находиться, и это может использоваться в некоторых видах сортировки (см. за­дачу 25).

Найдем теперь вероятности еще трех событий — эти вероятности потребуются нам при исследовании сложностей в среднем некоторых сортировок.

Предложение 6.1. Пусть п е N+. Тогда (i) при 1 s= и s= п, 1 s= v s= п имеем

1

■

" " п

для события F^^v, состоящего в том, что v-u элемент перестановки (а₁,а₂, ...,а„) равен и;

(ii) при 1 < и ^ п и любой перестановке р чисел 1, 2,..., и - 1 имеем

"( " ) (и-1)!

Эля события G^^p, состоящего в том, что относительный поряЭок элементов а,- , а,- ,..., а,- перестановки (а-,, а₂,... а„), меньших и, сов-

¹1 ¹2 'ii-1 ^1У , ⁿ ^

падает с относительным порядком элементов заданной перестанов­ки р (аналогичное утверждение имеет место для элементов, боль­ших и);

(iii) npu0^u<v^n имеем

P„(Я^¥) = - " n _v

¹ Серия вероятностных «задач о совпадении» с решениями приведена в [27].

§ 6. Сортировка и конечные вероятностные пространства 49

для события H_n^{u v}, состоящего в том, что в перестановке {a_ъa₂,...,a_n) содержится u элементов a_i, 1 ^ i < v, для которых a_i <a_v.

Доказательство. (i) Множество перестановок {a_ъ a₂,..., a_n) таких, что a_v = u, содержит (n-1)! элементов, независимо от значений u и v.

(ii) Событие G_n^u'^p включает ( ⁿ J(n-u + l)! перестановок, т.е.

n! гту перестановок, независимо от вида p.

(iii) Очевидно, что если p—любая перестановка чисел 1, 2, ...,v, то множество перестановок {a_г,a₂..., a_n) таких, что 'ф_v{a₁, a₂, ■■■,a_v) =

= p, содержит (ⁿ)(n-v)! = ⁿ_v- элементов (мы используем функ­цию i/v, определенную перед формулой (6.1)). Заметим, что коли­чество тех перестановок p чисел 1, 2,..., v, в которых последний эле­мент равен u + 1, есть (v-1)!. Поэтому количество перестановок,

образующих событие H_n^{u v}, равно ^j(v-l)!, т.е. у, откуда следует требуемое. _v' _v □

Напомним полезную формулу из курса теории вероятностей. Как и прежде, мы ограничимся рассмотрением конечных вероятност­ных пространств элементарных событий. Пусть W — такое простран­ство, P — соответствующее распределение вероятностей, Е,—некото­рая случайная величина (функция) на W. Пусть события W_ъ W₂,..., W_l задают полную группу событий, т. е. эти события попарно несовмест­ны и

W = W₁+W₂ + ... + W_l. (6.2)

Представление W в виде (6.2) с помощью некоторой полной группы событий мы будем называть разложением W. Как обычно, E? —это значение ^ ?(w)P(w), т. е. математическое ожидание (или среднее)

случайной величины £, а E(£|W_k), k = 1, 2,..., l, суть соответствующие условные математические ожидания этой случайной величины (при условии осуществления события W_k). Тогда, как известно, имеет ме­сто формула полного математического ожидания:

^l E?=^E(?|WУP(WУ. (6.3)

k=i

Оценивание математических ожиданий является оцениванием число­вых сумм. В этом иногда помогает простой прием, описанный в при­ложении B.

50