Параграф 1.1 (Математика 11)

Koмбинаторика

Из курса основной школы мы знаем, что

вероятностью Р(А) появления события А называется отношение числа k всех благоприятствующих этому событию исходов испытания к общему числу n всех возможностей: P\left(A\right)=\frac{k}{n}.

Пример 1.

У малыша есть 5 карточек, на которых написаны пока еще незнакомые ему цифры 0, 1, 2, 3, 4. Он располагает в ряд три случайно взятые карточки. Какова вероятность того, что он выложит трехзначное число?

Для решения нужно найти число всех возможностей n и число благоприятствующих возможностей k.

Чтобы выяснить, каким образом проще всего найти величины n и k, нам нужно познакомиться с некоторыми понятиями и фактами раздела математики, называемого комбинаторикой. Вообще говоря, комбинаторика изучает вопросы о том, как из данных элементов составлять множества, удовлетворяющие определенным условиям (такие множества называются также соединениями), и каково количество всех таких множеств (соединений).

Ниже мы рассмотрим некоторые понятия и факты комбинаторики.

Пусть ребенку предоставлена возможность выбрать одну игрушку из 3 мячиков и 2 кукол. Ясно, что различных возможностей для выбора у него будет 3 + 2 = 5. Подобные ситуации обобщаются в комбинаторике в виде так называемого правила сложения:

если выбор некоторого объекта A может быть осуществлен n различными способами, а выбор другого объекта B может быть осуществлен m различными способами, то число способов, которыми можно осуществить выбор либо объекта А, либо объекта В, равно сумме n + m.

В приведенном примере объектом А является мячик, объектом В кукла, а соответствующие числа способов выбора есть n = 3m = 2.

В некоторых случаях число возможностей для выбора подчиняется так называемому правилу умножения:

если выбор некоторого объекта A может быть осуществлен n различными способами, а выбор другого объекта B может быть осуществлен m различными способами, то число способов, которыми можно осуществить выбор как объекта A, так и объекта B, равно произведению n · m.

Например, если ребенок должен выбрать один из 3 мячиков и одновременно одну из 2 кукол, то всего у него имеется 3 · 2 = 6 возможностей для выбора. Правилу умножения нетрудно дать и общее обоснование. Каждому из выборов объекта А сопутствует m возможностей выбора объекта В. Так как объект А можно выбрать n различными способами, то число возможностей для выбора как А, так и В будет как раз равно n · m.

Рассмотренные выше правила сложения и умножения можно обобщить на случай выбора трех и более объектов (считая, что предыдущие объекты уже выбраны).

Пример 1​. (прод.)

Решим задачу, сформулированную в примере 1.

Решение. Найдем число k возможностей, благоприятствующих событию, cocтоящему в появлении трехзначного числа. Для выбора первой цифры трехзначного числа имеется 4 возможности, так как 0 не может быть первой цифрой. После того, как первая цифра выбрана, можно выбрать любую из оставшихся 4 цифр, т. е. для выбора второй цифры имеется 4 возможности. После того, как выбраны первая и вторая цифры, есть 3 возможности для выбора третьей цифры. Поскольку должны быть выбраны как первая, так и вторая и третья цифры, то по правилу умножения получим, что всего можно составить 4 · 4 · 3 = 48 трехзначных чисел.

Рассуждая аналогично, мы видим, что из пяти цифр можно составить (располагая их подряд) n = 5 · 4 · 3 = 60 всевозможных комбинаций. Следовательно, соответствующая вероятность есть p = k : n = 48 : 60 = 0,8.

Правилам сложения и умножения соответствуют и словесные выражения, позволяющие различать эти случаи. В правиле сложения употребляется выражение либо А, либо В, а в правиле умножения – как А, так и В (коротко – A и В).

Пример 2.

Найдем, сколько автомобилей можно было бы зарегистрировать в Эстонии, если бы номер автомобиля состоял либо из четырех цифр, либо из четырех букв эстонского алфавита, за исключением букв Õ, Ä, Ö, Ü, Š, Ž.

Решение. По правилу умножения из цифр можно образовать 10 ⋅ 10 ⋅ 10 ⋅ 10 = 104 различных номеров. Аналогично, из 26 букв можно образовать 264 автомобильных номеров. Так как номера можно образовывать либо из цифр, либо из букв, то по правилу сложения получим, что всего можно было бы зарегистрировать 104 + 264 = 466 976 автомобилей.

Пример 3.

У маленького Пети есть четыре карточки с буквами Е, Л, О, С. Найдем, сколькими способами он может их упорядочить, т. е. сколько и каких «слов» он может составить из этих карточек.

Решение. Первую букву можно выбрать 4 различными способами, вторую – тремя, третью – двумя и четвертую - одним способом. По правилу умножения всего можно составить 4 · 3 · 2 · 1 = 24 слова. Приведем их список:

Е Л О С

Е Л С О

Е О Л С

Е О С Л

Е С Л О

Е С О Л

Л Е О С

Л Е С О

Л О Е С

Л О С Е

Л С Е О

Л С О Е

О Е Л С

О Е С Л

О Л С Е

О Л Е С

О С Е Л

О С Л Е

С Е Л О

С Е О Л

С Л О Е

С Л Е О

С О Л Е

С О Е Л

С точки зрения комбинаторики в данном случае мы имеем дело с перестановками из четырех элементов. Дадим общее определение.

Перестановкой из n различных элементов называется любая упорядоченная комбинация всех элементов n-элементного множества.

Число всевозможных перестановок из n элементов обозначается символом Pn. По правилу умножения получим: Pn n · (n – 1) · (n – 2) · … · 3 · 2 · 1.

Произведение всех натуральных чисел от 1 до n называется факториалом числа n и обозначается символом n!

Таким образом,

Pnn · (n – 1) · (n – 2) · … · 3· 2 · 1 = n!

Например, 4! = 4 · 3 · 2 · 1 = 24.

Так как число перестановок из 1 элемента, очевидно, равно 1, то, желая сохранить соответствие с формулой Pn = n!, естественно определить факториал числа 1 следующим образом:

1! = 1.

Теперь получим, что P1 = 1! = 1.

Большинство калькуляторов имеет специальную клавишу !, x! или n!, позволяющую найти факториал числа.

Пример 4.

Найдем с помощью калькулятора \frac{50!\cdot40!\cdot5!}{28!\cdot60!\cdot8!}.

Калькулятор, как правило, не позволяет найти значение такого выражения, найдя сначала значение числителя дроби. Уже при вычислении значения произведения 50! · 40! на табло появляется сообщение, что результат не помещается в памяти калькулятора. Этого можно избежать, если производить вычисления в таком порядке, при котором можно сохранять промежуточные результаты. Например, это можно сделать по следующей схеме:

50 !: 60 !· 40 !: 28 !· 5 !: 8 !=

и в результате получим 0,0291115274.

Пример 5.

Найдем, сколько четырехбуквенных «слов» можно составить из букв А, А, Б, Р. Некоторые из этих слов содержательны.

Метод решения, использованный в примере 3, здесь не подходит, так как при перестановке одинаковых букв «слово» не изменяется. 

Но можно выписать все эти «слова» и затем подсчитать их количество. Чтобы избежать ошибок, рекомендуется сделать это с помощью диаграммы «дерево», как показано на рисунке 1.1.

Рис. 1.1

Упражнения A

Задание 1. Выбор фруктов
  1. либо одно яблоко, либо одну сливу, либо одну грушу?

    Ответ: в этом случае фрукты можно выбрать  различными способами.
  2. по одному фрукту каждого вида?

    Ответ: в этом случае фрукты можно выбрать  различными способами.
Задание 2. Составление двухбуквенных слов
  1. буквы должны быть различными?
    Ответ: можно составить  различных слов.
  2. буквы могут быть одинаковыми?
    Ответ: можно составить  различных слов.
  3. одна из букв должна быть гласной, а другая – согласной?
    Ответ: можно составить   различных слов(а).

Задание 3. Размещение компании в кино

Ответ: 5 человек могут разместиться  различными способами.

Задание 4. Обед из трех блюд

Ответ: можно выбрать  различных обедов из трех блюд.

Задание 5. Путь из города A в поселок D

Ответ: из города A в поселок D можно проехать  различными способами.

Задание 6. Руководство из лиц разной национальности

Ответ: это можно сделать  различными способами.

Задание 7. Номер автомобиля

Ответ: по этой системе можно зарегистрировать   автомобилей.

Задание 8. Однозначные, трехзначные, пятизначные и семизначные числа

Ответ: всего можно образовать  таких чисел.

Задание 9. Перестановки из букв Н, С, О

Ответ: получится   осмысленных слова.

Задание 10. Ноты одной октавы

Ответ: 12 нот одной октавы можно сыграть  различными способами.

Задание 11. Перестановки из элементов Л, К, П, О

Ответ: получается   осмысленных слова.

Задание 12. Все возможные фразы из трех словt есть, тут, слон

Задание 13. Вход в автобус

Ответ: 10 туристов могут войти в автобус  различными способами. Чтобы „проиграть” все эти ваотанты, потребуется   дней.

Задание 14. Посылка приглашений

Ответ: может получиться  различных вариантов.

Задание 15. Составление списка учеников класса

Задание 16. Гости и стулья

Ответ: четырех гостей можно разместить на 6 стульях  различными способами.

Задание 17. Пятизначный цифровой код
  1. все цифры должны быть различными?

    Ответ: тогда можно составить  различных кодов.
  2. цифры могут повторяться?

    Ответ: тогда можно составить  различных кодов.
Задание 18. Факториал числа

3!\ +\ 4! =  = 

4!\ -\ 3! =  = 

\frac{18!}{16!} =  = 

3!\ \cdot\ 4! =  = 

5!\ \cdot\ 6 =  = 

\frac{1!\cdot19!}{20!} =  = 

4!\ :\ 3! =  = 

8!\ :\ 56 =  = 

\frac{6!\cdot9!}{3!\cdot5!} =  = 

Задание 19. Выражение натуральных чисел 1, 2, 3, 4, 5 с помощью факториалов

1 = 

2 = 

3 = 

4 = 

5 = 

Задание 20. Упрощение

\left(n+1\right)\cdot n\cdot\left(n-1\right)! = 

\left(n-1\right)\cdot n!+n\cdot\left(n-1\right)! = 

\frac{n!}{\left(n-1\right)!}-\frac{\left(n+1\right)!}{n!} = 

\frac{\left(n+3\right)\left(n+2\right)\left(n+1\right)n!}{\left(n+4\right)!} = 

Упражнения Б

Задание 21. Упрощение

\frac{n!}{\left(n-1\right)!}+\frac{n!}{2!\left(n-2\right)!} = 

\frac{\left(n-1\right)!\cdot n\cdot\left(n+1\right)}{n!}+\frac{\left(n+1\right)!}{\left(n-1\right)!} = 

Задание 22. Число различных перестановок

Если среди n объектов имеется s объектов вида А и t объектов вида В, причем s + t = n, то из таких n объектов можно образовать \frac{n!}{s!t!} различных перестановок. Докажите это утверждение.

Задание 23. Пятизначные числа

Ответ: из этих цифр можно образовать  различных пятизначных чисел.

Задание 24. Слово ANANASS

Ответ: эти буквы можно расположить   различными способами.

Задание 25. Близнецы

Ответ: участников вечера можно упорядочить  различными способами.

Задание 26. Учебники

Ответ: это можно сделать  различными способами.

Ülesanne 27.Различные делители числа миллиард

Ответ: число 1 000 000 000 имеет  различных делителей.

Задание 28. Пятизначные числа

Ответ: с повторяющимися цифрами имеется всего  пятизначных чисел, что составляет % от всех пятизначных чисел. В случае четырехзначных чисел соответствующий процент будет .

Задание 29. Самые древние предки человека

Ответ: у каждого человека есть  "четырежды пра" предков, а на слудующем этапе всего   предков.

Задание 30. Анаграммы

Найдите:

  1. анаграммы слова «кот».
    Ответ: это будут  и  .
  2. анаграммы своего (если они есть) или какого-нибудь другого имени.
    Ответ: это будут .
  3. Сколько различных перестановок Вы можете образовать из своей фамилии?
    Ответ: из моей фамилии можно образовать  перестановок.
Задание 31. Решение уравнения

P_x=56P_{x-2}

x

Будь ласка, зачекайте