НГУ

Без ограничения общности можно считать, что пассажиры заходят в самолёт в том же порядке, в каком указаны их места в билетах. То есть у первого пассажира-бабки в билете значится место номер [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].

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

Ох уж мне эти некрофилы :)

Вероятность, что [tex]k[/tex]-й человек из [tex]N[/tex] сядет на своё место, равна [tex]p_k=\dfrac{N-(k-1)}{N-(k-2)}[/tex], если [tex]k\geq 2[/tex], и равна [tex]p_1=1/N[/tex] при [tex]k=1[/tex].

Если [tex]I_k[/tex] - индикатор того, что [tex]k[/tex]-й человек сел на своё место, то математическое ожидание числа севших на свои места равно
[tex]E\left(\sum_{k=1}^N I_k\right) = \sum_{k=1}^N p_k = \dfrac{1}{N}+\dfrac{N-1}{N}+\ldots+\dfrac12 = N-\sum_{k=1}^{N-1}\dfrac1k.[/tex]