Anonymous писал(а):
Какова вероятность, что человек номер к, сядет на свое место?
Чему равно среднее количество людей которые сядут на свои места?
Без ограничения общности можно считать, что пассажиры заходят в самолёт в том же порядке, в каком указаны их места в билетах. То есть у первого пассажира-бабки в билете значится место номер [tex]1[/tex], у второго заходящего в самолёт в билете указано место номер [tex]2[/tex] и т. д.
Допустим, бабка садится на место [tex]n_2[/tex]. Пассажир, у которого в билете значится место [tex]n_2[/tex], садится на место [tex]n_3[/tex]. Пассажир с местом [tex]n_3[/tex] в билете садится на место [tex]n_4[/tex] и т. д. Для некоторого [tex]m \leqslant N[/tex] будем иметь [tex]n_{m+1} = 1 = n_1[/tex]. Если рассмотреть перестановку [tex]\sigma[/tex], сопоставляющую номеру каждого билета номер места, на которое сел пассажир с этим билетом, то [tex]\sigma[/tex] будет состоять из одного цикла [tex](n_1, n_2, \ldots, n_m)[/tex]. Ясно, что [tex]1 = n_1 < n_2 < \ldots < n_m \leqslant N[/tex].
Пусть [tex]i \geqslant 1[/tex] и [tex]\bar{k}[/tex] - строго возрастающая последовательность натуральных чисел [tex]1 = k_1 < k_2 < \ldots < k_i \leqslant N[/tex] длины [tex]i[/tex], начинающаяся с [tex]1[/tex] и состоящая из чисел, не превосходящих [tex]N[/tex] (через [tex]U_i[/tex] обозначим множество всех таких последовательностей). Пусть [tex]A_\bar{k}[/tex] - событие, заключающееся в том, что [tex]m = i[/tex] и [tex]n_j = k_j[/tex] при всех [tex]j \in [1,i][/tex]. Тогда [tex]P(A_{\bar{k}}) = \frac{1}{N-k_1+1} \cdot \frac{1}{N-k_2+1} \cdot \ldots \cdot \frac{1}{N- k_i +1}[/tex]. Получаем, что
[tex]
P(m=i) = \sum_{\bar{k} \in U_i} \prod_{j=1}^i \frac{1}{N-k_i+1}
[/tex]
При [tex]i \neq 1[/tex] данная вероятность соответствует тому, что ровно [tex]i[/tex] человек сядут не на свои места.
И как это, спрашивается, считать? Может, есть какие-нибудь хитрые способы?
Что видно сразу? [tex]P(m=1) = 1/N[/tex] (бабка села на своё место и все сели на свои места), [tex]P(m=N) = 1/N![/tex] (все сели не на свои места в том и только в том случае, если каждый человек садится на следующее за его местом). Ещё [tex]P(m=2) = H_{N-1}/N[/tex], где
[tex]
H_k = \frac{1}{1} + \frac{1}{2} + \ldots + \frac{1}{k}
[/tex]
есть [tex]k[/tex]-ая частичная сумма гармонического ряда. И при [tex]N \to \infty[/tex] получается, что [tex]P(m=2) \approx \ln(N-1) / N[/tex].