Приложение. Математические вопросы Глава 2 м1. Совпадения знаков в алфавитах замены

Данная задача называется задачей о числе смещений элементов множества; ее решение в качестве частного случая может быть получено методом, известным под названиями принципа включения-исключения и классического метода решета. Доказательство этого метода можно найти в книгах по комбинаторике, таких как [2.6]. Применяя принцип включения-исключения, нетрудно показать, что среди всех перестановок множества (1,2,...,n) доля тех перестановок, в которых ни одно число не стоит на "своем" месте (то есть имеется n смещений), равна

и т.д. до (n+1)-го слагаемого.

Эта сумма дробей очень быстро сходится к значению 0,3678... , то есть к значению, обратному числу e (известному тем, кто знаком с натуральными логарифмами). Значения этой суммы для n от 0 до 6 с точностью до трех десятичных знаков равны 1, 0, 0.5, 0.333, 0.375, 0.367 и 0.368. Поэтому для значений n, больших 5, размер этой доли практически один и тот же. Это означает, что в перестановке знаков 26-буквенного алфавита примерно в 37% случаев не будет ни одной буквы, стоящей на "своем" месте, а в 63% случаев хотя бы одна такая буква найдется.