Задача по теории вероятностей

[gris]

Навеяно прослушиванием Времён Года в случайном порядке.

Возник вопрос: какова вероятность появления хотя бы одной пары, проигрываемой в правильном порядке. Или, вероятность того, что таких пар не будет.
То есть вот такой порядок, например: 2,4,6,3,8,7,9,1,12,10,5,11.

Для малых списков в 1-4 номера посчитал честным выписыванием благоприятствующих исходов. Для 2 и 3 получилось 0,5. А вот уже для 4 вероятность хотя бы одной пары равна 13/24. Для большего количества пар уже нужна комбинаторика. Я смоделировал на компьютере. Рассматривал списки по 100 композиций и моделировал по миллиону перемешиваний.
Вот, собственно, в чём вопросы. Задача должна быть известной. Где прочитать?
Как получить точное комбинаторное решение?

Допустимо ли такое рассуждение для предельных случаев: Так как для очень больших списков событие появления конкретной пары соседних номеров можно приближённо считать независимыми от появления других пар, то вероятность того, что правильных пар не будет, приближённо равна $P=\left(\dfrac{n-2}{n-1}\right)^n\to e^{-1}$, что согласуется с результатами компьютерных испытаний. Пуассоном запахло, однако.

Ещё там несколько задач попутно помоделировал. Например, найти вероятность того, что $k$ будут на своём месте. И там Пуассон. Но вроде бы можно и отыскать решение комбинаторно и там $e^{-1}$ через ряд вырисовывается. (Это я посмотрел в книжке).

Ну и не удержусь и приведу код. Из-за последней его строчки.

j=12;  k=0;
m=new array(j);

for (  n=0, n<1000000, n++  ) {
      for (  i=0, i<j-1, i++  ) {  m[i]=i  };
      for (  i=0, i<j-2, i++  ) {   swap(  m[i],m[i+random(j-1-i)];  };
      for (  i=0, i<j-2, i++  ) {   if (m[i+1]-m[i] == 1) {  k=k+1; break  }   }
}
trace (k/n);

Так вот: последняя строка читается почти как "Стросс-кан"! К чему бы это?

Через три дня, когда снова выйду в инет, очень надеюсь найти советы и указания по теме. Как обычно говорят в подобных случаях, спасибо заранее.

[PAV]

Не знаю, приведет ли подсказка к решению, но попробуйте так: обозначьте через $S_n$ количество перестановок длины $n$, в которых нет ни одной правильной пары. Можно рассмотреть все возможные способы вставить туда следующее значение $n+1$ и получить что-то типа рекуррентного соотношения. То есть понятно, что для $n+1$ есть уже только $n$ допустимых позиций.

Однако нужно учесть также, что если в последовательности $n$ имеется ровно одна пара, тогда элемент $n+1$ можно вставить в единственную позицию между этими элементами и ее разрушить.

По идее может получиться. Возможно, что есть и другой способ, или что вообще есть каноническое решение.

-- Чт май 03, 2012 19:46:19 --

И, кстати, если не наврал, тогда сходу понятно, что количество последовательностей длины $n$, имеющих ровно одну пару, равно $(n-1)S_{n-1}$

[venco]

$p\approx 1-\frac 1 e-\frac 1 {ne}$
См. A180191

[longstreet]

(Оффтоп)

Что за язык программирования, на языке которого приведён код в стартовом сообщении?

[gris]

longstreet, это ActionScript for Adobe Flash.

Спасибо всем, кто откликнулся.

Всё же насчёт Стросс-кана это был реальный сигнал. Я сразу понял, что Сарко в пролёте. Ну да сейчас чего говорить.