Элементы комбинаторики и теории вероятностей. Николай Петрович Морозов

Чтение книги онлайн.

Читать онлайн книгу Элементы комбинаторики и теории вероятностей - Николай Петрович Морозов страница

Элементы комбинаторики и теории вероятностей - Николай Петрович Морозов

Скачать книгу

ых формул может быть выведено из двух основных утверждений, касающихся конечных множеств – правило суммы и правило произведения [1] .

1.1.Правило суммы

      Если конечные множества не пересекаются, то число элементов X U {или} Y равно сумме числа элементов множества X и числа элементов множества Y.

      То есть, если на первой полке стоит X книг, а на второй Y, то выбрать книгу из первой или второй полки, можно X+Y способами.

1.2.Правило произведения

      Если элемент X можно выбрать k способами, а элемент Y – m способами, то пару (X,Y) можно выбрать k*m способами.

      То есть, если на первой полке стоит 5 книг, а на второй 10, то выбрать одну книгу с первой полки и одну со второй можно 5*10=50 способами.

      Пересекающиеся множества

      Но бывает так, что множества X и Y пересекаются, тогда пользуются формулой, где X и Y – множества, а – область пересечения.

      

      

      Пример 1. Пусть 20 человек знают английский и 10 – немецкий, из них 5 знают и английский, и немецкий. Сколько человек всего знают один язык?

      Ответ: 10+20—5=25 человек.

      Очень часто для наглядного решения задачи применяются круги Эйлера.

      Пример 2. Из 100 туристов, отправляющихся в заграничное путешествие, немецким языком владеют 30 человек, английским – 28, французским – 42. Английским и немецким одновременно владеют 8 человек, английским и французским – 10, немецким и французским – 5, всеми тремя языками – 3. Сколько туристов не владеют ни одним языком?

      Решение: Выразим условие этой задачи графически (см. рис.2.1). Обозначим кругом тех, кто знает английский, другим кругом – тех, кто знает французский, и третьим кругом – тех, кто знают немецкий.

      

      Рис.2.1.

      

      Рис.2.2.

      Всеми тремя языками владеют три туриста, значит, в общей части кругов вписываем число 3. Английским и французским языком владеют 10 человек, а 3 из них владеют еще и немецким. Следовательно, только английским и французским владеют 10—3=7 человек.

      Аналогично получаем, что только английским и немецким владеют 8—3=5 человек, а немецким и французским 5—3=2 туриста. Вносим эти данные в соответствующие части рисунка 2.2.

      Определим теперь, сколько человек владеют только одним, из перечисленных языков. Немецкий знают 30 человек, но 5+3+2=10 из них владеют и другими языками, следовательно, только немецкий знают 20 человек. Аналогично получаем, что одним английским владеют 13 человек, а одним французским – 30 человек (см. рис.2.3).

      

      Рис.2.3.

      По условию задачи всего 100 туристов. 20+13+30+5+7+2+3=80 туристов знают хотя бы один язык, следовательно, 20 человек не владеют ни одним из данных языков.

1.3. Размещения без повторений

      Пример 3. Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны?

      Это пример задачи на размещение без повторений. Размещаются здесь 10 цифр по 6. А варианты, при которых одинаковые цифры стоят в разном порядке считаются разными.

      Если X-множество, состоящие из n элементов, m≤n, то размещением без повторений из n элементов множества X по m называется упорядоченное множество А, содержащее m элементов из m элементов.

      Количество всех размещений из n элементов по m обозначают

      (2.1)

      

      n! – n-факториал (factorial анг. сомножитель) произведение чисел натурального ряда от 1 до какого либо числа n. n!=1*2*3*…*n. 0!=1.

      Значит, ответ на выше поставленную задачу будет

      

1.4. Перестановки без повторений

      В случае n=m (см. размещения без повторений) А из n элементов по m называется перестановкой множества x.

      Количество всех перестановок из n элементов обозначают Pn.

      Pn=n!

      Действительно при n=m:

      (2.2)

      

      Пример 4. Сколько различных шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4,5, если цифры в числе не повторяются?

      Решение:

      Найдем

Скачать книгу