Вот на суд "землемерческое" доказательство формулы для мат ожидания
Идею изложу вкраце.
1.разобъём всё множество вариантов N^N на два подмножества, в одном все те,где есть некоторая цифра(условно 1), в другом - где её нет.
2.каждое подмножество разобъём на два по признаку наличия некой другой цифры (условно 2)
3..N аналогично для цифр 3..N
Теперь представим это графически в виде прямоугольника шириной N^N и высотой N
область ░ - там, где нет цифры (соответствующего уровня)
область █ - там, где она есть
на каждом уровне общая площадь ░ равна (N-1)^N, площадь всех областей ░ равна N(N-1)^N
главное - абсолютно не важны конкретные ширины заштрихованных областей
и ещё -
нет вертикальной области высотой N из ░
схематично изображено для N=3 для пояснения
Код:
1 N^N
1 ░░░░░░░░░████████████
2 ░░███████░░░░████████
3 ██░░░████░░██░░░█████
получается,при рассматривании вертикалей, ░ будет определять к-во отсутствующих цифр в вариантах.
мат.ожидание вычисляем, рассматривая вертикали, двигаясь по горизонтали и имеем:
мат ожидание есть отношение площади всех областей ░ к N^N, M=N(N-1)^N/N^N= N(1-1/N)^N
а отношение мат.ожидания к N,
M/N=(1-1/N)^N
Спасибо Trurl , идея появилась после чтения
http://forum.oberoncore.ru/viewtopic.php?f=27&t=3554&start=80#p65190PS. Поправил текст немного.
Если кого смущает, а зачем нужна это ерунда с разбивкой на части, то отвечу - незачем, просто для того, что бы картинка была более конкретной (этакое упорядочивание применено)
Ну и для полноты уж переведу на более "пацанский" язык.
Всем возможным последовательностям случайных чисел(1..N) длины N присвоим номера от 1 до N^N, и обозначим каждую как Xj, где j=1..N^N
Построим матрицу размерности N (вертикаль) на N^N (горизонталь) из элементов Aij, i=1..N, j=1..N^N
Aij=1 , если число i
не присутствует в Xj
Aij=0 , если число i присутствует в Xj
для любого i сумма всех Aij, где j=1..N^N ( по горизонтали) равна (N-1)^N (кол-во всех Xj образованных без числа i)
сумма всех Aij по всей матрице S= N(N-1)^N
обозачим как Sj сумму всех Aij, где i=1..N (сумма по вертикали), т.е. Sj=кол-ву отсутствующих чисел из диапазона 1..N в последовательности Xj
мат.ожидание M (то что нас интересует в рассматриваемом эксперименте) будет равно сумме всех Sj/N^N, где j=1..N^N
вынося 1/N^N за скобки и суммируя все Sj получим M=S/N^N=N(N-1)^N/N^N=N(1-1/N)^N
а отношение M/N=(1-1/N)^N