Доказательство. По индукции. При n=1, 2 утверждение очевидно. Заметим, что имеет место соотношение . Предположим, что для n-1 множеств утверждение верно. Тогда
= .
Откуда
Следовательно, утверждение верно для n множеств. Что и требовалось доказать.
Задача о встречах. В дождливую погоду n человек пришли в театр. Они сдают зонтики в гардероб. После окончания спектакля получают зонтики обратно, в случайном порядке. Какова вероятность того, что каждый из них получит чужой зонтик?
Задача сводится к нахождению числа перестановок элементов множества {1, 2, ∙ ∙ ∙, n}, не имеющих неподвижных точек.
Пусть Si состоит из перестановок, оставляющих неподвижной точку i. Вычислим | S1È S2 È ∙ ∙ ∙È Sn |.
Искомая вероятность будет равна .
Получаем . Отсюда число перестановок, не имеющих неподвижных точек, равно . Искомая вероятность равна . Число f(n) будет ближайшим к дроби целым числом. При n®¥ вероятность стремится к .
Задача о счастливых билетах. Требуется найти число решений уравнения x1+x2+x3 = y1+y2+y3, где 0 £ xi, yi £ 9.
|
|
1) Подстановка x4=9-y1 , x5=9-y2 , x6=9-y3 устанавливает биекцию между решениями этого уравнения и уравнения x1+x2+x3 + x4+x5+x6 = 27, где 0£ xi £9.
Найдем число разложений x1+x2+x3 + x4+x5+x6 = 27, где 0£ xi £9.
Пусть U1 – число разложений с x1³10,
U2 – число разложений с x2³10,
∙∙∙
U6 – число разложений с x6³10.
Тогда | Ui ÇUjÇUk | =0 при |{I,j,k}|=3.
Вычислим число разложений, не удовлетворяющих неравенствам 0£ xi £9. Оно равно
| U1 ÈU2ÈU3 ÈU4 ÈU5 ÈU6 | = 6|U1|─15|U1ÇU2|,
где | U1| ─ число решений уравнения (x1─10)+x2+x3 + x4+x5+x6 = 27─10,
а |U1ÇU2| ─ число решений уравнения
(x1─10)+(x2─10)+x3 + x4+x5+x6 = 27─10-10.
Получаем | U1 ÈU2ÈU3 ÈU4 ÈU5 ÈU6 | = .
Из числа всех разложений вычитаем разложения с xi ≥10. Получаем окончательный ответ
.
Функция Эйлера. Пусть n – положительное натуральное число, j(n) – количество натуральных чисел 0<d£n, взаимно простых c n. Например, при n=10, dÎ{1, 3, 7, 9} и j(10) = 4. Функция j(n) называется функцией Эйлера.