Студенческая олимпиадная задача

[Cronky]

Если кому-то интересно, вот задача со студенческой олимпиады, которую почти никто не решил:
Неразборчивый жених женится на первой встречной, а как только встретит кого-то лучше своей текущей супруги, оформляет развод и женится снова. Такую активность жених проявляет с 20 до 45 лет, за это время ему в случайном порядке встретятся 50 неотразимых женщин, не возражающих против брака с ним (женится он не на всех из них, а только по правилу, описанному выше). Хватит ли в среднем места в паспорте для простановки всех штампов о браках и разводах, если на страницах о семейном положении умещаются штампы о 5 браках и 4 разводах, а потенциальные невесты встречаются в случайном порядке? Указание: используете то, что сумма $1/2+1/3+…+1/50<\ln 50$

Cronky, формулы оформляйте $\TeX$ом, сейчас я формулы поправил, в дальнейшем буду отправлять темы в Карантин.

[deep blue]

Число k-возрастающих n-ок является числом Стирлинга $S(n,k)$. Таким образом математическое ожидание числа возрастаний в n-ке будет равно:

$$M(n)=\frac1{n!}\sum\limits_{k=1}^{n}kS(n,k)=\frac1{n!}\sum\limits_{k=1}^{n-1}(n-1)kS(n-1,k)+\frac1{n!}\sum\limits_{k=1}^{n}kS(n-1,k-1)=$$

$$=\frac1{(n-1)!}\sum\limits_{k=1}^{n-1}kS(n-1,k)+\frac 1 n=M(n-1)+\frac 1 n=1+\frac 1 2+\dots+\frac 1 n$$

Откуда $M(50)<\ln{50}+1<5.5$ так что места в паспорте хватит и на самом деле останется на еще один брак.