АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Теорема 1. (Формула включения-исключения)

Читайте также:
  1. I. 4.1. Первая теорема двойственности
  2. S-M-N-теорема, приклади її використання
  3. Б1 1.Системы линейных алгебраических уравнений (СЛУ). Теорема Кроникера-Капелли. Общее решение СЛУ.
  4. Базисный минор и ранг матрицы. Теорема о базисном миноре
  5. Билет 22Понятие евклидова пространства, неравенство Коши-Буняковского. Теорема Кронекера Капелли.
  6. Билет 5 Теорема Безу и следствия из неё. Основная теорема алгебры.
  7. Внешние эффекты (экстерналии). Теорема Коуза.
  8. Внешние эффекты и внешние затраты. Государственная политика в случаях их возникновения. Теорема Коуза.
  9. Внешние эффекты трансакционные издержки. Теорема Коуза
  10. Внешние эффекты, их виды и последствия. Теорема Коуза
  11. Внешние эффекты. Теорема Коуза.
  12. Внешние эффекты. Теорема Коуза.

Доказательство. По индукции. При n =1, 2 утверждение очевидно. Заметим, что имеет место соотношение . Предположим, что для n множеств утверждение верно. Докажем ее для n+1. Имеем по формуле включения-исключения для n множеств A1 Ç An+1, A2 Ç An+1, …, An Ç An+1 :

Поскольку формула верна при n =2, то справедливо равенство

.

Отсюда мы видим, что содержит слагаемое, равное сумме и соответствующее первому слагаемому в формуле включения-исключения для n +1 множеств. Объединим k -е слагаемое определенное в формуле для и (k-1)-е слагаемое в формуле включения-исключения для . В силу = , будем иметь

- =

= .

В результате мы получили k -е слагаемое в формуле включения-исключения для множеств A1, …, An+1. Следовательно, эта формула верна для n+1 множеств. Что и требовалось доказать.

Задача о встречах. В дождливую погоду n человек пришли в театр. Они сдают зонтики в гардероб. После окончания спектакля получают зонтики обратно, в случайном порядке. Какова вероятность того, что каждый из них получит чужой зонтик?

Задача сводится к нахождению числа перестановок элементов множества {1, 2, ∙ ∙ ∙, n}, не имеющих неподвижных точек.

Пусть Si состоит из перестановок, оставляющих неподвижной точку i. Вычислим

| S1È S2 È ∙ ∙ ∙È Sn |.

Искомая вероятность будет равна .

Получаем . Отсюда число перестановок, не имеющих неподвижных точек, равно . Искомая вероятность равна . Число f (n) будет ближайшим к дроби целым числом. При n ®¥ вероятность стремится к .

Задача о счастливых билетах. Требуется найти число решений уравнения x1+x2+x3 = y1+y2+y3, где 0 £ xi, yi £ 9.

Решение. Подстановка 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 (т.е. не имеющих одинаковых делителей, кроме 1). Например, при n =10, d Î{1, 3, 7, 9} и j (10) = 4. Функция j (n) называется функцией Эйлера.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)