Как найти число размещений без повторений

Размещения

  1. Размещения без повторений
  2. Размещения с повторениями
  3. Примеры

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

Размещениe без повторений – это упорядоченная ⟨n,k⟩ – выборка без повторений,     kn. Общее количество размещений без повторений: $$ mathrm{ A_n^k=frac{n!}{(n-k)!} } $$

Например:
Для создания 3-значного пароля используются символы из алфавита {+,*,A,!,2}.
Сколько всего паролей без повторения символов можно составить?
По условию n = 5, k = 3. Рассматриваем размещение 5 символов по 3 позициям без повторений: (mathrm{ A_5^3=frac{5!}{(5-3)!}=5cdot 4cdot 3 = 60 })
Всего 60 паролей.
Результат можно получить непосредственно из правила произведения. Действительно, на первой позиции – 5 вариантов символов, на второй – 4 оставшихся, на третьей – 3 оставшихся. Итого, по правилу произведения: 5 · 4 · 3 = 60 паролей.

п.2. Размещения с повторениями

Размещение с повторением – это упорядоченная ⟨n,k⟩ – выборка с повторениями. Общее количество размещений с повторениями: $$ mathrm{ overline{A}_n^k=n^k } $$

Например:
Для создания 3-значного пароля используются символы из алфавита {+,*,A,!,2}.
Сколько всего паролей можно составить?
По условию n=5, k=3. Рассматриваем размещение 5 символов по 3 позициям с повторениями: (mathrm{ overline{A}_5^3=5^3=125. })
Всего 125 паролей.
Результат можно получить непосредственно из правила произведения. Действительно, на первой позиции 5 вариантов символов, на второй – 5 вариантов, и на третьей – 5 вариантов. Итого, по правилу произведения: 5 · 5 · 5 = 53 = 125 паролей.

п.3. Примеры

Пример 1. Исследуйте различие между перестановкой без повторений и размещением без повторений ⟨3,2⟩-выборок для трёх разноцветных фишек. Изобразите полученные решения.

Рассматриваем фишки: Пример 1

1) Для перестановок, ⟨3,3⟩-выборок, получаем:

Пример 1 В каждом ряду – отдельная перестановка.
Видно, как образуется факториал. Для каждой отдельной фишки – одна перестановка. Для каждой пары фишек – две перестановки: 2 · 1. Когда добавляем третью, получаем: 3 · 2 · 1
Итого: P3 = 3 · 2 · 1 = 6 перестановок.

2) Для размещений без повторений, ⟨3,2⟩-выборок, получаем:

Пример 1 В каждом ряду – отдельное размещение.
В первом столбце слева – 3 варианта по цвету.
Во втором столбце остается только 2 варианта.
Итого: (mathrm{A_3^2=3cdot 2=6}) размещений.

Пример 2. Исследуйте перестановки без повторений и размещения для ⟨4,3⟩ выборок и для ⟨4,2⟩ выборок без повторений из 4 разноцветных фишек.
Изобразите полученные решения.

Рассматриваем фишки: Пример 2

Пример 3. Исследуйте различие между перестановкой с повторениями и размещением с повторениями. Сделайте вывод.
Перестановка с повторениями: сколько слов можно получить, переставляя буквы в слове «МАМА»? Запишите все эти слова в лексикографическом порядке.
Размещение с повторениями: сколько 4-буквенных слов можно получить, используя две буквы: «М» и «А»? Запишите все эти слова в лексикографическом порядке.

1) Для перестановки с повторениями получаем: begin{gather*} mathrm{ a_1=M,k_1=2, a_2=A,k_2=2 }\ mathrm{ k=k_1+k_2=2+2=4 }\ mathrm{ P_4(2;2)=frac{4!}{2!cdot 2!}=frac{24}{2cdot 2}=6 } end{gather*} Все 6 слов в лексикографическом порядке:

AAMM≺AMAM≺AMMA≺MAAM≺MAMA≺MMAA

2) Для размещения с повторениями получаем: begin{gather*} mathrm{ n=2, k=4 }\ mathrm{ overline{A}_2^4=2^4=16 } end{gather*} Все 16 слов в лексикографическом порядке:

AAAA≺AAAM≺AAMA≺AAMM≺AMAA≺AMAM≺AMMA≺AMMM≺
≺MAAA≺MAAM≺MAMA≺MAMM≺MMAA≺MMAM≺MMMA≺MMMM

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

Пример 4. В базе данных с номерами телефонов содержатся все 7-значные номера.
1) Сколько в книге номеров, в которых цифры не повторяются?
2) Сколько в книге всего номеров?
3) Сколько в книге номеров, у которых 4 последних цифры одинаковые?
4) Сколько в книге номеров, у которых 4 последних цифры одинаковые, а 3 первых цифры отличаются от 4 последних?
1) Цифр – всего 10: {0;1;2;…;9}

n=10,   k=7

Количество семизначных номеров без повторений равно количеству размещений без повторений: $$ mathrm{ A_{10}^7=10cdot 9cdot 8cdot 7cdot 6cdot 5cdot 4=604800 } $$ 2) Количество всех семизначных номеров равно количеству размещений с повторениями: $$ mathrm{ overline{A}_{10}^7=10^7=10 000 000 } $$ 3) 4 последних одинаковых цифры рассматриваем как одну «склеенную» цифру;
а 7-значный номер – как 4-значный, с последней «склеенной цифрой».
Количество всех4-значных номеров равно количеству размещений с повторениями: $$ mathrm{ overline{A}_{10}^4=10^4=10 000 } $$ 4) Если 10 вариантов 4 последних цифр: {0;1;2;…;9}, тогда для каждой из 3 первых цифр остается 9 вариантов. Если 10 вариантов для 3 первых цифр, тогда для 4 последних остается 9 вариантов.
По правилу суммы и произведения общее количество таких номеров: $$ mathrm{ N=frac{9^3cdot 10+10^3cdot 9}{2}=8145 } $$ Ответ: 1) 604 800 2) 10 000 000; 3) 10 000; 4) 8145.

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

Содержание:

В комбинаторике перестановка — это упорядоченный набор без повторений чисел.

Перестановки:

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

Иными словами, это такое множество, для которого указано, какой элемент находится на первом месте, какой — на втором, …, какой — на n-м.

Формула числа перестановок Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Пример:

Количество различных шестизначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, не повторяя эти цифры в одном числе, равноКомбинаторика - правила, формулы и примеры с решением

Размещения:

Размещением из n элементов по k называется любое упорядоченное множество из k элементов, состоящее из элементов данного n-элементного множества.

Формулы для нахождения количества соединений с повторениями обязательны только для классов физико-математического профиля.

Формула числа размещений Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Пример:

Количество различных трехзначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, если цифры не могут повторяться, равно

Комбинаторика - правила, формулы и примеры с решением

Сочетания:

Сочетанием без повторений из n элементов по k называется любое k-элементное подмножество данного n-элементного множества.

Формула числа сочетаний Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением(по определению считают, чтоКомбинаторика - правила, формулы и примеры с решением

Пример:

Из 25 учащихся одного класса можно выделить пятерых для дежурства по школе Комбинаторика - правила, формулы и примеры с решениемспособами, то есть Комбинаторика - правила, формулы и примеры с решениемспособами.

Некоторые свойства числа сочетаний без повторений

Комбинаторика - правила, формулы и примеры с решением (в частности, Комбинаторика - правила, формулы и примеры с решением)

Комбинаторика - правила, формулы и примеры с решением

Схема поиска плана решения простейших комбинаторных задач:

Выбор правила:

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

Если элемент А можно выбрать т способами, а элемент В — n способами (при этом выбор элемента А исключает одновременный выбор элемента В), то А или В можно выбрать m + n способами.

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

Если элемент А можно выбрать m способами, а после этого элемент В — n способами, то А и В можно выбрать Комбинаторика - правила, формулы и примеры с решением способами.

Комбинаторика - правила, формулы и примеры с решением

Объяснение и обоснование:

Понятие соединения. Правило суммы и произведения:

При решении многих практических задач приходится выбирать из определенной совокупности объектов элементы, имеющие те или иные свойства, размещать их в определенном порядке и т. д. Поскольку в этих задачах речь идет о тех или иных комбинациях объектов, то такие задачи называют комбинаторными. Раздел математики, в котором рассматриваются методы решения комбинаторных задач, называется комбинаторикой. В комбинаторике рассматривается выбор и размещение элементов некоторого конечного множества на основании определенных условий.

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

Решение многих комбинаторных задач базируется на двух основных правилах — правиле суммы и правиле произведения.

Правило суммы. Если на тарелке лежат 5 груш и 4 яблока, то выбрать один фрукт (грушу или яблоко) можно 9 способами (5 + 4 = 9). В общем виде справедливо такое утверждение:

  • если элемент А можно выбрать m способами, а элемент В — n способами (при этом выбор элемента А исключает одновременный выбор элемента В), то А или В можно выбрать m + n способами.

Уточним содержание этого правила, используя понятие множеств и операций над ними.

Пусть множество А состоит из m элементов, а множество В -из n элементов. Если множества А и В не пересекаются (то есть Комбинаторика - правила, формулы и примеры с решением), то множество АКомбинаторика - правила, формулы и примеры с решением В состоит изКомбинаторика - правила, формулы и примеры с решениемэлементов.

Правило произведения. Если в киоске продают ручки 5 видов и тетради 4 видов, то выбрать набор из ручки и тетради (то есть пару — ручка и тетрадь) можно 5æ4 = 20 способами (поскольку с каждой из 5 ручек можно взять любую из 4 тетрадей). В общем виде имеет место такое утверждение:

  • если элемент А можно выбрать m способами, а после этого элемент В — n способами, то А и В можно выбрать Комбинаторика - правила, формулы и примеры с решением способами.

Это утверждение означает, что если для каждого из m элементов А можно взять в пару любой из n элементов В, то количество пар равно произведению Комбинаторика - правила, формулы и примеры с решением.

В терминах множеств полученный результат можно сформулировать следующим образом. Если множество А состоит из т элементов, а множество В — из n элементов, то множество всех упорядоченных пар* (а; b), где первый элемент принадлежит множеству А (а ∈ А), а второй  множеству В (b ∈ В), состоит из Комбинаторика - правила, формулы и примеры с решением элементов.

Повторяя приведенные рассуждения несколько раз (или, более строго, используя метод математической индукции), получаем, что правила суммы и произведения можно применять при выборе произвольного конечного количества элементов.

Упорядоченные множества:

При решении комбинаторных задач приходится рассматривать не только множества, в которых элементы можно записывать в любом порядке, но и так называемые упорядоченные множества. Для упорядоченных множеств существенным является порядок следования их элементов, то есть то, какой элемент записан на первом месте, какой на втором и т. д. В частности, если одни и те же элементы записать в разном порядке, то мы получим различные упорядоченные множества. Чтобы различить записи упорядоченного и неупорядоченного множеств, элементы упорядоченного множества часто записывают в круглых скобках, например (1; 2; 3) ≠ (1; 3; 2).

Рассматривая упорядоченные множества, следует учитывать, что одно и то же множество можно упорядочить по-разному. Например, множество из трех чисел {–5; 1; 3} можно упорядочить по возрастанию: (–5; 1; 3), по убыванию: (3; 1; –5), по возрастанию абсолютной величины числа: (1; 3; –5) и т. д.

* Множество всех упорядоченных пар (а; b), где первый элемент принадлежит множеству А (а ∈ А), а второй – множеству В (b ∈ В), называют декартовым произведением множеств А и В и обозначают А × В. Отметим, что декартово произведение В × А также состоит из m*n элементов.

Заметим следующее: для того чтобы задать конечное упорядоченное множество из n элементов, достаточно указать, какой элемент находится на первом месте, какой на втором, …, какой на n-м.

Размещения:

Размещением из n элементов по k называется любое упорядоченное множество из k элементов, состоящее из элементов заданного n-элементного множества.

Например, из множества, содержащего три цифры {1; 5; 7}, можно составить следующие размещения из двух элементов без повторений:

(1; 5), (1; 7), (5; 7), (5; 1), (7; 1), (7; 5).

Количество размещений из n элементов по k обозначается Комбинаторика - правила, формулы и примеры с решением (читается: «А из n по k», A — первая буква французского слова arrangement, что означает «размещение, приведение в порядок»). Как видим,Комбинаторика - правила, формулы и примеры с решением

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

Если элементы нельзя повторять, то на второе место можно выбрать только один элемент из оставшихся, то есть из n – 1 элементов. Теперь уже два элемента использованы и на третье место можно выбрать только один из n – 2 элементов и т. д. На k-е место можно выбрать только один из n – (k –1) = n – k +1 элементов (см. рис. 21.1).

Комбинаторика - правила, формулы и примеры с решением

Поскольку требуется выбрать элементы и на первое место, и на второе, …, и на k-е, то используем правило произведения и получим следующую формулу числа размещений из n элементов по k:

Комбинаторика - правила, формулы и примеры с решением

Например, Комбинаторика - правила, формулы и примеры с решением (что совпадает с соответствующим значением, полученным выше). Аналогично можно обосновать формулу для нахождения числа размещений с повторениями. При решении простейших комбинаторных задач важно правильно выбрать формулу, по которой будут проводиться вычисления. Для этого нужно выяснить следующее:

  1. Учитывается ли порядок следования элементов в соединении?
  2. Все ли заданные элементы входят в полученное соединение?

Если, например, порядок следования элементов учитывается и из n данных элементов в соединении используется только k элементов, то по определению это — размещение из n элементов по k.

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

Примеры решения задач:

Пример:

На соревнования по легкой атлетике приехала команда из 12 спортсменок. Сколькими способами тренер может определить, кто из них побежит в эстафете 4 × 100 м на первом, втором, третьем и четвертом этапах?

Решение:

Количество способов выбрать из 12 спортсменок четырех для участия в эстафете равно количеству размещений из 12 элементов по 4 (без повторений), то есть Комбинаторика - правила, формулы и примеры с решением

Комментарий:

Для выбора формулы выясняем ответы на вопросы, приведенные выше. Поскольку для спортсменок важно, в каком порядке они будут бежать, то порядок при выборе элементов учитывается. В полученное соединение входят не все 12 заданных элементов. Следовательно, соответствующее соединение — размещение из 12 элементов по 4 (без повторений, поскольку каждая спортсменка может бежать только на одном этапе эстафеты).

Пример:

Найдите количество трехзначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, 7, если цифры в числе не повторяются.

Решение:

Количество трехзначных чисел, которые можно составить из семи цифр 1, 2, 3, 4, 5, 6, 7, равно числу размещений из 7 элементов по 3, то естьКомбинаторика - правила, формулы и примеры с решением

Комментарий:

Для выбора формулы выясняем, что для чисел, которые мы будем составлять, порядок следования цифр учитывается и не все элементы выбираются (только 3 из заданных семи). Следовательно, соответствующее соединение — размещение из 7 элементов по 3 (без повторений).

Пример:

Найдите количество трехзначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, 0, если цифры в числе не повторяются.

Комментарий:

Выбор формулы проводится таким же образом, как и в задаче 2. Следует учесть, что если число, составленное из трех цифр, начинается цифрой 0, то оно не считается трехзначным. Следовательно, для ответа на вопрос задачи можно сначала из заданных 7 цифр записать все числа, состоящие из 3 цифр (см. задачу 2). Затем из количества полученных чисел вычесть количество чисел, составленных из трех цифр, но начинающихся цифрой 0. В последнем случае мы фактически будем из всех цифр без нуля (их 6) составлять двузначные числа. Тогда их количество равно числу размещений из 6 элементов по 2 (см. решение).

Можно выполнить также непосредственное вычисление, последовательно заполняя три места в трехзначном числе и используя правило произведения. В этом случае для наглядности удобно изображать соответствующие разряды в трехзначном числе в виде клеточек, например так:

Комбинаторика - правила, формулы и примеры с решением

Решение:

Количество трехзначных чисел, которые можно составить из семи цифр (среди которых нет цифры 0), если цифры в числе не повторяются, равно числу размещений из 7 элементов по 3, то есть Комбинаторика - правила, формулы и примеры с решением

Но среди данных цифр есть цифра 0, с которой не может начинаться трехзначное число. Поэтому из размещений из 7 элементов по 3 необходимо исключить те размещения, в которых первым элементом является цифра 0. Их количество равно числу размещений из 6 элементов по 2, то есть Комбинаторика - правила, формулы и примеры с решением Следовательно, искомое количество трехзначных чисел равно Комбинаторика - правила, формулы и примеры с решением

Пример:

Решите уравнениеКомбинаторика - правила, формулы и примеры с решением

Решение:

ОДЗ: x ∈ N, Комбинаторика - правила, формулы и примеры с решением. Тогда получаем: Комбинаторика - правила, формулы и примеры с решением

На ОДЗ это уравнение равносильно уравнениям:

(x – 2) (x – 3) = 6,

x2 – 5x = 0,

x (x – 5) = 0.

Тогда x = 0 или x = 5. В ОДЗ входит только x = 5.

Ответ: 5.

Комментарий:

Уравнения, в запись которых входят выражения, обозначающие количество соответствующих соединений из x элементов, считаются определенными только при натуральных значениях переменной x. Чтобы выражение Комбинаторика - правила, формулы и примеры с решением имело смысл, следует выбирать натуральные значения Комбинаторика - правила, формулы и примеры с решением(в этом случае Комбинаторика - правила, формулы и примеры с решением также существует и, конечно, Ax 2 ≠ 0). Для преобразования уравнения используем формулы:Комбинаторика - правила, формулы и примеры с решением

Объяснение и обоснование:

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

Напомним, что упорядоченное множество — это такое множество, для которого указано, какой элемент находится на первом месте, какой на втором, …, какой на n-м.

Например, переставляя цифры в числе 236 (в котором множество цифр {2; 3; 6} уже упорядоченное), можно составить такие перестановки без повторений: (2; 3; 6), (2; 6; 3), (3; 2; 6), (3; 6; 2), (6; 2; 3), (6; 3; 2) — всего 6 перестановок* .

Количество перестановок без повторений из n элементов обозначается Комбинаторика - правила, формулы и примеры с решением (P — первая буква французского слова permutation — перестановка). Как видим, Комбинаторика - правила, формулы и примеры с решением= 6.

Фактически перестановки без повторений из n элементов являются размещениями из n элементов по n без повторений, поэтомуКомбинаторика - правила, формулы и примеры с решением ПроизведениеКомбинаторика - правила, формулы и примеры с решением обозначается n!. Поэтому полученная формула числа перестановок без повторений из n элементов может быть записана следующим образом:

Комбинаторика - правила, формулы и примеры с решением

*Отметим, что каждая из перестановок определяет трехзначное число, составленное из цифр 2, 3, 6 таким образом, что цифры в числе не повторяются.

Например,Комбинаторика - правила, формулы и примеры с решением (что совпадает с соответствующим значением, полученным выше).

С помощью факториалов формулу для числа размещений без повторений

Комбинаторика - правила, формулы и примеры с решением(1)

запишем в другом виде. Для этого умножим и разделим выражение в формуле (1) на произведение Комбинаторика - правила, формулы и примеры с решением тогда

Комбинаторика - правила, формулы и примеры с решением

Следовательно, формула числа размещений без повторений из n элементов по k может быть записана так:

Комбинаторика - правила, формулы и примеры с решением (2)

Для того чтобы этой формулой можно было пользоваться при всех значениях k, в частности при k = n – 1 и k = n, договорились считать, что

1! = 1 и 0! = 1.

Например, по формуле (2) Комбинаторика - правила, формулы и примеры с решением

Обратим внимание, что в тех случаях, когда значение n! оказывается очень большим, ответы оставляют записанными с помощью факториалов. Например,Комбинаторика - правила, формулы и примеры с решением

Примеры решения задач:

Для выбора формулы при решении простейших комбинаторных задач достаточно выяснить следующее:

  1. Учитывается ли порядок следования элементов в соединении?
  2. Все ли заданные элементы входят в полученное соединение?

Если, например, порядок следования элементов учитывается и все n заданных элементов используются в соединении, то по определению это перестановки из n элементов.

Пример:

Найдите, сколькими способами можно восемь учащихся построить в колонну по одному.

Решение:

Количество способов равно числу перестановок из 8 элементов, то есть Комбинаторика - правила, формулы и примеры с решением

Комментарий:

Для выбора соответствующей формулы выясняем ответы на вопросы, приведенные выше. Поскольку порядок следования элементов учитывается и все 8 заданных элементов выбираются, то искомые соединения — это перестановки из 8 элементов без повторений. Их количество можно вычислить по формуле Комбинаторика - правила, формулы и примеры с решением

Пример:

Найдите количество различных четырехзначных чисел, которые можно составить из цифр 0, 3, 7, 9 (цифры в числе не повторяются).

Решение:

Из четырех цифр 0, 3, 7, 9, не повторяя заданные цифры, можно получить Комбинаторика - правила, формулы и примеры с решением перестановок. Перестановки, начинающиеся с цифры 0, не являются записью четырехзначного числа — их количество Комбинаторика - правила, формулы и примеры с решением. Тогда искомое количество четырехзначных чисел равноКомбинаторика - правила, формулы и примеры с решением

Комментарий:

Поскольку порядок следования элементов учитывается и для получения четырехзначного числа надо использовать все элементы, то искомые соединения — это перестановки из 4 элементов. Их количество — Комбинаторика - правила, формулы и примеры с решением. При этом необходимо учесть, что в четырехзначном числе на первом месте не может стоять цифра 0. Таких чисел будет столько, сколько раз мы сможем выполнить перестановки из 3 оставшихся цифр, то есть Комбинаторика - правила, формулы и примеры с решением

Пример:

Имеется десять книг, из которых четыре — учебники. Сколькими способами можно поставить эти книги на полку так, чтобы все учебники стояли рядом?

Решение:

Сначала будем рассматривать учебники как одну книгу. Тогда на полке надо расставить не 10, а 7 книг. Это можно сделать Комбинаторика - правила, формулы и примеры с решениемспособами. В каждом из полученных наборов книг можно выполнить еще Комбинаторика - правила, формулы и примеры с решениемперестановок учебников. По правилу умножения искомое количество способов равноКомбинаторика - правила, формулы и примеры с решением

Комментарий:

Задачу можно решать в два этапа. На первом будем условно считать все учебники одной книгой.

Тогда получим 7 книг (6 не учебников + 1 условная книга — учебник). Порядок следования элементов учитывается и используются все элементы (поставить на полку необходимо все книги). Следовательно, соответствующие соединения — это перестановки из 7 элементов. Их количество — Комбинаторика - правила, формулы и примеры с решением.

На втором этапе решения будем переставлять между собой только учебники. Это можно сделать Комбинаторика - правила, формулы и примеры с решениемспособами. Поскольку нам надо переставить и учебники, и другие книги, то используем правило произведения.

Объяснение и обоснование:

1. Сочетания без повторений:

Сочетанием без повторений из n элементов по k называется любое k-элементное подмножество заданного n-элементного множества.

Например, из множества {a, b, c, d} можно составить следующие сочетания без повторений из трех элементов: {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}.

Количество сочетаний без повторений из n элементов по k элементов обозначается символом Комбинаторика - правила, формулы и примеры с решением (читается: «число сочетаний из п по k» или «це из п по k», С — первая буква французского слова combinaison — сочетание). Как видим, Комбинаторика - правила, формулы и примеры с решением

Выясним, сколько всего можно составить сочетаний без повторений из n элементов по k. Для этого используем известные нам формулы числа размещений и перестановок. Составление размещения без повторений из n элементов по k проведем в два этапа. Сначала выберем k разных элементов из заданного n-элементного множества, не учитывая порядок выбора этих элементов (то есть выберем kэлементное подмножество из n-элементного множества — сочетание без повторений из n-элементов по k). По нашему обозначению это можно сделать Комбинаторика - правила, формулы и примеры с решением способами. После этого полученное множество из k разных элементов упорядочим. Его можно упорядочить Комбинаторика - правила, формулы и примеры с решениемспособами. Получим размещения без повторений из n элементов по k. Следовательно, количество размещений без повторений из n элементов по k в k! раз больше числа сочетаний без повторений из n элементов по k, то естьКомбинаторика - правила, формулы и примеры с решениемОтсюда Комбинаторика - правила, формулы и примеры с решением Учитывая, что по формуле (2) Комбинаторика - правила, формулы и примеры с решением, получаем:

Комбинаторика - правила, формулы и примеры с решением(3)

Например, Комбинаторика - правила, формулы и примеры с решением что совпадает со значением, полученным выше.

Используя формулу (3), можно легко обосновать свойство 1 числа сочетаний без повторений, приведенное в табл. 28.

1) Поскольку Комбинаторика - правила, формулы и примеры с решением то

Комбинаторика - правила, формулы и примеры с решением(4)

Для того чтобы формулу (4) можно было использовать и при k = n, договорились считать, что Комбинаторика - правила, формулы и примеры с решениемТогдаКомбинаторика - правила, формулы и примеры с решением

Заметим, что формулу (4) можно получить без вычислений с помощью достаточно простых комбинаторных рассуждений.

Когда мы выбираем k предметов из n, то n – k предметов мы оставляем. Если же, напротив, выбранные предметы оставим, а другие n – k -выберем, то получим способ выбора n – k предметов из n. Мы получили взаимно-однозначное соответствие способов выбора k и n – k предметов из n. Значит, количество одних и других способов одинаково. Но количество одних — Комбинаторика - правила, формулы и примеры с решением , а других Комбинаторика - правила, формулы и примеры с решением , поэтому Комбинаторика - правила, формулы и примеры с решением .

Если в формуле (3) сократить числитель и знаменатель на (n – k)!, то получим формулу, по которой удобно вычислять Комбинаторика - правила, формулы и примеры с решением при малых значениях k:

Комбинаторика - правила, формулы и примеры с решением(5)

Например,Комбинаторика - правила, формулы и примеры с решением

2. Вычисление числа сочетаний без повторений с помощью треугольника Паскаля:

Для вычисления числа сочетаний без повторений можно применять формулу (3): Комбинаторика - правила, формулы и примеры с решением, а можно последовательно вычислять соответствующие значения, пользуясь следующим свойством:

Комбинаторика - правила, формулы и примеры с решением (6)

Для обоснования равенства (6) можно записать суммуКомбинаторика - правила, формулы и примеры с решением, используя формулу (3), и после приведения полученных дробей к общему знаменателю получить формулу для правой части равенства (6) (проделайте это самостоятельно). Также формулу (6) можно получить без вычислений с помощью комбинаторных рассуждений.

Комбинаторика - правила, формулы и примеры с решением– это количество способов выбрать k +1 предмет из n + 1. Подсчитаем это количество, зафиксировав один предмет (назовем его «фиксированным»). Если мы не берем фиксированный предмет, то нам нужно выбрать k +1 предмет из n тех, что остались, а если мы его берем, то нужно выбрать из n тех, что остались, еще k предметов. Первое можно сделать Комбинаторика - правила, формулы и примеры с решением способами, второеКомбинаторика - правила, формулы и примеры с решениемспособами. Всего как раз Комбинаторика - правила, формулы и примеры с решением способов, следовательно,

Комбинаторика - правила, формулы и примеры с решением

Это равенство позволяет последовательно вычислять значения Комбинаторика - правила, формулы и примеры с решением с помощью специальной таблицы, которая называется треугольником Паскаля. Если считать, что Комбинаторика - правила, формулы и примеры с решением, то он будет иметь вид, представленный в табл. 29.

Комбинаторика - правила, формулы и примеры с решением

Каждая строка этой таблицы начинается с единицы и заканчивается единицейКомбинаторика - правила, формулы и примеры с решением

Если какая-либо строка уже заполнена, например третья, то в четвертой строке надо записать на первом месте единицу. На втором месте запишем число, равное сумме двух чисел третьей строки, стоящих над ним левее и правее (поскольку по формуле (6) Комбинаторика - правила, формулы и примеры с решением На третьем месте запишем число, равное сумме двух следующих чисел третьей строки, стоящих над ним левее и правееКомбинаторика - правила, формулы и примеры с решением , и т. д. (а на последнем месте снова запишем единицу).

Примеры решения задач:

Обратим внимание, что, как и раньше, для выбора формулы при решении простейших комбинаторных задач достаточно ответить на вопросы:

  1. Учитывается ли порядок следования элементов в соединении?
  2. Все ли заданные элементы входят в полученное соединение?

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

Пример:

Из 12 членов туристической группы надо выбрать трех дежурных. Сколькими способами можно сделать этот выбор?

Решение:

Количество способов выбрать из 12 туристов трех дежурных равно количеству сочетаний из 12 элементов по 3 (без повторений), то естьКомбинаторика - правила, формулы и примеры с решением

Комментарий:

Для выбора соответствующей формулы выясняем ответы на вопросы, приведенные выше. Поскольку порядок следования элементов не учитывается (для дежурных неважно, в каком порядке их выберут), то соответствующее соединение является сочетанием из 12 элементов по 3 (без повторений). Для вычисления можно использовать формулы (3) или (5), в данном случае применяем формулу (3):Комбинаторика - правила, формулы и примеры с решением

Пример:

Из вазы с фруктами, в которой лежат 10 разных яблок и 5 разных груш, требуется выбрать 2 яблока и 3 груши. Сколькими способами можно сделать такой выбор?

Решение:

Выбрать 2 яблока из 10 можно Комбинаторика - правила, формулы и примеры с решением способами. При каждом выборе яблок груши можно выбратьКомбинаторика - правила, формулы и примеры с решением способами. Тогда по правилу произведения выбор требуемых фруктов можно выполнить Комбинаторика - правила, формулы и примеры с решением способами. ПолучаемКомбинаторика - правила, формулы и примеры с решением

Комментарий:

Сначала отдельно выберем 2 яблока из 10 и 3 груши из 5.

Поскольку при выборе яблок или груш порядок следования элементов не учитывается, то соответствующие соединения — сочетания без повторений.

Учитывая, что требуется выбрать 2 яблока и 3 груши, используем правило произведения и перемножим полученные возможности выбора яблок Комбинаторика - правила, формулы и примеры с решением и груш Комбинаторика - правила, формулы и примеры с решением

Бином Ньютона:

Комбинаторика - правила, формулы и примеры с решением

Поскольку Комбинаторика - правила, формулы и примеры с решением (при x ≠ 0 и a ≠ 0), то формулу бинома Ньютона можно записать еще и так:

Комбинаторика - правила, формулы и примеры с решением

Общий член разложения степени бинома имеет вид

Комбинаторика - правила, формулы и примеры с решением(где Комбинаторика - правила, формулы и примеры с решением). КоэффициентыКомбинаторика - правила, формулы и примеры с решением называют биномиальными коэффициентaми.

Свойства биномиальных коэффициентов:

  1. Число биномиальных коэффициентов (а следовательно, и число слагаемых) в разложении n-й степени бинома равно n + 1.
  2. Коэффициенты членов, равноудаленных от начала и конца разложения, равны между собой (поскольку Комбинаторика - правила, формулы и примеры с решением )
  3. Сумма всех биномиальных коэффициентов равна Комбинаторика - правила, формулы и примеры с решением Комбинаторика - правила, формулы и примеры с решением
  4. Сумма биномиальных коэффициентов, стоящих на четных местах, равна сумме биномиальных коэффициентов, стоящих на нечетных местах.
  5. Для вычисления биномиальных коэффициентов можно воспользоваться треугольником Паскаля, в котором вычисления коэффициентов основываются на формуле Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Объяснение и обоснование:

Бином Ньютона:

Двучлен вида a + x также называют биномом. Из курса алгебры известно, что:

Комбинаторика - правила, формулы и примеры с решением

Можно заметить, что коэффициенты разложения степени бинома Комбинаторика - правила, формулы и примеры с решением при n = 1, 2, 3 совпадают с числами в соответствующей строке треугольника Паскаля. Оказывается, что это свойство выполняется для любого натурального n, то есть справедлива формула

Комбинаторика - правила, формулы и примеры с решением (7)

Формулу (7) называют биномом Ньютона. Правая часть этого равенства называется разложением степени биномаКомбинаторика - правила, формулы и примеры с решением, а числа Комбинаторика - правила, формулы и примеры с решением (при k = 0, 1, 2, …, n) называют биномиальными коэффициентами.

Общий член разложения степени бинома имеет вид

Комбинаторика - правила, формулы и примеры с решением

Обосновать формулу (7) можно, например, с помощью метода математической индукции. (Проведите такое обоснование самостоятельно.)

Приведем также комбинаторные рассуждения для обоснования формулы бинома Ньютона.

По определению степени с натуральным показателем Комбинаторика - правила, формулы и примеры с решениемКомбинаторика - правила, формулы и примеры с решением (всего n скобок). Раскрывая скобки, получаем в каждом слагаемом произведение n букв, каждая из которых – а или х. Если, например, в каком-либо слагаемом количество букв x равно k, то количество букв а в нем — n – k, то есть каждое слагаемое имеет вид Комбинаторика - правила, формулы и примеры с решением при некотором k от 0 до n. Покажем, что для каждого такого k число слагаемых anКомбинаторика - правила, формулы и примеры с решениемравноКомбинаторика - правила, формулы и примеры с решением , откуда после приведения подобных членов и получаем формулу бинома. Произведение Комбинаторика - правила, формулы и примеры с решением получаем, взяв букву x из k скобок и букву а из n – k тех скобок, которые остались. Разные такие слагаемые получим путем разного выбора первых k скобок, а k скобок из n можно выбрать именно Комбинаторика - правила, формулы и примеры с решением способами. Следовательно, общий член разложения биномаКомбинаторика - правила, формулы и примеры с решением действительно имеет вид Комбинаторика - правила, формулы и примеры с решением где k = 0, 1, 2, …, n.

Именно из-за бинома Ньютона числа Комбинаторика - правила, формулы и примеры с решением часто называют биномиальными коэффициентами.

Записывая степень двучлена по формуле бинома Ньютона для небольших значений n, биномиальные коэффициенты можно вычислять с помощью треугольника Паскаля (см. табл. 30).

Например, Комбинаторика - правила, формулы и примеры с решением

Так как Комбинаторика - правила, формулы и примеры с решением, формулу бинома Ньютона можно записать в виде:

Комбинаторика - правила, формулы и примеры с решением (8)

Если в формуле бинома Ньютона (8) заменить x на (–x), то получим формулу возведения в степень разности a – x:

Комбинаторика - правила, формулы и примеры с решением

Например, Комбинаторика - правила, формулы и примеры с решением (знаки членов разложения чередуются!).

Свойства биномиальных коэффициентов:

  1. Число биномиальных коэффициентов (а следовательно, и число слагаемых) в разложении n-й степени бинома равно n + 1, поскольку разложение содержит все степени x от 0 до n (и других слагаемых не содержит).
  2. Коэффициенты членов, равноудаленных от начала и конца разложения, равны между собой, поскольку Комбинаторика - правила, формулы и примеры с решением
  3. Сумма всех биномиальных коэффициентов равнаКомбинаторика - правила, формулы и примеры с решением

Для обоснования полагаем в равенстве (7) значения a = x = 1 и получаем:

Комбинаторика - правила, формулы и примеры с решением

Например, Комбинаторика - правила, формулы и примеры с решением

4. Сумма биномиальных коэффициентов, стоящих на четных местах, равна сумме биномиальных коэффициентов, стоящих на нечетных местах.

Для обоснования возьмем в равенстве (7) значения a = 1, x = –1:

Комбинаторика - правила, формулы и примеры с решением

Тогда Комбинаторика - правила, формулы и примеры с решением

Примеры решения задач:

Пример:

По формуле бинома Ньютона найдите разложение степениКомбинаторика - правила, формулы и примеры с решением.

Комментарий:

Для нахождения коэффициентов разложения можно использовать треугольник Паскаля (табл. 30) или вычислять их по общей формуле. По треугольнику Паскаля коэффициенты равны: 1, 6, 15, 20, 15, 6, 1. Учитывая, что при возведении разности в степень знаки членов разложения чередуются, получаем:

Комбинаторика - правила, формулы и примеры с решением

Для упрощения записи ответа можно избавиться от иррациональности в знаменателях полученных выражений (см. решение) или сначала учесть, что ОДЗ данного выражения: x > 0. Тогда Комбинаторика - правила, формулы и примеры с решением то есть данное выражение можно записать так: Комбинаторика - правила, формулы и примеры с решением и возвести в степень последнее выражение.

Решение:

Комбинаторика - правила, формулы и примеры с решением

Пример:

В разложении степени Комбинаторика - правила, формулы и примеры с решением найдите член, содержащий Комбинаторика - правила, формулы и примеры с решением

Решение:

ОДЗ: b > 0. Тогда

Комбинаторика - правила, формулы и примеры с решением.

Общий член разложения: Комбинаторика - правила, формулы и примеры с решением

По условию член разложения должен содержать Комбинаторика - правила, формулы и примеры с решением, следовательно, Комбинаторика - правила, формулы и примеры с решением Отсюда k = 6.

Тогда член разложения, содержащий Комбинаторика - правила, формулы и примеры с решением, равен

Комбинаторика - правила, формулы и примеры с решением

Комментарий:

На ОДЗ (b > 0) каждое слагаемое в данном двучлене можно записать как степень с дробным показателем. Это позволит проще записать общий член разложения степени Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

(где k = 0, 1, 2, …, n), выяснить, какой из членов разложения содержит Комбинаторика - правила, формулы и примеры с решением и записать его. Чтобы упростить запись общего члена разложения, запишем:

Комбинаторика - правила, формулы и примеры с решением

Всё о комбинаторике

Пусть имеется несколько множеств элементов:

Комбинаторика - правила, формулы и примеры с решением

Вопрос: сколькими способами можно составить новое множество Комбинаторика - правила, формулы и примеры с решениемвзяв из каждого исходного множества по одному элементу? Ответ на этот вопрос дают следующие рассуждения.

Элемент Комбинаторика - правила, формулы и примеры с решением из первого множества можно выбрать Комбинаторика - правила, формулы и примеры с решением способами, элемент Комбинаторика - правила, формулы и примеры с решением из второго – s способами, элемент с можно выбрать Комбинаторика - правила, формулы и примеры с решением способами и т. д. Пару элементов Комбинаторика - правила, формулы и примеры с решением можно составить Комбинаторика - правила, формулы и примеры с решением• s способами. Это следует из табл. 1.1, в которой перечислены все способы такого выбора.

Комбинаторика - правила, формулы и примеры с решением

Способы выбора трех элементов аbc перечислены в табл. 1.2.

Комбинаторика - правила, формулы и примеры с решением

В этой таблице Комбинаторика - правила, формулы и примеры с решением строк и Комбинаторика - правила, формулы и примеры с решениемs столбцов. Поэтому искомое число способов выбора трех элементов аbc равно Комбинаторика - правила, формулы и примеры с решениемКомбинаторика - правила, формулы и примеры с решением. Продолжая рассуждать подобным образом, получим следующее утверждение.

Основной комбинаторный принцип. Если некоторый первый выбор можно сделать Комбинаторика - правила, формулы и примеры с решением способами, для каждого первого выбора некоторый второй можно сделать s способами, для каждой пары первых двух – третий выбор можно сделать Комбинаторика - правила, формулы и примеры с решением способами и т.д., то число способов для последовательности таких выборов равно Комбинаторика - правила, формулы и примеры с решениемКомбинаторика - правила, формулы и примеры с решением….

Комбинаторные формулы в прикладных задачах теории вероятностей обычно связывают с выбором Комбинаторика - правила, формулы и примеры с решением элементов («выборкой объема Комбинаторика - правила, формулы и примеры с решением») из совокупности, состоящей из Комбинаторика - правила, формулы и примеры с решением элементов (элементов «генеральной совокупности»). Различают два способа выбора:

  • а)    повторный выбор, при котором выбранный элемент возвращается в генеральную совокупность и может быть выбран вновь;
  • б)    бесповторный выбор, при котором выбранный элемент в совокупность не возвращается и выборка не содержит повторяющихся элементов.

При повторном выборе каждый по порядку элемент может быть выбран Комбинаторика - правила, формулы и примеры с решением способами. Согласно комбинаторному принципу, такую выборку можно сделать Комбинаторика - правила, формулы и примеры с решением способами. Например, повторную выборку объема 2 из трех элементов Комбинаторика - правила, формулы и примеры с решениемможно сделать 32 =9 способами: Комбинаторика - правила, формулы и примеры с решением Комбинаторика - правила, формулы и примеры с решением

В случае бесповторной выборки первый элемент можно выбрать Комбинаторика - правила, формулы и примеры с решением способами, для второго остается Комбинаторика - правила, формулы и примеры с решением возможность выбора, третий элемент можно выбрать Комбинаторика - правила, формулы и примеры с решением способами и т.д. Элемент выборки с номером Комбинаторика - правила, формулы и примеры с решением можно выбрать Комбинаторика - правила, формулы и примеры с решением способом. Согласно комбинаторному принципу, общее число бесповторных выборок объема Комбинаторика - правила, формулы и примеры с решением равно

Комбинаторика - правила, формулы и примеры с решением

Число Комбинаторика - правила, формулы и примеры с решением называют числом размещений из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением.

Например, существует Комбинаторика - правила, формулы и примеры с решением размещений из трех элементов Комбинаторика - правила, формулы и примеры с решением по два: Комбинаторика - правила, формулы и примеры с решением Отметим, что и в первом случае и во втором выборки отличаются либо составом элементов, либо порядком выбора элементов.

Выделим особо случай, когда один за другим выбраны все Комбинаторика - правила, формулы и примеры с решением элементов. В этом случае выборки имеют один и тот же состав (все Комбинаторика - правила, формулы и примеры с решением элементов) и отличаются только порядком выбора элементов. Поэтому число

Комбинаторика - правила, формулы и примеры с решением

называют числом перестановок из Комбинаторика - правила, формулы и примеры с решением элементов.

Например, пять человек могут встать в очередь Комбинаторика - правила, формулы и примеры с решением способами. Три элемента Комбинаторика - правила, формулы и примеры с решением можно переставить Комбинаторика - правила, формулы и примеры с решением способами: Комбинаторика - правила, формулы и примеры с решением

Подсчитаем количество бесповторных выборок объема Комбинаторика - правила, формулы и примеры с решением, которые отличаются друг от друга только составом элементов. Пусть X — число таких выборок. Для каждого набора из Комбинаторика - правила, формулы и примеры с решением элементов можно выбрать порядок их расположения Комбинаторика - правила, формулы и примеры с решениемспособами. Тогда Комбинаторика - правила, формулы и примеры с решением равно числу способов выбрать Комбинаторика - правила, формулы и примеры с решением различных элементов и выбрать порядок их расположения, т.е. равно числу размещений из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением:

Комбинаторика - правила, формулы и примеры с решением

Это число называют числом сочетаний из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением и обозначают через Комбинаторика - правила, формулы и примеры с решением Если в формуле (1.2) умножить числитель и знаменатель на Комбинаторика - правила, формулы и примеры с решением, то

Комбинаторика - правила, формулы и примеры с решением

Например, сочетаний из четырех элементов Комбинаторика - правила, формулы и примеры с решением по два существует Комбинаторика - правила, формулы и примеры с решением. Это Комбинаторика - правила, формулы и примеры с решением

Так как из Комбинаторика - правила, формулы и примеры с решением элементов выбрать Комбинаторика - правила, формулы и примеры с решением элементов можно единственным образом, то Комбинаторика - правила, формулы и примеры с решением откуда следует, что Комбинаторика - правила, формулы и примеры с решением

Величины Комбинаторика - правила, формулы и примеры с решением называют биномиальными коэффициентами. Название связано с формулой бинома Ньютона

Комбинаторика - правила, формулы и примеры с решением

Из формулы (1.3) следует, что

Комбинаторика - правила, формулы и примеры с решением

Биномиальные коэффициенты образуют так называемый треугольник Паскаля, который имеет вид:

Комбинаторика - правила, формулы и примеры с решением

В Комбинаторика - правила, формулы и примеры с решением-й строке треугольника Паскаля располагаются коэффициенты, соответствующие представлению Комбинаторика - правила, формулы и примеры с решением по формуле (1.3). Треугольником удобно пользоваться для нахождения значений Комбинаторика - правила, формулы и примеры с решением. Это значение находится на пересечении Комбинаторика - правила, формулы и примеры с решением-й строки и Комбинаторика - правила, формулы и примеры с решением-го наклонного ряда. Например, Комбинаторика - правила, формулы и примеры с решением

Биномиальные коэффициенты обладают свойством симметрии:

Комбинаторика - правила, формулы и примеры с решением

Это наглядно демонстрирует треугольник Паскаля. Равенство (1.4) подтверждает тот очевидный факт, что выбор Комбинаторика - правила, формулы и примеры с решением элементов из n равносилен выбору тех Комбинаторика - правила, формулы и примеры с решениемКомбинаторика - правила, формулы и примеры с решением элементов из Комбинаторика - правила, формулы и примеры с решением, которые следует удалить, чтобы остались Комбинаторика - правила, формулы и примеры с решением элементов.

При повторном выборе из Комбинаторика - правила, формулы и примеры с решением элементов число выборок объема Комбинаторика - правила, формулы и примеры с решением, которые отличаются только составом равно Комбинаторика - правила, формулы и примеры с решением Еще раз подчеркнем, что речь идет о выборках, которые отличаются хотя бы одним элементом, а порядок выбора этих элементов во внимание не принимается. Число таких выборок можно подсчитать следующим образом. Между элементами Комбинаторика - правила, формулы и примеры с решением поставим разграничительные знаки, например, нули: Комбинаторика - правила, формулы и примеры с решением Таких знаков (нулей) понадобится Комбинаторика - правила, формулы и примеры с решением. На месте каждого элемента поставим столько единиц, сколько раз предполагается выбрать этот элемент. Например, комбинация Комбинаторика - правила, формулы и примеры с решением  означает, что элемент Комбинаторика - правила, формулы и примеры с решением выбран четыре раза, элемент Комбинаторика - правила, формулы и примеры с решением выбран один раз, элемент Комбинаторика - правила, формулы и примеры с решением не выбран, …, элемент Комбинаторика - правила, формулы и примеры с решением выбран два раза. Заметим, что в такой записи число единиц равно объему выборки Комбинаторика - правила, формулы и примеры с решением. Для перебора всех возможных комбинаций нужно из Комбинаторика - правила, формулы и примеры с решением мест выбрать Комбинаторика - правила, формулы и примеры с решением место и поставить на них нули, а на остальных местах разместить единицы. Это можно сделать способами.

Комбинаторика - правила, формулы и примеры с решением

Совокупность из Комбинаторика - правила, формулы и примеры с решением элементов разделить на Комбинаторика - правила, формулы и примеры с решением групп по Комбинаторика - правила, формулы и примеры с решением элементов соответственно Комбинаторика - правила, формулы и примеры с решением можно Комбинаторика - правила, формулы и примеры с решением способами. Порядок элементов внутри каждой из этих Комбинаторика - правила, формулы и примеры с решением групп не имеет значения.

Пусть Комбинаторика - правила, формулы и примеры с решением – множества, число элементов в каждом из которых равно соответственно Комбинаторика - правила, формулы и примеры с решением Составить множество B из Комбинаторика - правила, формулы и примеры с решением элементов множества А1, Комбинаторика - правила, формулы и примеры с решением элементов множества А2, …, Комбинаторика - правила, формулы и примеры с решением элементов множества Аk, можно, согласно основному комбинаторному принципу, способами.

Комбинаторика - правила, формулы и примеры с решением

Для безошибочного выбора комбинаторной формулы достаточно последовательно ответить на вопросы в следующей схеме:

Комбинаторика - правила, формулы и примеры с решением

Например, число словарей, необходимых для непосредственного перевода с одного на другой, для пяти языков определяется из следующих рассуждений. Для составления словаря выбираем из пяти языков (Комбинаторика - правила, формулы и примеры с решением= 5) любые два (Комбинаторика - правила, формулы и примеры с решением=2). Выбор бесповторный, причем при выборе важен и состав выбора и порядок выбора. Поэтому искомое число словарей равно Комбинаторика - правила, формулы и примеры с решением

Комбинаторные задачи с решением

Комбинаторика – раздел математики, занимающийся вопросом выбора и расположения элементов некоторого конечного множества в соответствии с заданными условиями.

Рассмотрим примеры задач комбинаторики.

Пример №1

Сколькими способами можно выбрать путь из начала координат 0(0,0) в точку В(6,4), если каждый шаг равен единице, но его можно совершать только вправо или вверх? Сколько таких путей проходит через точку А(2,3)?

Решение. Весь путь занимает 10 шагов (четыре вверх и шесть вправо). Для планирования пути следует решить, какие именно по счету четыре шага следует сделать вверх, а остальные шесть — вправо. Выбор бесповторный и нас интересует только состав выбора. Поэтому в описанных условиях всего путей из точки О в точку В будет Комбинаторика - правила, формулы и примеры с решением

Рассуждая подобным образом легко видеть, что путей из точки О в точку А существует Комбинаторика - правила, формулы и примеры с решением а путь из точки А в точку В можно выбрать Комбинаторика - правила, формулы и примеры с решением способами. По комбинаторному принципу всего путей через точку А существует 10 • 5 = 50.

Ответ. 210; 50.

Пример №2

Сколькими способами можно выбрать путь из начала координат 0(0,0) в точку Комбинаторика - правила, формулы и примеры с решением если каждый шаг равен 1, но его можно совершать только вправо или вверх? Сколько таких путей проходит через точку Комбинаторика - правила, формулы и примеры с решением (См. пример 1.1 и исходные данные.)

Исходные данные к задаче 1.1.

Комбинаторика - правила, формулы и примеры с решением

Пример №3

В городе с идеальной прямоугольной планировкой (сеть улиц в этом городе изображена на рис. 1.1) из пункта А выходят Комбинаторика - правила, формулы и примеры с решением человек. Половина из них идет по направлению Комбинаторика - правила, формулы и примеры с решением половина — по направлению Комбинаторика - правила, формулы и примеры с решением Дойдя до первого перекрестка, каждая группа разделяется так, что половина ее идет по направлению Комбинаторика - правила, формулы и примеры с решением половина — по направлению Комбинаторика - правила, формулы и примеры с решением Такое же разделение происходит на каждом перекрестке. Требуется перечислить перекрестки, на которых окажутся люди после прохождения N улиц (отрезков на рис. 1.1), и сколько людей окажется на каждом из этих перекрестков.

Комбинаторика - правила, формулы и примеры с решением

Решение. Каждый человек пройдет N улиц и окажется на одном из перекрестков Комбинаторика - правила, формулы и примеры с решениемКоординаты перекрестков указаны в предположении, что точка А служит началом координат.

На каждом перекрестке для каждого человека производится выбор из двух возможностей: идти в направлении Комбинаторика - правила, формулы и примеры с решением или в направлении Комбинаторика - правила, формулы и примеры с решением Поэтому всего возможных путей будет Комбинаторика - правила, формулы и примеры с решением . Из этого следует, что каждый путь пройдет только один человек.

В пункте Комбинаторика - правила, формулы и примеры с решением окажется столько человек, сколько различных путей ведет в этот пункт из точки А . Чтобы попасть в пункт Комбинаторика - правила, формулы и примеры с решением необходимо из N улиц выбрать бесповторным способом к улиц в направлении Комбинаторика - правила, формулы и примеры с решением. Это можно сделать Комбинаторика - правила, формулы и примеры с решением способами.

Ответ. Комбинаторика - правила, формулы и примеры с решением

Пример №4

Сколькими способами можно Комбинаторика - правила, формулы и примеры с решением одинаковых предметов распределить между Комбинаторика - правила, формулы и примеры с решением лицами так, чтобы каждый получил не менее одного предмета?

Решение. Поставим эти предметы в ряд. Между ними будет Комбинаторика - правила, формулы и примеры с решением промежуток. В любыеКомбинаторика - правила, формулы и примеры с решением из этих промежутков поставим разделяющие перегородки. Тогда все предметы разделятся на Комбинаторика - правила, формулы и примеры с решением непустых частей. Первую часть передадим первому лицу, вторую — второму и т.д. Выбрать же Комбинаторика - правила, формулы и примеры с решением промежуток из Комбинаторика - правила, формулы и примеры с решением промежутка можно Комбинаторика - правила, формулы и примеры с решением способами. Заметим, что вообще Комбинаторика - правила, формулы и примеры с решением предметов распределить между Комбинаторика - правила, формулы и примеры с решением лицами можно Комбинаторика - правила, формулы и примеры с решением способами.

Ответ. Комбинаторика - правила, формулы и примеры с решением

Пример 1.4.

Сколькими способами можно распределить 6 яблок, 8 груш и 10 слив между тремя детьми? Сколькими способами это можно сделать так, чтобы каждый ребенок получил по меньшей мере одно яблоко, одну сливу и одну грушу?

Решение. Яблоки в соответствии с формулой (1.5) можно распределить Комбинаторика - правила, формулы и примеры с решением способами, груши — Комбинаторика - правила, формулы и примеры с решением, а сливы Комбинаторика - правила, формулы и примеры с решением способами. По комбинаторному принципу всего способов Комбинаторика - правила, формулы и примеры с решением Если необходимо, чтобы каждый ребенок получил по меньшей мере одно яблоко, одну грушу и одну сливу, то в соответствии с формулой предыдущего примера имеем Комбинаторика - правила, формулы и примеры с решением способов.

Ответ. 83160; 7560.

Пример №5

Сколько цифр в первой тысяче не содержат в своей записи цифры 5?

Решение. Для записи любой из цифр 000, 001, 002, …, 999 необходимо трижды выбрать повторным способом одну из десяти цифр, поэтому и получается всего Комбинаторика - правила, формулы и примеры с решением чисел. Если цифру 5 исключить, то выбор можно производить только из девяти цифр: 0, 1,2, 3, 4, 6, 7, 8, 9. Поэтому всего получится Комбинаторика - правила, формулы и примеры с решением чисел в первой тысяче, в записи которых нет цифры 5.

Ответ. 729.

Пример №6

Сколько шестизначных чисел содержат в записи ровно три различных цифры?

Решение. Заметим, что всего шестизначных чисел имеется Комбинаторика - правила, формулы и примеры с решением, так как первая цифра может быть любой (исключая нуль), а остальные пять могут быть выбраны Комбинаторика - правила, формулы и примеры с решением способами.

Выбрать три ненулевых цифры можно Комбинаторика - правила, формулы и примеры с решением способами. Из выбранных трех цифр можно составить Комбинаторика - правила, формулы и примеры с решением шестизначных чисел, из двух — Комбинаторика - правила, формулы и примеры с решением, а из одной — Комбинаторика - правила, формулы и примеры с решением шестизначное число. По формуле (1.7) получаем, что существует Комбинаторика - правила, формулы и примеры с решением шестизначных чисел, в записи которых есть только три заданные цифры. Поэтому общее число шестизначных чисел, в записи которых имеются три отличные от нуля цифры, равно Комбинаторика - правила, формулы и примеры с решением

Учтем теперь возможность использования нуля. К нулю нужно добавить две цифры, что можно сделать Комбинаторика - правила, формулы и примеры с решением способами. Если, например, были выбраны цифры 0, 2, 5, то первой цифрой должна быть 2 или 5. К этой первой цифре в соответствии с формулой (1.7) можно добавить Комбинаторика - правила, формулы и примеры с решением комбинаций остальных пяти цифр. Тогда всего шестизначных чисел, состоящих из 0, 2, 5 будет Комбинаторика - правила, формулы и примеры с решением Всего же шестизначных чисел, записанных тремя цифрами, среди которых встречается нуль, ровно Комбинаторика - правила, формулы и примеры с решением Всего чисел, удовлетворяющих условиям задачи, имеется Комбинаторика - правила, формулы и примеры с решением

Ответ. 58320.

Пример №7

В саду есть цветы десяти наименований (розы, флоксы, ромашки и т. д.).

а)    Сколькими способами можно составить букет из пяти цветков (не принимая во внимание совместимость растений и художественные соображения)?

б)    Сколькими способами можно составить букет из пяти различных цветков?

в)    Сколькими способами можно составить букет из пяти цветков так, чтобы в букете непременно было хотя бы по одному цветку двух определенных наименований

Решение. а) Если запрета на повторение цветков нет, то мы имеем дело с повторным выбором и нас интересует только состав. Поэтому по формуле (1.5) получаем Комбинаторика - правила, формулы и примеры с решением способа.

б)    Если цветы должны быть разными, то способ выбора бесповторный и букет можно составить Комбинаторика - правила, формулы и примеры с решением способами.

в)    Отберем по одному цветку каждого из двух названных наименований. Три остальных цветка можно выбрать из 10 возможных Комбинаторика - правила, формулы и примеры с решением способами.

Ответ. а) 2002; б) 504; в) 220.

Пример №8

Имеется Комбинаторика - правила, формулы и примеры с решением яблок, Комбинаторика - правила, формулы и примеры с решением груш и Комбинаторика - правила, формулы и примеры с решением персиков. Сколькими способами можно их разложить по двум корзинам? Сколькими способами можно это сделать, если в каждой корзине должно быть хотя бы по одному фрукту всех названных видов (полагаем, что фруктов каждого наименования два или больше)?

Решение. Ясно, что яблоки можно разложить Комбинаторика - правила, формулы и примеры с решением способом (в первую корзину можно не положить яблок совсем, положить одно яблоко, два яблока, …, все яблоки). Те же рассуждения в отношении груш и персиков дают соответственно Комбинаторика - правила, формулы и примеры с решением комбинаций. По комбинаторному принципу всего будет Комбинаторика - правила, формулы и примеры с решением способов.

При ответе на второй вопрос учтем, что следует по одному яблоку сразу положить в каждую из корзин, а остальные Комбинаторика - правила, формулы и примеры с решением яблока раскладывать произвольным образом (в первую корзину либо не добавляем яблок, либо добавляем одно, либо –– два, …, либо – все Комбинаторика - правила, формулы и примеры с решением яблока). Все это можно сделать Комбинаторика - правила, формулы и примеры с решением способами. Те же рассуждения насчет других фруктов и комбинаторный принцип дают следующий результат: Комбинаторика - правила, формулы и примеры с решением

Ответ. Комбинаторика - правила, формулы и примеры с решением

Пример №9

Требуется найти число натуральных делителей натурального числа Комбинаторика - правила, формулы и примеры с решением.

Решение. Разложим Комбинаторика - правила, формулы и примеры с решением на простые множители:

Комбинаторика - правила, формулы и примеры с решением

где Комбинаторика - правила, формулы и примеры с решением– различные простые числа. (Например, Комбинаторика - правила, формулы и примеры с решениемКомбинаторика - правила, формулы и примеры с решением)

Заметим, что при разделении числа Комбинаторика - правила, формулы и примеры с решением на любые два множителя Комбинаторика - правила, формулы и примеры с решением и Комбинаторика - правила, формулы и примеры с решением простые сомножители распределятся между Комбинаторика - правила, формулы и примеры с решением и Комбинаторика - правила, формулы и примеры с решением. Если сомножитель , Комбинаторика - правила, формулы и примеры с решением в число Комбинаторика - правила, формулы и примеры с решением входит Комбинаторика - правила, формулы и примеры с решением то разложение (1.8) примет вид:

Комбинаторика - правила, формулы и примеры с решением

Так что разложение Комбинаторика - правила, формулы и примеры с решением на два сомножителя сводится к разделению каждого из чисел Комбинаторика - правила, формулы и примеры с решением на две части, а это можно сделать Комбинаторика - правила, формулы и примеры с решением способами.

Ответ. Комбинаторика - правила, формулы и примеры с решением.

Пример №10

Сколькими способами легкоатлет, собираясь на тренировку, может выбрать себе пару спортивной обуви, имея 5 пар кроссовок и 2 нары кед?

Очевидно, что выбрать одну из имеющихся пар обуви, кроссовки или кеды, можно 5 + 2 = 7 способами.

Обобщая, приходим к комбинаторному правилу сложения:

Это правило справедливо также для трех и более элементов.

Пример №11

В меню школьной столовой предлагается на выбор 4 вида пирожков и 3 вида сока. Сколько разных вариантов выбора завтрака, состоящего из одного пирожка и одного стакана сока, имеется у учащегося этой школы? Комбинаторика - правила, формулы и примеры с решением

Пирожок можно выбрать 4 способами и к каждому пирожку выбрать сок 3 способами (рис. 76). Следовательно, учащийся имеет Комбинаторика - правила, формулы и примеры с решением вариантов выбора завтрака.

Обобщая, приходим к комбинаторному правилу умножения:

Это правило справедливо также для трех и более элементов.

Пример №12

Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, если в числе: 1) цифры не повторяются; 2) цифры могут повторяться?

Комбинаторика - правила, формулы и примеры с решением

Решение:

1) Первую цифру можем выбрать 4 способами (рис.77). Так как после выбора первой цифры их останется три (ведь цифры в нашем случае повторяться не могут), то вторую цифру можем выбрать 3 способами.И наконец, третью цифру можем выбрать из оставшихся двух – то есть 2 способами. Следовательно, количество искомых трехзначных у чисел будет равно Комбинаторика - правила, формулы и примеры с решением.

2) Применим комбинаторное правило умножения. Так как цифры в числе могут повторяться, то каждую из цифр искомого числа можно выбрать 4 способами (рис. 78), и тогда таких чисел будет Комбинаторика - правила, формулы и примеры с решением.

Ответ. 1) 24 числа; 2) 64 числа.

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

Пример №13

Сколько четных пятизначных чисел можно составить из цифр 5, 6, 7, 8, 9, если цифры в числе не повторяются?

Решение:

Четное пятизначное число можно получить, если последней его цифрой будет 6 или 8. Чисел, у которых последней является цифра 6, будет Комбинаторика - правила, формулы и примеры с решением (рис. 79),

Комбинаторика - правила, формулы и примеры с решением

а тех, у которых последней является цифра 8, – также 24. По комбинаторному правилу сложения всего четных чисел будет Комбинаторика - правила, формулы и примеры с решением.

Ответ. 48.

Пример №14

Азбука племени АБАБ содержит всего две буквы – «а» и «б». Сколько слов в языке этого племени состоит: 1) из двух букв; 2) из трех букв?

Решение:

1) аа, ба, аб, бб (всего четыре слова); 2) ааа, ааб, аба, абб, ббб, бба, баб, баа (всего восемь слов).

Заметим, что найденное количество слов соответствует комбинаторному правилу умножения. Так как на каждое место есть два «претендента» – «а» и «б», то слов, состоящих из двух букв, будет Комбинаторика - правила, формулы и примеры с решением, а из трех букв – Комбинаторика - правила, формулы и примеры с решением.

Пример №15

В футбольной команде из 11 игроков надо выбрать капитана и его заместителя. Сколькими способами это можно сделать?

Решение:

Капитаном можно выбрать любого из 11 игроков, а его заместителем – любого из 10 оставшихся игроков. Таким образом (по правилу умножения), имеем Комбинаторика - правила, формулы и примеры с решением разных способов.

Пример №16

В Стране Чудес 10 городов и каждые два из них соединяет авиалиния. Сколько авиалиний в этой стране?

Решение. Так как каждая авиалиния соединяет два города, то одним из них может быть любой из 10 городов, а другим – любой из 9 оставшихся. Следовательно, количество авиалиний равно Комбинаторика - правила, формулы и примеры с решением. Но при этом каждую из авиалиний мы учли дважды. Поэтому всего их будет Комбинаторика - правила, формулы и примеры с решением.

Комбинаторные задачи неразрывно связаны с задачами теории вероятностей, еще одного раздела математики.

В ХIII-ХII в. до н. э. встречаются упоминания о вопросах, близких к комбинаторным. Некоторые комбинаторные задачи решали и в Древней Греции. В частности, Аристоксен из Тарента (IV в. до н. э.), ученик Аристотеля, перечислил различные комбинации длинных и коротких слогов в стихотворных размерах. А Папп Александрийский в IV в. н. э. рассматривал число пар и троек, которые можно получить из трех элементов, допуская их повторения. Некоторые элементы комбинаторики были известны и в Индии во II в. до н. э. Индийцы умели вычислять числа, известные нам как коэффициенты формулы бинома Ньютона. Позднее, в VIII в. н. э., арабы нашли и саму эту формулу, и ее коэффициенты, которые сейчас вычисляют с помощью комбинаторных формул или «треугольника Паскаля».

Свой нынешний вид упомянутые комбинаторные формулы приобрели благодаря средневековому ученому Леви бен Гершону (XIV в.) и французскому математику П. Эригону (XVII в.).

В III в. н. э. сирийский философ Порфирий для классификации понятий составил специальную схему, получившую название «древо Порфирия». Сейчас подобные деревья используются для решения определенных задач комбинаторики в разнообразных областях знаний. Некоторые ранее неизвестные комбинаторные задачи рассмотрел Леонардо Пизанский (Фибоначчи) в своей знаменитой «Книге абака» (1202 г.), в частности, о нахождении наименьшего набора различных гирь, позволяющего взвесить груз с любой целочисленной массой, не превышающей заданного числа. Со времен греческих математиков были известны две последовательности, каждый член которых получали по определенному правилу из предыдущих, – арифметическая и геометрическая прогрессии. А Фибоначчи впервые в одной из задач выразил член последовательности через два предыдущих, используя формулу, которую назвали рекуррентной. В дальнейшем метод рекуррентных формул стал одним из мощнейших для решения комбинаторных задач.

Как ни странно, развитию комбинаторики в значительной степени способствовали азартные игры, которые были очень популярны в XVI в. В частности, вопросами определения разнообразных комбинаций в игре в кости в то время занимались такие известные итальянские математики, как Д. Кардано, H. Тарталья и др. А наиболее полно изучил этот вопрос в XVII в. Галилео Галилей.

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

Правила суммы и произведения

Вспомните, что в математике любые совокупности называют множествами. Объекты, входящие в множества, называют его элементами. Множества обозначают большими латинскими буквами, а их элементы записывают в фигурных скобках. Считают, что все элементы множества различны.

Например, Комбинаторика - правила, формулы и примеры с решением

Множества бывают конечными и бесконечными. Если множество не содержит ни одного элемента, его называют пустым и обозначают символом Комбинаторика - правила, формулы и примеры с решением

Два множества называют равными, если они состоят из одних и тех же элементов.

Если Комбинаторика - правила, формулы и примеры с решением — часть множества Комбинаторика - правила, формулы и примеры с решением то его называют подмножеством множества Комбинаторика - правила, формулы и примеры с решением и записывают Комбинаторика - правила, формулы и примеры с решением Наглядно это изображают с помощью диаграммы Эйлера (рис. 135, а). В частности, для числовых множеств правильные такие соотношения: 

Комбинаторика - правила, формулы и примеры с решением

Случается, что множества Комбинаторика - правила, формулы и примеры с решением имеют общие элементы. Если множество Комбинаторика - правила, формулы и примеры с решением содержит все общие элементы множеств Комбинаторика - правила, формулы и примеры с решением и только их, то множество Комбинаторика - правила, формулы и примеры с решением называют пересечением множеств Комбинаторика - правила, формулы и примеры с решением Записывают это так: Комбинаторика - правила, формулы и примеры с решениемДиаграммой Эйлера пересечение изображают, как показано на рисунке 135, б. Множество, содержащее каждый элемент каждого из множеств Комбинаторика - правила, формулы и примеры с решением и только эти

Комбинаторика - правила, формулы и примеры с решением

элементы, называется объединением множеств Комбинаторика - правила, формулы и примеры с решением Если Комбинаторика - правила, формулы и примеры с решением — объединение множеств  Комбинаторика - правила, формулы и примеры с решением то пишут Комбинаторика - правила, формулы и примеры с решением (рис. 135, в).

Разницей множеств Комбинаторика - правила, формулы и примеры с решением называют множество, состоящее из всех элементов множества Комбинаторика - правила, формулы и примеры с решением не принадлежащих множеству Комбинаторика - правила, формулы и примеры с решением Его обозначают Комбинаторика - правила, формулы и примеры с решениемНапример, если Комбинаторика - правила, формулы и примеры с решениемКомбинаторика - правила, формулы и примеры с решением

Говоря «множество», «подмножество», порядок их элементов не учитывают. Говорят, что они не упорядочены. Рассматривают и упорядоченные множества. Так называют множества с фиксированным порядком элементов. Их обозначают не фигурными, а круглыми скобками. Например, из элементов множества Комбинаторика - правила, формулы и примеры с решением можно образовать 6 трёхэлементных упорядоченных множеств: Комбинаторика - правила, формулы и примеры с решением

Как множества, все они равны, как упорядоченные множества — разные.

Существуют задачи, в которых надо определить, сколько различных подмножеств или упорядоченных подмножеств можно образовать из элементов данного множества. Их называют комбинаторными задачами, а раздел математики, в котором рассматривается решение комбинаторных задач, называют комбинаторикой.

Комбинаторика — раздел математики, посвящённый решению задач выбора и расположения элементов некоторого конечного множества в соответствии с заданными правилами.

Рассмотрим два основных правила, с помощью которых решается много комбинаторных задач.

Пример №17

В городе Комбинаторика - правила, формулы и примеры с решением есть два университета — политехнический и экономический. Абитуриенту нравятся три факультета в политехническом университете и два — в экономическом. Сколько возможностей имеет студент для поступления в университет?

Решение:

Обозначим буквой Комбинаторика - правила, формулы и примеры с решением множество факультетов, которые выбрал абитуриент в политехническом университете, а буквой Комбинаторика - правила, формулы и примеры с решением — в экономическом: Комбинаторика - правила, формулы и примеры с решением Поскольку эти множества не имеют общих элементов, то в делом абитуриент имеет Комбинаторика - правила, формулы и примеры с решением возможностей для поступления в университет.

Описанную ситуацию можно обобщить в виде утверждения, которое называется правилом суммы.

 Если элемент некоторого множества Комбинаторика - правила, формулы и примеры с решением можно выбрать Комбинаторика - правила, формулы и примеры с решением способами, а элемент множества Комбинаторика - правила, формулы и примеры с решением способами, то элемент из множества Комбинаторика - правила, формулы и примеры с решением или из множества Комбинаторика - правила, формулы и примеры с решением можно выбрать Комбинаторика - правила, формулы и примеры с решением способами.

Правило суммы распространяется и на большее количество множеств.

Пример №18

Планируя летний отдых, семья определилась с местами его проведения: в Одессе — 1, в Евпатории — 3, в Ялте — 2, в Феодосии — 2. Сколько возможностей выбора летнего отдыха имеет семья?

Решение:

Поскольку все базы отдыха разные, то для решения задачи достаточно найти сумму элементов всех множеств, о которых говорится: Комбинаторика - правила, формулы и примеры с решениемСледовательно, семья может выбирать отдых из 8 возможных.

Пример №19

От пункта Комбинаторика - правила, формулы и примеры с решением до пункта Комбинаторика - правила, формулы и примеры с решением ведут три тропинки, а от Комбинаторика - правила, формулы и примеры с решением — две. Сколько маршрутов можно проложить от пункта Комбинаторика - правила, формулы и примеры с решением до пункта Комбинаторика - правила, формулы и примеры с решением

Решение:

Чтобы пройти от пункта Комбинаторика - правила, формулы и примеры с решением до пункта Комбинаторика - правила, формулы и примеры с решением надо выбрать одну из трёх тропинок: 1, 2 или 3 (рис. 136). После этого следует выбрать одну из двух других троп: 4 или 5. Всего от пункта Комбинаторика - правила, формулы и примеры с решением до пункта Комбинаторика - правила, формулы и примеры с решением ведут 6 маршрутов, потому что Комбинаторика - правила, формулы и примеры с решением Все эти маршруты можно обозначить с помощью пар:Комбинаторика - правила, формулы и примеры с решением

Обобщим описанную ситуацию.

 Если первый компонент пары можно выбрать Комбинаторика - правила, формулы и примеры с решением способами, а . второй — Комбинаторика - правила, формулы и примеры с решением способами, то такую пару можно выбрать Комбинаторика - правила, формулы и примеры с решением способами.

Это — правило произведения, его часто называют основным правилом комбинаторики. Обратите внимание: речь идёт об упорядоченных парах, составленных из различных компонентов.

Правило произведения распространяется и на упорядоченные тройки, четвёрки и любые другие упорядоченные конечные множества. В частности, если первый компонент упорядоченной тройки можно выбрать Комбинаторика - правила, формулы и примеры с решением способами, второй — Комбинаторика - правила, формулы и примеры с решением способами, третий — Комбинаторика - правила, формулы и примеры с решением способами, то такую упорядоченную тройку можно выбрать Комбинаторика - правила, формулы и примеры с решением способами. Например, если столовая на обед приготовила 2 первых блюда — борщ (б) и суп (с ), 3 вторых — котлеты (к), вареники (в), голубцы (г) и 2 десертных — пирожные (п) и мороженое (м), то всего из трёх блюд столовая может предложить 12 различных наборов, поскольку Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Описанной ситуации соответствует диаграмма, изображённая на рисунке 137. Такие диаграммы называют деревьями.

Пример №20

Сколько разных поездов можно составить из 6 вагонов, если каждый из вагонов можно поставить на любом месте?

Решение:

Первым можно поставить любой из б вагонов. Имеем 6 выборов. Второй вагон можно выбрать из оставшихся 5 вагонов. Поэтому, согласно правилу умножения, два первых вагона можно выбрать Комбинаторика - правила, формулы и примеры с решением способами. Третий вагон можно выбрать из 4 вагонов, которые остались. Поэтому три первых вагона можно выбрать Комбинаторика - правила, формулы и примеры с решением способами. Продолжая подобные рассуждения, приходим к ответу: всего можно составить Комбинаторика - правила, формулы и примеры с решением различных поездов.

Обратите внимание на решение последней задачи. Оно свелось к вычислению произведения всех натуральных чисел от 1 до 6. В комбинаторике подобные произведения вычисляют часто.

Произведение всех натуральных чисел от 1 до Комбинаторика - правила, формулы и примеры с решением называют Комбинаторика - правила, формулы и примеры с решением факториалом и обозначают Комбинаторика - правила, формулы и примеры с решением

Например:

Комбинаторика - правила, формулы и примеры с решением

Условились считать, что Комбинаторика - правила, формулы и примеры с решением

Языком теории множеств правила суммы и произведения можно сформулировать следующим образом.

Если пересечение множеств Комбинаторика - правила, формулы и примеры с решением пустое, то количество элементов в их объединении Комбинаторика - правила, формулы и примеры с решением равно сумме количества элементов множеств Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Если множества Комбинаторика - правила, формулы и примеры с решением имеют общие элементы, то 

Комбинаторика - правила, формулы и примеры с решением

Если множества Комбинаторика - правила, формулы и примеры с решением конечны, то количество возможных пар Комбинаторика - правила, формулы и примеры с решением равно произведению количества элементов множеств Комбинаторика - правила, формулы и примеры с решением 

Комбинаторика - правила, формулы и примеры с решением

Пример №21

В розыгрыше на первенство города по баскетболу принимают участие команды из 12 школ. Сколькими способами могут быть распределены первое и второе места?

Решение:

Первое место может получить одна из 12 команд. После того, как определён обладатель первого места, второе место может получить одна из 11 команд. Следовательно, общее количество способов, которыми можно распределить первое и второе места, равно Комбинаторика - правила, формулы и примеры с решением

Ответ. 132.

Пример №22

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

Решение:

Первой цифрой числа может быть одна из 5 цифр 1, 2, 3, 4, 5. Если первая цифра выбрана, то вторая может быть выбрана 5-ю способами, третья — 4-мя, четвёртая — 3-мя. Согласно правилу умножения общее число способов равно:

Комбинаторика - правила, формулы и примеры с решением

 Ответ. 300.

Пример №23

Упростите выражение Комбинаторика - правила, формулы и примеры с решением

Решение:

 Комбинаторика - правила, формулы и примеры с решениемКомбинаторика - правила, формулы и примеры с решением

Размещения и перестановки

Задача:

Сколькими способами собрание из 20 человек может избрать председателя и секретаря?

Решение:

Председателя можно выбрать 20-ю способами, секретаря — из остальных 19 человек — 19-ю способами. По правилу произведения председателя и секретаря собрания могут выбрать Комбинаторика - правила, формулы и примеры с решением способами.

Обобщим задачу. Сколько упорядоченных Комбинаторика - правила, формулы и примеры с решениемэлементных подмножеств можно составить из Комбинаторика - правила, формулы и примеры с решением различных элементов? На первое место можно поставить любой из данных Комбинаторика - правила, формулы и примеры с решением элементов. На второе место — любой из остальных Комбинаторика - правила, формулы и примеры с решением элементов и т. д. На последнее Комбинаторика - правила, формулы и примеры с решением место можно поставить любой из остальных Комбинаторика - правила, формулы и примеры с решением элементов. Из правила произведения следует, что из данных Комбинаторика - правила, формулы и примеры с решением элементов можно получить Комбинаторика - правила, формулы и примеры с решением  Комбинаторика - правила, формулы и примеры с решением-элементных упорядоченных подмножеств.

Например, из 4 элементов Комбинаторика - правила, формулы и примеры с решением упорядоченных двухэлементных подмножеств можно образовать всего Комбинаторика - правила, формулы и примеры с решениемКомбинаторика - правила, формулы и примеры с решением

Упорядоченое Комбинаторика - правила, формулы и примеры с решением-элементное подмножество Комбинаторика - правила, формулы и примеры с решениемэлементного множества называют размещением из Комбинаторика - правила, формулы и примеры с решением элементов Комбинаторика - правила, формулы и примеры с решением Их число обозначают Комбинаторика - правила, формулы и примеры с решением

Из предыдущих рассуждений следует, что Комбинаторика - правила, формулы и примеры с решением и что для любых натуральных Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

В правой части этого равенства Комбинаторика - правила, формулы и примеры с решением множителей. Поэтому результат можно сформулировать в виде такого утверждения.

Число размещений из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением равно произведению Комбинаторика - правила, формулы и примеры с решениемпоследовательных натуральных чисел, наибольшее из которых Комбинаторика - правила, формулы и примеры с решением

Примеры:

 Комбинаторика - правила, формулы и примеры с решением

Пример №24

Сколькими способами можно составить дневное расписание из пяти разных уроков, если класс изучает 10 различных предметов?

Решение:

Речь идёт об упорядоченных 5-элементных подмножествах некоторого множества, состоящего из 10 элементов.

Это размещения. Комбинаторика - правила, формулы и примеры с решением

Ответ. 30 240 способами.

Число размещений из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением можно вычислять и по другой формуле: Комбинаторика - правила, формулы и примеры с решением (проверьте самостоятельно).

 Размещение Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением называют перестановками из Комбинаторика - правила, формулы и примеры с решением элементов. Их число обозначают Комбинаторика - правила, формулы и примеры с решением

Например, из трёх элементов Комбинаторика - правила, формулы и примеры с решением можно образовать 6 различных перестановок: Комбинаторика - правила, формулы и примеры с решением Следовательно, Комбинаторика - правила, формулы и примеры с решением

Подставив в формулу числа размещений Комбинаторика - правила, формулы и примеры с решением получим, что Комбинаторика - правила, формулы и примеры с решением

Число перестановок из Комбинаторика - правила, формулы и примеры с решением элементов равно Комбинаторика - правила, формулы и примеры с решением

Примеры:

 Комбинаторика - правила, формулы и примеры с решением

Пример №25

Сколькими способами можно составить список из 10 фамилий?

Решение:

 Комбинаторика - правила, формулы и примеры с решением

Ответ. 3 628 800 способами.

Некоторые комбинаторные задачи сводятся к решению уравнений, в которых переменная указывает на количество элементов в некотором множестве или подмножестве. Рассмотрим несколько таких уравнений.

Пример №26

Решите уравнение Комбинаторика - правила, формулы и примеры с решением

Решение:

Пользуясь формулой размещений, данное уравнение можно заменить таким:

Комбинаторика - правила, формулы и примеры с решением

По условию задачи Комбинаторика - правила, формулы и примеры с решением — натуральное число, поэтому Комбинаторика - правила, формулы и примеры с решением — посторонний корень. Следовательно, Комбинаторика - правила, формулы и примеры с решением

Пример №27

Решите уравнение Комбинаторика - правила, формулы и примеры с решением

Решение:

Запишем выражения Комбинаторика - правила, формулы и примеры с решением через произведения.

Имеем: Комбинаторика - правила, формулы и примеры с решением

Поскольку по смыслу задачи Комбинаторика - правила, формулы и примеры с решением Поэтому последнее уравнение можно сократить на произведение Комбинаторика - правила, формулы и примеры с решением Тогда Комбинаторика - правила, формулы и примеры с решениемКомбинаторика - правила, формулы и примеры с решением Но уравнение Комбинаторика - правила, формулы и примеры с решением удовлетворяет только одно значение: Комбинаторика - правила, формулы и примеры с решением

Пример №28

Команда из трёх человек выступает в соревнованиях по художественной гимнастике, в которых принимают участие ещё 27 спортсменок. Сколькими способами могут распределиться места между членами команды, при условии, что на этих соревнованиях ни одно место не делится?

Решение:

Речь идёт об упорядоченных 3-элементных подмножествах множества, состоящего из 30 элементов. Это — размещения. Комбинаторика - правила, формулы и примеры с решением

Пример №29

Сколькими способами можно разместить на полке 5 дисков?

Решение:

Речь идёт об упорядоченных 5-элементных множествах. Искомое количество способов равно Комбинаторика - правила, формулы и примеры с решением

Ответ. 120 способами.

Пример №30

Изображённое на рисунке 140 кольцо раскрашено в 7 цветов. Сколько существует таких колец, раскрашенных теми же цветами только в других последовательностях? 

Решение:

Зафиксируем одну какую-нибудь часть кольца, окрашенную одним цветом, б других частей можно раскрасить Комбинаторика - правила, формулы и примеры с решением способами.

Комбинаторика - правила, формулы и примеры с решением

Ответ. 720 колец.

Пример №31

Сколько можно составить различных неправильных дробей, числителями и знаменателями которых есть числа 3,5, 7,9,11,13?

Решение:

Способ 1. Дробей, у которых числитель не равен знаменателю, можно составить Комбинаторика - правила, формулы и примеры с решением то есть Комбинаторика - правила, формулы и примеры с решением Из этих дробей только половина — неправильных, то есть — 15.

Неправильными являются также дроби, у которых числитель равен знаменателю. Таких дробей в нашем случае 6. Итак, всего можно составить Комбинаторика - правила, формулы и примеры с решением (дробь).

Способ 2. Если знаменатель неправильной дроби 3, то его числителями могут быть все 6 данных чисел. Если знаменатель 5, то числителями неправильной дроби могут быть 5 чисел (5, 7, 9, 11, 13) и т.д. Наконец, если знаменатель — число 13, то существует только 1 неправильная дробь, со знаменателем 13. Всего таких неправильных дробей существует Комбинаторика - правила, формулы и примеры с решением

Ответ. 21 дробь.

Комбинаторика - правила, формулы и примеры с решением

Комбинации и бином ньютона

Пусть дано множество из трёх элементов: Комбинаторика - правила, формулы и примеры с решением Его двухэлементных подмножеств (не упорядоченных) существует всего три: Комбинаторика - правила, формулы и примеры с решениемГоворят, что существует 3 комбинации из трёх элементов по два. Пишут: Комбинаторика - правила, формулы и примеры с решением

 Комбинацией из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением называют любое Комбинаторика - правила, формулы и примеры с решениемэлементное подмножество Комбинаторика - правила, формулы и примеры с решениемэлементного множества.

Число комбинаций из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением обозначают Комбинаторика - правила, формулы и примеры с решением В отличие от размещений, комбинации — подмножества неупорядоченные.

Сравните: Комбинаторика - правила, формулы и примеры с решением При тех же значениях Комбинаторика - правила, формулы и примеры с решением значение Комбинаторика - правила, формулы и примеры с решением меньше  Комбинаторика - правила, формулы и примеры с решением Можно также указать, во сколько раз меньше. Каждую Комбинаторика - правила, формулы и примеры с решениемэлементную комбинацию можно упорядочить Комбинаторика - правила, формулы и примеры с решением способами. В результате из одной комбинации получают Комбинаторика - правила, формулы и примеры с решением размещений (упорядоченных подмножеств) из тех же элементов. Итак,

число Комбинаторика - правила, формулы и примеры с решениемэлементных комбинаций в Комбинаторика - правила, формулы и примеры с решением раз меньше числа размещений из тех же Комбинаторика - правила, формулы и примеры с решением элементов.

То есть, Комбинаторика - правила, формулы и примеры с решением отсюда

Комбинаторика - правила, формулы и примеры с решением

Пример №32

Вычислите: Комбинаторика - правила, формулы и примеры с решением

Решение:

Комбинаторика - правила, формулы и примеры с решением

Обратите внимание! Комбинаторика - правила, формулы и примеры с решением Полагают также, что Комбинаторика - правила, формулы и примеры с решением для любого Комбинаторика - правила, формулы и примеры с решением

Пример №33

Сколькими способами из 25 учеников можно выбрать на конференцию двух делегатов?

Решение:

Здесь Комбинаторика - правила, формулы и примеры с решением порядок учеников не имеет значения.

Комбинаторика - правила, формулы и примеры с решением

Ответ. 300-ми способами.

Докажем, что для натуральных значений Комбинаторика - правила, формулы и примеры с решением правильно тождество Комбинаторика - правила, формулы и примеры с решением

Доказательство. Пусть дано Комбинаторика - правила, формулы и примеры с решением различных элементов: Комбинаторика - правила, формулы и примеры с решением Всего из них можно образовать Комбинаторика - правила, формулы и примеры с решением различных  Комбинаторика - правила, формулы и примеры с решениемэлементных комбинаций. Это количество комбинаций вычислим другим способом. Из данных Комбинаторика - правила, формулы и примеры с решением элементов, кроме последнего Комбинаторика - правила, формулы и примеры с решением можно образовать Комбинаторика - правила, формулы и примеры с решением комбинаций. Остальные Комбинаторика - правила, формулы и примеры с решениемэлементные комбинации из всех данных элементов можно образовать, если к каждой комбинации из первых Комбинаторика - правила, формулы и примеры с решениемэлементов по Комбинаторика - правила, формулы и примеры с решением дописать элемент Комбинаторика - правила, формулы и примеры с решением Таких комбинаций Комбинаторика - правила, формулы и примеры с решением

Следовательно, Комбинаторика - правила, формулы и примеры с решением А это и требовалось доказать.

Такое комбинаторное тождество можно доказать также, воспользовавшись формулой числа комбинаций.

С комбинациями тесно связана формула бинома Ньютона. Вспомните формулу квадрата двучлена: Комбинаторика - правила, формулы и примеры с решением

 Умножив Комбинаторика - правила, формулы и примеры с решением получим формулы:

Комбинаторика - правила, формулы и примеры с решением

Эти три формулы можно записать и так:

Комбинаторика - правила, формулы и примеры с решением

Оказывается, для каждого натурального значения Комбинаторика - правила, формулы и примеры с решением правильна и общая формула:

Комбинаторика - правила, формулы и примеры с решением

Это тождество называют формулой бинома Ньютона. а её правую часть разложением бинома Ньютона. Бином — латинское название двучлена. Пользуясь этой формулой, возведём, например, двучлен Комбинаторика - правила, формулы и примеры с решением в пятую степень. Поскольку Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Доказать формулу бинома Ньютона можно методом математической индукции.

Доказательство. Предположим, что формула Комбинаторика - правила, формулы и примеры с решением верна для некоторого натурального показателя степени Комбинаторика - правила, формулы и примеры с решением Покажем, что тогда она верна и для следующего за ним значения Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Выражения в скобках преобразованы согласно формулы

Комбинаторика - правила, формулы и примеры с решением

Следовательно, если формула бинома Ньютона верна для Комбинаторика - правила, формулы и примеры с решением то она правильна и для Комбинаторика - правила, формулы и примеры с решением Для Комбинаторика - правила, формулы и примеры с решением она правильна, так как Комбинаторика - правила, формулы и примеры с решением Поэтому на основе аксиомы математической индукции можно утверждать, что формула верна для любого натурального показателя Комбинаторика - правила, формулы и примеры с решением

Вычислять коэффициенты разложения бинома Ньютона можно не по формуле числа комбинаций, а пользуясь числовым треугольником Паскаля — своеобразным способом вычисления коэффициентов разложения бинома Ньютона Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Треугольник Паскаля можно продолжать как угодно далеко. Это следует из тождества Комбинаторика - правила, формулы и примеры с решением Его крайние числа — единицы, а каждое другое равно сумме двух ближайших к нему чисел сверху.

Например, прибавляя числа шестой строки (для Комбинаторика - правила, формулы и примеры с решением получим числа следующей строки (для Комбинаторика - правила, формулы и примеры с решением Следовательно, Комбинаторика - правила, формулы и примеры с решением Общий член разложения бинома Комбинаторика - правила, формулы и примеры с решением можно определить по формуле Комбинаторика - правила, формулы и примеры с решением

Например:

  • первый член — Комбинаторика - правила, формулы и примеры с решением
  • второй член — Комбинаторика - правила, формулы и примеры с решением
  • третий член — Комбинаторика - правила, формулы и примеры с решением

Пример №34

В турнире по шашкам приняли участие 5 девушек и 7 юношей. Каждый участник сыграл один раз с каждым другим. Сколько партий было: а) между девушками; б) между юношами; в) между юношами и девушками?

Решение:

а) Речь идёт о 2-элементных подмножествах (неупорядоченных) множества, состоящего из 5 элементов. Это — комбинации. Комбинаторика - правила, формулы и примеры с решением 

б) Аналогично Комбинаторика - правила, формулы и примеры с решением

в) Воспользуемся правилом умножения. Поскольку каждой из 5 девушек предстоит сыграть с каждым из 7 юношей, возможных случаев Комбинаторика - правила, формулы и примеры с решением

Пример №35

Для дежурства в столовой приглашают 3-х учеников из 7 класса и 2-х учеников из 10 класса. Сколькими способами это можно сделать, если в 7 классе учится 24 ученика, а в 10 классе — 18.

Решение:

Речь идёт о неупорядоченных подмножествах двух разных множеств. Это — комбинации.
Комбинаторика - правила, формулы и примеры с решением
По правилу произведения имеем Комбинаторика - правила, формулы и примеры с решением способов выбрать учащихся для дежурства.

Пример №36

Сколько разных делителей имеет число 1001?

Решение:

Разложим заданное число на простые множители: Комбинаторика - правила, формулы и примеры с решением Если число Комбинаторика - правила, формулы и примеры с решением — делитель числа 1001, то оно должно быть одним из чисел 7, 11,13 (три случая) или любым их произведением. Различных произведений может быть Комбинаторика - правила, формулы и примеры с решением Делителем данного числа есть ещё единица. Следовательно, число 1001 имеет Комбинаторика - правила, формулы и примеры с решением делителей.

Пример №37

Докажите, что выпуклый Комбинаторика - правила, формулы и примеры с решениемугольник имеет Комбинаторика - правила, формулы и примеры с решением диагоналей.

Решение:

Отрезков, концами которых являются Комбинаторика - правила, формулы и примеры с решением вершин данного Комбинаторика - правила, формулы и примеры с решением-угольника, существует Комбинаторика - правила, формулы и примеры с решением Среди них есть и Комбинаторика - правила, формулы и примеры с решением сторон данного Комбинаторика - правила, формулы и примеры с решением-угольника. Поэтому диагоналей он имеет Комбинаторика - правила, формулы и примеры с решениемКомбинаторика - правила, формулы и примеры с решением

Пример №38

Докажите тождество

Комбинаторика - правила, формулы и примеры с решением

Сделайте обобщение.

Решение:

 Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Все члены разложения бинома Ньютона Комбинаторика - правила, формулы и примеры с решением такие же, как и члены разложения бинома Комбинаторика - правила, формулы и примеры с решением только их члены с чётными номерами отрицательные.

Пример №39

Найдите номер члена разложения Комбинаторика - правила, формулы и примеры с решением который не содержит Комбинаторика - правила, формулы и примеры с решением

Решение:

Воспользуемся формулой общего члена разложения бинома. Имеем:

Комбинаторика - правила, формулы и примеры с решением

По условию задачи Комбинаторика - правила, формулы и примеры с решением то есть Комбинаторика - правила, формулы и примеры с решением Отсюда Комбинаторика - правила, формулы и примеры с решением Следовательно, не содержит Комбинаторика - правила, формулы и примеры с решением шестой член разложения бинома.

Элементы комбинаторики

Решение многих задач теории вероятностей требует знания элементов комбинаторики, основными понятиями которой являются перестановки, размещения и сочетания.

Определение: Перестановки – это комбинации из одних и тех же элементов, отличающиеся только порядком элементов.

Пример:

Даны три числа 1, 2, 3. Определить количество комбинаций из этих элементов, отличающиеся только порядком элементов.

Решение:

Комбинации из данных элементов, отличающиеся только порядком элементов: 123; 132; 213; 231; 321; 312. Всего таких комбинаций Комбинаторика - правила, формулы и примеры с решением Если дано n элементов, то число перестановок Комбинаторика - правила, формулы и примеры с решением O2. Размещения – это комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их расположением.

Пример:

Даны три числа 1, 2, 3. Определить количество размещений из этих элементов по два, отличающиеся составом или порядком элементов.

Решение:

Комбинации из данных элементов по два, отличающиеся составом или порядком элементов: 12; 21; 23; 32; 13; 31. Всего таких комбинаций 6. Если дано n элементов, то число размещений по m элементов, которые отличаются либо составом элементов, либо их расположением: Комбинаторика - правила, формулы и примеры с решением

Определение: Сочетания – это комбинации, составленные из n различных элементов по m элементов, которые отличаются друг от друга хотя бы одним элементом.

Пример:

Даны три числа 1, 2, 3. Определить количество размещений из этих элементов по два, отличающиеся хотя бы одним элементом.

Решение:

Комбинации из данных элементов по два, отличающиеся хотя бы одним элементом: 12; 23; 13. Всего таких комбинаций 3. Если дано n элементов, то число сочетаний по m элементов, которые отличаются хотя бы одним элементом:Комбинаторика - правила, формулы и примеры с решением

Пример:

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

Решение:

Число способов равно числу различных комбинаций из п элементов, отличающихся только порядком элементов, т.е. числу перестановок: Комбинаторика - правила, формулы и примеры с решением

Пример:

Из колоды, содержащей 36 карт, наугад вынимают 3 карты. Найти вероятность того, что среди выбранных карт окажется один туз.

Решение:

Событие А состоит в том, что среди выбранных карт окажется один туз. Это сложное событие состоит из двух событий: выбирается один туз из четырех, а две другие карты выбираются из оставшихся 32 карт. Следовательно, число случаев, благоприятствующих появлению события A, равно Комбинаторика - правила, формулы и примеры с решением Всего возможных равновероятных исходов, образующих полную группу определяется числом сочетаний из 36 карт по 3 карты, т.е. Комбинаторика - правила, формулы и примеры с решением Таким образом, вероятность события А равна Комбинаторика - правила, формулы и примеры с решением

Арифметика случайных событий

Будем считать, что все события, которые могут произойти в рамках данного эксперимента, располагаются внутри квадрата G, тогда невозможные события располагаются вне квадрата G (Рис. 2): Комбинаторика - правила, формулы и примеры с решением

Рис. 2. Квадрат возможных событий.

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

Определение: Суммой двух случайных событий А и В называется третье случайное событие С, которое состоит в том, что произойдет (или не произойдет) или событие А, или событие В : С = А + В (Рис. 3).

Определение: Суммой n случайных событий Комбинаторика - правила, формулы и примеры с решением называется случайное событие С, которое реализуется в данном опыте, если произойдет (или не произойдет) или одно событий Комбинаторика - правила, формулы и примеры с решением, или любая их совокупность: Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Рис. 3. Сумма случайных событий

Замечание: Если в словесном описании сложного события присутствует разделительный союз “или” между элементарными событиями, то речь идет о сумме этих элементарных событий.

Замечание: Суммой события А и ему противоположного события Комбинаторика - правила, формулы и примеры с решением является достоверное событие Комбинаторика - правила, формулы и примеры с решением т.е. Комбинаторика - правила, формулы и примеры с решением Следовательно, противоположное событие можно записать в виде Комбинаторика - правила, формулы и примеры с решением

Определение: Произведением двух случайных событий А и В называется третье случайное событие С, которое состоит в том, что произойдет (или не произойдет) и событие А, и событие В : Комбинаторика - правила, формулы и примеры с решением(Рис. 4). Комбинаторика - правила, формулы и примеры с решением

Рис. 4. Произведение случайных событий.

Определение: Произведением n случайных событий Комбинаторика - правила, формулы и примеры с решением называется случайное событие С, которое реализуется в данном опыте, если произойдет (или не произойдет) совместная реализация событий Комбинаторика - правила, формулы и примеры с решением

Замечание: Если в словесном описании сложного события присутствует соединительный союз “и” между элементарными событиями, то речь идет о произведении этих элементарных событий.

Пример №40

Пусть имеются передатчик и приемник. Приемник удален от передатчика недостаточно большое расстояние, при котором он может при определенных условиях не принять один из сигналов, переданных передатчиком. Пусть передатчик послал три сигнала. Определить следующие сложные события:

  • а) приемник принят только второй сигнал (событие А );
  • б) приемник принял только один сигнал (событие В);
  • в) приемник принял не менее двух сигналов (2 или 3 сигнала – событие С);
  • г) приемник не принял ни одного сигнала (событие D);
  • д) приемник принял хотя бы один сигнал (событие E).

Решение:

Обозначим через Комбинаторика - правила, формулы и примеры с решением элементарное событие, состоящее в том, что приемник принял сигнал i.

Сложное событие А состоит в том, что приемник не принял первый сигнал и принял второй сигнал, и не принял третий сигнал. Так как между элементарными событиями стоит соединительный союз “и”, то речь идет о их произведении, т.е. Комбинаторика - правила, формулы и примеры с решением

Сложное событие В состоит в том, что приемник принял или первый сигнал, или принял второй сигнал, или принял третий сигнал. Так как между элементарными событиями стоит разделительный союз “или”, то речь идет о сумме сложных событии, т.е. Комбинаторика - правила, формулы и примеры с решением

Рассуждая аналогично, получим выражения для остальных событий: Комбинаторика - правила, формулы и примеры с решением Сложное событие Е содержит в своем словесном описании слова “хотя бы один”, следовательно, оно противоположно событию, содержащему в своем словесном описании слова “ни один”, т.е. событию D: Комбинаторика - правила, формулы и примеры с решением

Теорема сложения вероятностей несовместных событий

Теорема: Если случайные события А и В несовместны, то вероятность их суммы равна сумме вероятностей этих событий, т.е. Р(А + В) = Р(А) + Р(В)

Доказательство: Пусть в данном опыте имеется n равновозможных, элементарных, несовместных событий и пусть в m случаях наступает событие А, а в l случаях-событие В. Тогда появлению события А + В благоприятствует m+l исходов. Поэтому Комбинаторика - правила, формулы и примеры с решением

Следствие: Если имеется N событий, то Комбинаторика - правила, формулы и примеры с решением

Следствие: Если события Комбинаторика - правила, формулы и примеры с решением (Комбинаторика - правила, формулы и примеры с решением) образуют полную группу, то Комбинаторика - правила, формулы и примеры с решением

Доказательство: Так как события Комбинаторика - правила, формулы и примеры с решением образуют полную группу равно возможных, элементарных, несовместных событий, то их сумма есть достоверное событие Комбинаторика - правила, формулы и примеры с решением а вероятность достоверного события равна 1.

Следствие: Вероятность суммы противоположных событий равна 1.

Доказательство: В силу того, что события А и ему противоположное событие Комбинаторика - правила, формулы и примеры с решением образуют полную группу несовместных событий, то по следствию вероятность их суммы равна 1.

Замечание: Если сложное событие состоит из суммы элементарных событий, то перед применением теоремы надо определить совместны или несовместны элементарные события.

Пример:

Пусть в урне находится 5 белых шаров, 3 – красных и 4 – зеленых. Из урны наудачу вынули шар. Какова вероятность того, что данный шар цветной?

Решение:

Событие, состоящее в том, что из урны извлечен красный шар, обозначим через А. Событие, состоящее в том, что из урны извлечен зеленый шар, обозначим через В. Тогда извлечение цветного шара есть событие С. Так как события А и В несовместны, т.е. событие С состоит в том, что из урны извлечен или событие А , или событие В, то С = А + В. Используя теорему о сложении вероятностей несовместных событий, получим:

Комбинаторика - правила, формулы и примеры с решением

Зависимые и независимые события. Условная и безусловная вероятности

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

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

Пример №41

В хранилище находится 10 исправных и 5 неисправных приборов, причем неизвестно, какие из них исправные, а какие – нет. Обозначим событием А – из хранилища взят исправный прибор, а В – взят неисправный прибор. Пусть вначале взят неисправный прибор. Определить вероятности указанных событий с возвращением неисправного прибора на склад и без возвращения неисправного прибора в хранилище.

Решение:

Если неисправный прибор возвращается в хранилище, то события А и В независимы и их вероятности равны Комбинаторика - правила, формулы и примеры с решением Во втором случае, когда неисправный прибор не возвращается на склад, общее количество приборов в хранилище изменилось и стало равным 14, причем неисправных приборов будет храниться 4. Следовательно, произошедшее событие В изменило вероятности события А и В: Комбинаторика - правила, формулы и примеры с решением т.е. при такой организации эксперимента события А и В являются зависимыми.

Определение: Вероятность случайного события называется безусловной, если при ее вычислении на комплекс условий, в которых рассматривается это случайное событие, не накладывается никаких дополнительных ограничений. Безусловная вероятность обозначается Комбинаторика - правила, формулы и примеры с решением

Определение: Вероятность случайного события называется условной, если она вычисляется при условии, что произошло другое случайное событие. Условная вероятность обозначается Комбинаторика - правила, формулы и примеры с решением

Теорема умножения вероятностей

Т.2. Вероятность совместного появления двух случайных событий А и В равна произведению вероятности одного из них на условную вероятность другого события, вычисленную при условии, что первое событие имело место: Комбинаторика - правила, формулы и примеры с решением

Доказательство: Пусть событие А состоит в том, что брошенная точка наугад в квадрат G попадает в область А, которая имеет площадь Комбинаторика - правила, формулы и примеры с решением Событие В состоит в том, что брошенная наугад в квадрат G точка попадает в область В с площадью Комбинаторика - правила, формулы и примеры с решением Пусть весь квадрат имеет площадь S, а область совместного наступления событий Комбинаторика - правила, формулы и примеры с решением имеет площадь Комбинаторика - правила, формулы и примеры с решением(Рис. 5). Тогда вероятность события А равна Комбинаторика - правила, формулы и примеры с решениема события В – Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Рис. 5. Совместное наступление зависимых и независимых случайных событий.

Вероятность совместного наступления событий Комбинаторика - правила, формулы и примеры с решением.Условные вероятности того, что произойдут указанные события, определяются по формулам: Комбинаторика - правила, формулы и примеры с решением Таким образом, можно записать, что вероятность совместного наступления событий Комбинаторика - правила, формулы и примеры с решением равна:

Комбинаторика - правила, формулы и примеры с решением

Замечание: Если события А и В независимы, то Комбинаторика - правила, формулы и примеры с решением т.е. безусловная и условная вероятности равны между собой.

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

ТЗ. Вероятность совместного наступления независимых событий равна произведению вероятностей этих событий: Комбинаторика - правила, формулы и примеры с решением

Замечание: Независимость случайных событий всегда взаимная. Если Комбинаторика - правила, формулы и примеры с решением то по теореме Комбинаторика - правила, формулы и примеры с решением откуда следует, чтоКомбинаторика - правила, формулы и примеры с решением

Следствие: Методом математической индукции теоремы легко обобщается на произведение N зависимых событий:

Комбинаторика - правила, формулы и примеры с решением а теорема – для независимых событий: Комбинаторика - правила, формулы и примеры с решением

Замечание: Если сложное событие представляется в виде произведения элементарных событий, то при вычислении вероятности такого события надо определить, зависимы или независимы эти элементарные события.

Что такое комбинаторика

Понятие множества и его элементов:

Множество можно представить как совокупность некоторых объектов, объединенных по определенному признаку. В математике множество — одно из основных неопределяемых понятий. Каждый объект, принадлежащий множеству А, называется элементом этого множества. Множество, не содержащее ни одного элемента, называется пустым множеством и обозначается Комбинаторика - правила, формулы и примеры с решением.

ПодмножествоКомбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Если каждый элемент множества А является элементом множества В, то говорят, что множество А является подмножеством множества В,

и записывают так: Комбинаторика - правила, формулы и примеры с решением Используется также запись Комбинаторика - правила, формулы и примеры с решением если множество А или является подмножеством множества В, или равно множеству В.

Равенство множеств

Комбинаторика - правила, формулы и примеры с решением

Два множества называются равными, если каждый элемент первого множества является элементом второго множества и, наоборот, каждый элемент второго множества является элементом первого множества.

Пересечение множествКомбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Пересечением множеств A и В называют их общую часть, то есть множество С всех элементов, принадлежащих как множеству А, так и множеству В

Объединение множеств Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Объединением множеств А и В называют множество С, состоящее из всех элементов, принадлежащих хотя бы одному из этих множеств (А или В)

Разность множеств Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Разностью множеств А и В называется множество С, которое состоит из всех элементов, принадлежащих множеству А и не принадлежащих множеству В

Дополнение множества

Комбинаторика - правила, формулы и примеры с решением

Если все рассматриваемые множества являются подмножествами некоторого универсального множества U, то разность U А называется дополнением множества А. Другими словами, дополнением множества А называется множество, состоящее из всех элементов, не принадлежащих множеству А (но принадлежащих универсальному множеству).

Объяснение и обоснование:

Понятие множества

Одним из основных понятий, которые используются в математике, является понятие множества. Для него не дается определения. Можно пояснить, что множеством называют произвольную совокупность объектов, а сами объекты — элементами данного множества. Так, можно говорить о множестве учеников в классе (элементы — ученики), множестве дней недели (элементы — дни недели), множестве натуральных делителей числа 6 (элементы — числа 1, 2, 3, 6) и т. д.

В курсах алгебры и алгебры и начал анализа чаще всего рассматривают множества, элементами которых являются числа, и поэтому их называют числовыми множествами.

Как правило, множества обозначают прописными буквами латинского алфавита. Например, если множество М состоит из чисел 1; 2; 3, то его обозначают так: М = {1; 2; 3}. Тот факт, что число 2 входит в это множество (является элементом данного множества М) записывается с помощью специального значкаКомбинаторика - правила, формулы и примеры с решением следующим образом: Комбинаторика - правила, формулы и примеры с решением; а то, что число 5 не входит в это множество (не является элементом данного множества), записывается так:Комбинаторика - правила, формулы и примеры с решением

Можно рассматривать также множество, не содержащее ни одного элемента, — пустое множество.

Например: множество простых делителей числа 1 — пустое множество.

Для некоторых множеств существуют специальные обозначения. Так, пустое множество обозначается символомКомбинаторика - правила, формулы и примеры с решением, множество всех натуральных чисел — буквой N, множество всех целых чисел — буквой Z, множество всех рациональных чисел — буквой Q, а множество всех действительных чисел — буквой R.

Множества бывают конечными и бесконечными в зависимости от того, какое количество элементов они содержат. Так, множества А = {7} и М = {1; 2; 3} — конечные потому, что содержат конечное число элементов, а множества N, Z, Q, R — бесконечные.

Множества задают или с помощью перечисления их элементов (это можно сделать только для конечных множеств), или с помощью описания, когда задается правило (характеристическое свойство), которое позволяет определить, принадлежит или нет данный объект рассматриваемому множеству. Например, А = {-1; 0; 1} (множество задано перечислением элементов), В — множество четных целых чисел (множество задано характеристическим свойством элементов множества). Последнее множество иногда записывают так: Комбинаторика - правила, формулы и примеры с решением — четное целое число} или так: Комбинаторика - правила, формулы и примеры с решением — здесь после вертикальной черточки записано характеристическое свойство.

В общем виде запись множества с помощью характеристического свойства можно обозначить так:Комбинаторика - правила, формулы и примеры с решением — характеристическое свойство. Например,Комбинаторика - правила, формулы и примеры с решением

Равенство множеств

Пусть А — множество цифр трехзначного числа 312, то есть А = {3; 1; 2}, а В — множество натуральных чисел, меньших четырех, то есть В = {1; 2; 3}. Поскольку эти множества состоят из одних и тех же элементов, то они считаются равными. Это записывают так: А = В.

Для бесконечных множеств таким способом (сравнивая все элементы) установить их равенство невозможно. Поэтому в общем случае равенство множеств определяется следующим образом.

Два множества называются равными, если каждый элемент первого множества является элементом второго множества и, наоборот, каждый элемент второго множества является элементом первого множества.

Из приведенного определения равенства множеств следует, что в множестве одинаковые элементы не различаются. Действительно, например, {1; 2; 2} = {1; 2}, поскольку каждый элемент первого множества (1 или 2) является элементом второго множества и, наоборот, каждый элемент второго множества (1 или 2) является элементом первого. Поэтому, записывая множество, чаще всего каждый его элемент записывают только один раз.

Подмножество

Если каждый элемент множества А является элементом множества В, то говорят, что множество А является подмножеством множества В.

Это записывают следующим образом: Комбинаторика - правила, формулы и примеры с решением

Например,Комбинаторика - правила, формулы и примеры с решением (поскольку любое натуральное число — целое), Комбинаторика - правила, формулы и примеры с решением (поскольку любое целое число — рациональное),Комбинаторика - правила, формулы и примеры с решением (поскольку любое рациональное число — действительное).

Полагают, что всегдаКомбинаторика - правила, формулы и примеры с решением, то есть пустое множество является подмножеством любого множества.

Иногда вместо записи Комбинаторика - правила, формулы и примеры с решением используется также запись Комбинаторика - правила, формулы и примеры с решением, если множество А является подмножеством множества В или равно множеству В. Например, можно записать, что Комбинаторика - правила, формулы и примеры с решением .

Сопоставим определение равенства множеств с определением подмножества. Если множества А и В равны, то: 1) каждый элемент множества А является элементом множества В, следовательно, А — подмножество ВКомбинаторика - правила, формулы и примеры с решением; 2) каждый элемент множества В является элементом множества А, следовательно, В — подмножествоКомбинаторика - правила, формулы и примеры с решением Таким образом,

два множества равны, если каждое из них является подмножеством другого.

А = В означает то же, что Комбинаторика - правила, формулы и примеры с решением

Иногда соотношения между множествами удобно иллюстрировать с помощью кругов (которые часто называют кругами Эйлера-Венна). Например, рисунок 118 иллюстрирует определение подмножества, а рисунок 119-отношения между множествами Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Операции над множествами

Над множествами можно выполнять определенные действия: находить их пересечение, объединение, разность. Дадим определение этих операций и проиллюстрируем их с помощью кругов.

Пересечением множеств А и В называют их общую часть, то есть множество С всех элементов, принадлежащих как множеству А, так и множеству В.

Пересечение множеств обозначают знаком Комбинаторика - правила, формулы и примеры с решением (на рисунке 120 приведена иллюстрация и символическая запись определения пересечения множеств).

Например, если А = {2; 3; 4}, В = {0; 2; 4; 6}, то Комбинаторика - правила, формулы и примеры с решением

Объединением множеств А и В называют множество С, состоящее из всех элементов, принадлежащих хотя бы одному из этих множеств (А или В).

Объединение множеств обозначают знаком U (на рисунке 121 приведена иллюстрация и символическая запись определения объединения множеств).

Например, для множеств А и В из предыдущего примераКомбинаторика - правила, формулы и примеры с решением Если обозначить множество иррациональных чисел через М, то М U Q = R. Разностью множеств А и В называется множество С, состоящее из всех элементов, которые принадлежат множеству А и не принадлежат множеству В.

Разность множеств обозначают знаком . На рисунке 122 приведена иллюстрация и символическая запись определения разности множеств.

Например, если А = {1; 2; 3}, В = {2; 3; 4; 5}, то АВ = {1}, а В А = {4; 5}. Если В — подмножество А, то разность А В называют дополнением множества В до множества А (рис. 123).

Например, если обозначить множество иррациональных чисел через М, то R Q = М: множество М иррациональных чисел дополняет множество Q рациональных чисел до множества R всех действительных чисел.

Все множества, которые мы рассматриваем, являются подмножествами некоторого так называемого универсального множества U. Его обычно изображают в виде прямоугольника, а все остальные множества — в виде кругов внутри этого прямоугольника (рис. 124). Разность U А называется дополнением множества А. Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Дополнением множества А называется множество, состоящее из всехэлементов, не принадлежащих множеству А (но принадлежащих универсальному множеству U).

Дополнение множества А обозначаетсяКомбинаторика - правила, формулы и примеры с решением (можно читать: «А с чертой»). Например, если U = R и А = [0; 1], то Комбинаторика - правила, формулы и примеры с решением Для этого примера удобно использовать традиционную иллюстрацию множества действительных чисел на числовой прямой (рис. 125).

Комбинаторика и Бином Ньютона

Элементы комбинаторики:

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

Если все элементы полученного множества разные — получаем соединения без повторений, а если в полученном множестве элементы повторяются, то получаем соединения с повторениями*.

Перестановки:

Перестановкой из п элементов называется любое упорядоченное множество изКомбинаторика - правила, формулы и примеры с решением элементов.

Иными словами, это такое множество, для которого указано, какой элемент находится на первом месте, какой — на втором,…, какой — на п-м.

*Формулы для нахождения количества соединений с повторениями являются обязательными только для классов физико-математического профиля. Формула числа перестановокКомбинаторика - правила, формулы и примеры с решением Комбинаторика - правила, формулы и примеры с решением (читается: «Эн факториал»)

Пример:

Количество различных шестизначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, не повторяя эти цифры в одном числе, равно Комбинаторика - правила, формулы и примеры с решением

Размещения:

Размещением из Комбинаторика - правила, формулы и примеры с решением элементов поКомбинаторика - правила, формулы и примеры с решением называется любое упорядоченное множество из Комбинаторика - правила, формулы и примеры с решением элементов, состоящее из элементов Комбинаторика - правила, формулы и примеры с решением-элементного множества Формула числа размещенийКомбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Пример:

Количество различных трехзначных чисел, которые можно составить из цифр 1,2,3, 4, 5, 6, если цифры не могут повторяться, равно Комбинаторика - правила, формулы и примеры с решением

Сочетания:

Сочетанием без повторений изКомбинаторика - правила, формулы и примеры с решением элементов поКомбинаторика - правила, формулы и примеры с решением называется любое Комбинаторика - правила, формулы и примеры с решением-элементное подмножество Комбинаторика - правила, формулы и примеры с решением-элементного множества Формула числа сочетанийКомбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением(по определению считают, что Комбинаторика - правила, формулы и примеры с решением)

Пример:

Из класса, состоящего из 25 учащихся, можно выделить 5 учащихся для дежурства по школе Комбинаторика - правила, формулы и примеры с решением способами, то есть Комбинаторика - правила, формулы и примеры с решением способами. Некоторые свойства числа сочетаний без повторений Комбинаторика - правила, формулы и примеры с решением

Схема решения комбинаторных задач

Выбор правила:

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

Если элемент А можно выбрать Комбинаторика - правила, формулы и примеры с решением способами, а элемент В — Комбинаторика - правила, формулы и примеры с решением способами, то А или В можно выбрать Комбинаторика - правила, формулы и примеры с решением способами.

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

Если элемент А можно выбрать Комбинаторика - правила, формулы и примеры с решением способами, а после этого элемент В — Комбинаторика - правила, формулы и примеры с решениемспособами, то А и В можно выбратьКомбинаторика - правила, формулы и примеры с решением способами. Выбор формулы

Учитывается ли порядок следования элементов в соединении?

  • Нет

Все ли элементы входят в соединение?

  • Перестановки
  • Размещения
  • Сочетания

без повторений с повторениями без повторений с повторениями без повторений с повторениямиКомбинаторика - правила, формулы и примеры с решением

Объяснение и обоснование:

Понятие соединения

При решении многих практических задач приходится выбирать из определенной совокупности объектов элементы, имеющие те или иные свойства, размещать эти элементы в определенном порядке и т. д. Поскольку в этих задачах речь идет о тех или иных комбинациях объектов, то такие задачи называют комбинаторными. Раздел математики, в котором рассматриваются методы решения комбинаторных задач, называется комбинаторикой. В комбинаторике рассматривается выбор и размещение элементов некоторого конечного множества на основании определенных условий.

Выбранные (или выбранные и размещенные) группы элементов называют соединениями. Если все элементы полученного множества разные — получаем размещения без повторений, а если в полученном множестве элементы могут повторяться, то получаем размещения с повторениями. Рассматриваются соединения без повторений, а соединения с повторениями.

Решение многих комбинаторных задач базируется на двух основных правилах — правиле суммы и правиле произведения.

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

Если на тарелке лежит 5 груш и 4 яблока, то выбрать один фрукт (то есть грушу или яблоко) можно 9 способами (5 + 4 = 9). В общем виде имеет место такое утверждение:

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

Если в киоске продают ручки 5 видов и тетради 4 видов, то выбрать набор из ручки и тетради (то есть пару — ручка и тетрадь) можно 5 • 4 = 20 способами (поскольку с каждой из 5 ручек можно взять любую из 4 тетрадей). В общем виде имеет место такое утверждение:

  • если элемент А можно выбрать m способами, а после этого элемент В — Комбинаторика - правила, формулы и примеры с решениемспособами, то А и В можно выбрать m • п способами.

Это утверждение означает, что если для каждого из т элементов А можно взять в пару любой из Комбинаторика - правила, формулы и примеры с решением элементов В, то количество пар равно произведению Комбинаторика - правила, формулы и примеры с решением

Повторяя приведенные рассуждения несколько раз (или, иначе говоря, используя метод математической индукции), получаем, что правила суммы и произведения можно применять при выборе произвольного конечного количества элементов.

Следовательно, если приходится выбирать или первый элемент, или второй, или третий и т. д. элемент, количества способов выбора каждого еле-мента складывают, а когда приходится выбирать набор, в который входят и первый, и второй, и третий, и т. д. элементы, количества способов выбора каждого элемента перемножают.

Упорядоченные множества

При решении комбинаторных задач приходится рассматривать не только множества, в которых элементы можно записывать в любом порядке, но и так называемые упорядоченные множества. Для упорядоченных множеств существенным является порядок следования их элементов, то есть то, какой элемент записан на первом месте, какой на втором и т. д. В частности, если одни и те же элементы записать в разном порядке, то мы получим различные упорядоченные множества. Чтобы различить записи упорядоченного и неупорядоченного множеств, элементы упорядоченного множества часто записывают в круглых скобках, например Комбинаторика - правила, формулы и примеры с решением

Рассматривая упорядоченные множества, следует учитывать, что упорядоченность не является свойством самого неупорядоченного множества (из которого мы получили упорядоченное), поскольку одно и то же множество можно по-разному упорядочить. Например, множество из трех чисел {-5; 1; 3} можно упорядочить по возрастанию: (-5; 1; 3), по убыванию: (3; 1; – 5), по возрастанию абсолютной величины числа: (1; 3; -5) и т. д.

Будем понимать, что для того чтобы задать конечное упорядоченное множество из п элементов, достаточно указать, какой элемент находится на первом месте, какой на втором, …, какой на п-м.

Размещения

Размещением из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением называется любое упорядоченное множество из Комбинаторика - правила, формулы и примеры с решением элементов, состоящее из элементов Комбинаторика - правила, формулы и примеры с решением-элементного множества.

Например, из множества, содержащего три цифры {1; 5; 7}, можно составить следующие размещения из двух элементов без повторений: (1;5),(1;7),(5; 7), (5; 1), (7; 1), (7; 5).

Количество размещений из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением обозначается Комбинаторика - правила, формулы и примеры с решением (читается: «А из Комбинаторика - правила, формулы и примеры с решениемпо Комбинаторика - правила, формулы и примеры с решением», А — первая буква французского слова arrangement, что означает «размещение, приведение в порядок»). Как видим,Комбинаторика - правила, формулы и примеры с решением

 Выясним, сколько всего можно составить размещений из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением без повторений. Составление размещения представим себе как последовательное заполнение Комбинаторика - правила, формулы и примеры с решением мест, которые мы будем изображать в виде клеточек (рис. 126). На первое место мы можем выбрать один из п элементов заданного множества (то есть элемент для первой клеточки можно выбрать Комбинаторика - правила, формулы и примеры с решением способами).

Если элементы нельзя повторять, то на второе место можно выбрать только один элемент из оставшихся, то есть изКомбинаторика - правила, формулы и примеры с решением – 1 элементов. Теперь уже два элемента использованы и на третье место можно выбрать только один из Комбинаторика - правила, формулы и примеры с решением – 2 элементов и т. д. На Комбинаторика - правила, формулы и примеры с решением-e место можно выбрать только один из Комбинаторика - правила, формулы и примеры с решением элементов.

Поскольку требуется выбрать элементы и на первое место, и на второе, …, и наКомбинаторика - правила, формулы и примеры с решением-e, то используем правило произведения, получим следующую формулу числа размещений из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решениемКомбинаторика - правила, формулы и примеры с решением

Например, Комбинаторика - правила, формулы и примеры с решением (что совпадает с соответствующим значением, полученным выше). Аналогично можно обосновать формулу для нахождения числа размещений с повторениями.

При решении простейших комбинаторных задач важно правильно выбрать формулу, по которой будут проводиться вычисления. Для этого достаточно выяснить следующее: Комбинаторика - правила, формулы и примеры с решением

  • — Учитывается ли порядок следования элементов в соединении?
  • — Все ли заданные элементы входят в полученное соединение?

Если, например, порядок следования элементов учитывается и из Комбинаторика - правила, формулы и примеры с решением заданных элементов в соединении используется только Комбинаторика - правила, формулы и примеры с решением элементов, то по определению — это размещение из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением.

Заметим, что после определения вида соединения следует также выяснить, могут ли элементы в соединении повторяться, то есть выяснить, какую формулу необходимо использовать — для количества соединений без повторений или с повторениями.

Примеры решения задач:

Пример №42

На соревнования по легкой атлетике приехала команда из 12 спортсменок. Сколькими способами тренер может определить, кто из них побежит в эстафете 4 х 100 м на первом, втором, третьем и четвертом этапах?

Решение:

Комбинаторика - правила, формулы и примеры с решениемКоличество способов выбрать из 12 спортсменок четырех для участия в эстафете равно количеству размещений из 12 элементов по 4 (без повторений), то есть Комбинаторика - правила, формулы и примеры с решением

Комментарий:

Для выбора формулы выясняем ответы на вопросы, приведенные выше. Поскольку для спортсменок важно, в каком порядке они будут бежать, то порядок при выборе элементов учитывается. В полученное соединение входят не все 12 заданных элементов. Следовательно, соответствующее соединение — размещение из 12 элементов по 4 (без повторений, поскольку каждая спортсменка может бежать только на одном этапе эстафеты).

Пример №43

Найдите количество трехзначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, 7, если цифры в числе не повторяются.

Решение:

Комбинаторика - правила, формулы и примеры с решениемКоличество трехзначных чисел, которые можно составить из семи цифр 1, 2, 3, 4, 5, 6, 7, равно числу размещений из 7 элементов по 3, то есть

Комбинаторика - правила, формулы и примеры с решением

Комментарий:

Для выбора формулы выясняем, что для чисел, которые мы будем составлять, порядок следования цифр учитывается и не все элементы выбираются (только 3 из заданных семи). Следовательно, соответствующее соединение — размещение из 7 элементов по 3 (без повторений).

Пример №44

Найдите количество трехзначных чисел, которые можно составить из цифр 1, 2, 3, 4, 5, 6, 0, если цифры в числе не повторяются.

Комментарий:

Выбор формулы проводится таким же образом, как и в задаче 2. Следует учесть, что если число, составленное из трех цифр, начинается цифрой О, то оно не считается трехзначным. Следовательно, для ответов на вопросы задачи можно сначала из заданных 7 цифр записать все числа, состоящие из 3 цифр (см. пример 2), а затем из количества полученных чисел вычесть количество чисел, составленных из трех цифр, но начинающих цифрой 0. В последнем случае мы фактически будем из всех цифр без нуля (их 6) составлять двузначные числа. Тогда их количество равно числу размещений из 6 элементов по 2 (см. решение).

Также можно выполнить непосредственное вычисление, последовательно заполняя три места в трехзначном числе и используя правило произведения. В этом случае удобно сделать рассуждения наглядными, изображая соответствующие разряды в трехзначном числе в виде клеточек, например, так:

  • 6 возможностей
  • 6 возможностей
  • 5 возможностей

Решение:

Комбинаторика - правила, формулы и примеры с решениемКоличество трехзначных чисел, которые можно составить из семи цифр (среди которых нет цифры 0), если цифры в числе не повторяются, равно числу размещений из 7 элементов по 3, то есть Комбинаторика - правила, формулы и примеры с решением

Но среди данных цифр есть цифра 0, с которой не может начинаться трехзначное число. Поэтому из размещений из 7 элементов по 3 необходимо исключить те размещения, в которых первым элементом является цифра 0. Их количество равно числу размещений из 6 элементов по 2, то есть Комбинаторика - правила, формулы и примеры с решением Следовательно, искомое количество трехзначных чисел равноКомбинаторика - правила, формулы и примеры с решением

Пример №45

Решите уравнение Комбинаторика - правила, формулы и примеры с решением

Решение:

Комбинаторика - правила, формулы и примеры с решениемТогда получаем Комбинаторика - правила, формулы и примеры с решениемНа ОДЗ это уравнение равносильно уравнениям:Комбинаторика - правила, формулы и примеры с решением

Комментарий:

Уравнения, в запись которых входят выражения, обозначающие количество соответствующих соединений из х элементов, считаются определенными только при натуральных значениях переменной х. В данном случае, чтобы выражение Комбинаторика - правила, формулы и примеры с решением имело смысл необходимо выбирать натуральные значения Комбинаторика - правила, формулы и примеры с решением (в этом случае Комбинаторика - правила, формулы и примеры с решением также существует и, конечно, Комбинаторика - правила, формулы и примеры с решением Для преобразования уравнения используем соответствующие формулы:Комбинаторика - правила, формулы и примеры с решением

Перестановки

Перестановкой из п элементов называется любое упорядоченное множество из Комбинаторика - правила, формулы и примеры с решениемэлементов

Напомним, что упорядоченное множество — это такое множество, для которого указано, какой элемент находится на первом месте, какой на втором,…, какой на Комбинаторика - правила, формулы и примеры с решением

Например, переставляя цифры в числе 236 (там множество цифр {2; 3; 6} уже упорядоченное), можно составить такие перестановки без повторений: (2; 3; 6), (2; 6; 3), (3; 2; 6), (3; 6; 2), (6; 2; 3), (6; 3; 2) — всего 6 перестановок*.

Количество перестановок без повторений изКомбинаторика - правила, формулы и примеры с решением элементов обозначается Комбинаторика - правила, формулы и примеры с решением (Р — первая буква французского слова permutation — перестановка). Как видим, Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решениемФактически перестановки без повторений изКомбинаторика - правила, формулы и примеры с решением элементов являются размещениями из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением без повторений, поэтому Комбинаторика - правила, формулы и примеры с решением Произведение 1 • 2 • 3 •… • Комбинаторика - правила, формулы и примеры с решением обозначается

Комбинаторика - правила, формулы и примеры с решением!. Поэтому полученная формула числа перестановок без повторений изКомбинаторика - правила, формулы и примеры с решением элементов может быть записана так:

Комбинаторика - правила, формулы и примеры с решением

*Отметим, что каждая такая перестановка определяет трехзначное число, составленное из цифр 2,3,6 так, что цифры в числе не повторяются.

Например, Комбинаторика - правила, формулы и примеры с решением (что совпадает с соответствующим значением, полученным выше).

С помощью факториалов формулу для числа размещений без повторений

Комбинаторика - правила, формулы и примеры с решением

можно записать в другом виде. Для этого умножим и разделим выражение в формуле (1) на произведение Комбинаторика - правила, формулы и примеры с решением Получаем Комбинаторика - правила, формулы и примеры с решением

Следовательно, формула числа размещений без повторений из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением может быть записана так:

Комбинаторика - правила, формулы и примеры с решением

Для того чтобы этой формулой можно было пользоваться при всех значенияхКомбинаторика - правила, формулы и примеры с решением в частности, при Комбинаторика - правила, формулы и примеры с решением договорились считать, что

Комбинаторика - правила, формулы и примеры с решением

Например, по формуле (2) Комбинаторика - правила, формулы и примеры с решением

Обратим внимание, что в тех случаях, когда значение Комбинаторика - правила, формулы и примеры с решением! оказывается очень большим, ответы оставляют записанными с помощью факториалов.

Например,Комбинаторика - правила, формулы и примеры с решением

Примеры решения задач:

Напомним, что для выбора формулы при решении простейших комбинаторных задач достаточно выяснить следующее:

  • — Учитывается ли порядок следования элементов в соединении?
  • — Все ли заданные элементы входят в полученное соединение? Если, например, порядок следования элементов учитывается и все п заданных элементов используются в соединении, то по определению это перестановки из п элементов.

Пример №46

Найдите, сколькими способами можно восемь учащихся построить в колонну по одному.

Решение:

Комбинаторика - правила, формулы и примеры с решением Количество способов равно числу перестановок из 8 элементов. То есть Комбинаторика - правила, формулы и примеры с решением

Комментарий:

Для выбора соответствующей формулы выясняем ответы на вопросы, приведенные выше. Поскольку порядок следования элементов учитывается и все 8 заданных элементов выбираются, то соответствующие соединения — это перестановки из 8 элементов без повторений. Их количество можно вычислить по формуле.

Пример №47

Найдите количество разных четырехзначных чисел, которые можно составить из цифр 0, 3, 7, 9 (цифры в числе не повторяются).

Решение:

Комбинаторика - правила, формулы и примеры с решением Из четырех цифр 0, 3, 7, 9, не повторяя заданные цифры, можно получитьКомбинаторика - правила, формулы и примеры с решением перестановок. Перестановки, начинающиеся с цифры 0, не являются записью четырехзначного числа — их количество Комбинаторика - правила, формулы и примеры с решением. Тогда искомое количество четырехзначных чисел равно

Комбинаторика - правила, формулы и примеры с решением

Комментарий:

Поскольку порядок следования элементов учитывается и для получения четырехзначного числа надо использовать все элементы, то искомые соединения — это перестановки из 4 элементов. Их количество — Комбинаторика - правила, формулы и примеры с решением. При этом необходимо учесть, что в четырехзначном числе на первом месте не может стоять цифра 0. Таких чисел будет столько, сколько раз мы сможем выполнить перестановки из 3 оставшихся цифр, то есть Комбинаторика - правила, формулы и примеры с решением.

Пример №48

Есть десять книг, из которых четыре — учебники. Сколькими способами можно поставить эти книги на полку так, чтобы все учебники стояли рядом?

Решение:

Комбинаторика - правила, формулы и примеры с решениемСначала будем рассматривать учебники как одну книгу. Тогда на полке надо расставить не 10, а 7 книг. Это можно сделать Комбинаторика - правила, формулы и примеры с решением способами. В каждом из полученных наборов книг можно выполнить еще Комбинаторика - правила, формулы и примеры с решением перестановок учебников. По правилу умножения искомое количество способов равно Комбинаторика - правила, формулы и примеры с решением

Комментарий:

Задачу можно решать в два этапа. На первом этапе условно будем считать все учебники за 1 книгу. Тогда получим 7 книг (6 не учебников + 1 условная книга — учебник). Порядок следования элементов учитывается и используются все элементы (поставить на полку необходимо все книги). Следовательно, соответствующие соединения — это перестановки из 7 элементов. Их количество — Комбинаторика - правила, формулы и примеры с решением.

На втором этапе решения будем переставлять между собой только учебники. Это можно сделать Комбинаторика - правила, формулы и примеры с решением способами. Поскольку нам надо переставить и учебники, и другие книги, то используем правило произведения.

Сочетания без повторений

Сочетанием без повторений из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением называется любое Комбинаторика - правила, формулы и примеры с решением-элементное подмножество Комбинаторика - правила, формулы и примеры с решением-элементного множества.

Например, из множества Комбинаторика - правила, формулы и примеры с решением} можно составить следующие сочетания без повторений из трех элементов: Комбинаторика - правила, формулы и примеры с решением

Количество сочетаний без повторений из п элементов по к элементов обозначается символом Комбинаторика - правила, формулы и примеры с решением (читается: «Число сочетаний из Комбинаторика - правила, формулы и примеры с решением» или «це из Комбинаторика - правила, формулы и примеры с решением», С — первая буква французского слова combinaison — сочетание). Как видим,Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением Выясним, сколько всего можно составить сочетаний без повторений из Комбинаторика - правила, формулы и примеры с решениемэлементов по Комбинаторика - правила, формулы и примеры с решением. Для этого используем известные нам формулы числа размещений и перестановок.

Составление размещения без повторений из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением проведем в два этапа. Сначала выберем Комбинаторика - правила, формулы и примеры с решением разных элементов из заданного Комбинаторика - правила, формулы и примеры с решением-элементного множества, не учитывая порядок выбора этих элементов (то есть выберем Комбинаторика - правила, формулы и примеры с решением-элементное подмножество из Комбинаторика - правила, формулы и примеры с решением-элементного множества — сочетание без повторений из Комбинаторика - правила, формулы и примеры с решением-элементов по Комбинаторика - правила, формулы и примеры с решением). По нашему обозначению это можно сделать Комбинаторика - правила, формулы и примеры с решением способами. После этого полученное множество из к разных элементов упорядочим. Его можно упорядочить Комбинаторика - правила, формулы и примеры с решением способами. Получим размещения без повторений из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением. Следовательно, количество размещений без повторений из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением в Комбинаторика - правила, формулы и примеры с решением раз больше числа сочетаний без повторений из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением. То есть Комбинаторика - правила, формулы и примеры с решением Отсюда Комбинаторика - правила, формулы и примеры с решением Учитывая, что по формуле (2) Комбинаторика - правила, формулы и примеры с решением, получаем Комбинаторика - правила, формулы и примеры с решением

Например, Комбинаторика - правила, формулы и примеры с решением совпадает со значением, полученным выше.

Используя формулу (3), можно легко обосновать свойство 1 числа сочетаний без повторений, приведенное в таблице 21.

Комбинаторика - правила, формулы и примеры с решением 1) Поскольку Комбинаторика - правила, формулы и примеры с решением

Для того чтобы формулу (4) можно было использовать и при Комбинаторика - правила, формулы и примеры с решением, договорились считать, чтоКомбинаторика - правила, формулы и примеры с решением. Тогда по формуле (4) Комбинаторика - правила, формулы и примеры с решением.

Если в формуле (3) сократить числитель и знаменатель наКомбинаторика - правила, формулы и примеры с решением, то получим формулу, по которой удобно вычислять Комбинаторика - правила, формулы и примеры с решением при малых значениях Комбинаторика - правила, формулы и примеры с решением:

Комбинаторика - правила, формулы и примеры с решением

Например, Комбинаторика - правила, формулы и примеры с решением

Вычисление числа сочетаний без повторений с помощью треугольника Паскаля

Для вычисления числа сочетаний без повторений можно применять формулу (3):Комбинаторика - правила, формулы и примеры с решением , а можно последовательно вычислять соответствующие значения, пользуясь таким свойством:

Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением Для обоснования равенства (6) найдем сумму Комбинаторика - правила, формулы и примеры с решением учитывая, что Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением, следовательно,

Это равенство позволяет последовательно вычислять значения Комбинаторика - правила, формулы и примеры с решением с помощью специальной таблицы, которая называется треугольником Паскаля. Если считать, что Комбинаторика - правила, формулы и примеры с решением , то таблица будет иметь следующий вид (табл. 23).

Каждая строка этой таблицы начинается с единицы и заканчивается единицей Комбинаторика - правила, формулы и примеры с решением .

Если какая-либо строка уже заполнена, например, третья, то в четвертой строке надо записать на первом месте единицу. На втором месте запишем число, равное сумме двух чисел третьей строки, стоящих над ним левее и правее (поскольку по формуле (6)Комбинаторика - правила, формулы и примеры с решением.

Комбинаторика - правила, формулы и примеры с решением

На третьем месте запишем число, равное сумме двух следующих чисел третьей строки, стоящих над ним левее и правееКомбинаторика - правила, формулы и примеры с решением, и т. д. (а на последнем месте снова запишем единицу).

Примеры решения задач:

Обратим внимание, что, как и раньше, для выбора формулы при решении простейших комбинаторных задач достаточно ответить на вопросы:

  1. Учитывается ли порядок следования элементов в соединении?
  2. Все ли заданные элементы входят в полученное соединение?

Для выяснения того, что заданное соединение является сочетанием, достаточно ответить только на первый вопрос. Если порядок следования элементов не учитывается, то по определению это сочетания из Комбинаторика - правила, формулы и примеры с решением элементов по Комбинаторика - правила, формулы и примеры с решением элементов.

Пример №49

Из 12 членов туристической группы надо выбрать трех дежурных. Сколькими способами можно сделать этот выбор?

Решение:

Комбинаторика - правила, формулы и примеры с решением Количество способов выбрать из 12 туристов трех дежурных равно количеству сочетаний из 12 элементов по 3 (без повторений), то есть

Комбинаторика - правила, формулы и примеры с решением

Комментарий:

Для выбора соответствующей формулы выясняем ответы на вопросы, приведенные выше. Поскольку порядок следования элементов не учитывается (для дежурных неважно, в каком порядке их выберут), то соответствующее соединение является сочетанием из 12 элементов по 3 (без повторений). Для вычисления можно использовать формулы (3) или (5), в данном случае применяем формулу (3):Комбинаторика - правила, формулы и примеры с решением

Пример №50

Из вазы с фруктами, в которой лежит 10 разных яблок и 5 разных груш, требуется выбрать 2 яблока и 3 груши. Сколькими способами можно сделать такой выбор?

Решение:

Комбинаторика - правила, формулы и примеры с решением Выбрать 2 яблока из 10 можно Комбинаторика - правила, формулы и примеры с решениемспособами. При каждом выборе яблок груши можно выбрать способами. Тогда по правилу произведения выбор требуемых фруктов можно выполнить Комбинаторика - правила, формулы и примеры с решением способами. Получаем

Комбинаторика - правила, формулы и примеры с решением

Комментарий:

Сначала отдельно выберем 2 яблока из 10 и 3 груши из 5. Поскольку при выборе яблок или груш порядок следования элементов не учитывается, то соответствующие соединения — сочетания без повторений.

Учитывая, что требуется выбрать 2 яблока и 3 груши, используем правило произведения и перемножим полученные возможности выбора яблок(Комбинаторика - правила, формулы и примеры с решением) и груш (Комбинаторика - правила, формулы и примеры с решением).

Бином Ньютона

Бином Ньютона:

Комбинаторика - правила, формулы и примеры с решением

Поскольку Комбинаторика - правила, формулы и примеры с решением то формулу бинома Ньютона можно записать еще и так:

Комбинаторика - правила, формулы и примеры с решением

Общий член разложения степени бинома имеет вид Комбинаторика - правила, формулы и примеры с решением

Коэффициенты Комбинаторика - правила, формулы и примеры с решением называют биномиальными коэффициентами.

Свойства биномиальных коэффициентов:

  1. Число биномиальных коэффициентов (а следовательно, и число слагаемых в разложении Комбинаторика - правила, формулы и примеры с решением степени бинома) равноКомбинаторика - правила, формулы и примеры с решением
  2. Коэффициенты членов, равноудаленных от начала и конца разложения, равны между собой (поскольку Комбинаторика - правила, формулы и примеры с решением
  3. Сумма всех биномиальных коэффициентов равна Комбинаторика - правила, формулы и примеры с решениемКомбинаторика - правила, формулы и примеры с решением
  4. Сумма биномиальных коэффициентов, стоящих на четных местах, равна сумме биномиальных коэффициентов, стоящих на нечетных местах.
  5. Для вычисления биномиальных коэффициентов можно воспользоваться треугольником Паскаля, в котором вычисления коэффициентов основываются на формуле Комбинаторика - правила, формулы и примеры с решением

Треугольник Паскаля

Степень:

Комбинаторика - правила, формулы и примеры с решением

Коэффициенты разложения:

Комбинаторика - правила, формулы и примеры с решением

Ориентир:

В каждом ряду по краям стоят единицы, а каждое из остальных чисел равно сумме двух чисел, находящихся над ним справа и слева Например, Комбинаторика - правила, формулы и примеры с решением

Объяснение и обоснование Бинома Ньютона

Двучлен вида а + х также называют биномом. Из курса алгебры известно, что: Комбинаторика - правила, формулы и примеры с решением

Можно заметить, что коэффициенты разложения степени бинома Комбинаторика - правила, формулы и примеры с решением приКомбинаторика - правила, формулы и примеры с решением совпадают с числами в соответствующей строке треугольника Паскаля. Оказывается, что это свойство выполняется для любого натурального Комбинаторика - правила, формулы и примеры с решениемто есть справедлива формула:

Комбинаторика - правила, формулы и примеры с решением

Формулу (7) называют биномом Ньютона. Правая часть этого равенства называется разложением степени бинома Комбинаторика - правила, формулы и примеры с решениемКомбинаторика - правила, формулы и примеры с решениемназывают биномиальными коэффициентами. Общий член разложения степени бинома имеет вид Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением Обосновать формулу (7) можно, например, следующим образом.

Если раскрыть скобки в выражении Комбинаторика - правила, формулы и примеры с решением то есть умножить бином а + х сам на себя Комбинаторика - правила, формулы и примеры с решением раз, то получим многочленКомбинаторика - правила, формулы и примеры с решением степени относительно переменной х. Тогда результат можно записать так:

Комбинаторика - правила, формулы и примеры с решением

Чтобы найти значение Комбинаторика - правила, формулы и примеры с решением подставим в обе части равенства (8) вместо х значение 0. Получаем Комбинаторика - правила, формулы и примеры с решением можем записать:

Комбинаторика - правила, формулы и примеры с решением

Чтобы найти Комбинаторика - правила, формулы и примеры с решением сначала возьмем производную от обеих частей равенства (8):

Комбинаторика - правила, формулы и примеры с решением

затем, подставив в обе части полученного равенства (9) х = 0, получим: Комбинаторика - правила, формулы и примеры с решением Учитывая, чтоКомбинаторика - правила, формулы и примеры с решениемможем записать: Комбинаторика - правила, формулы и примеры с решением Аналогично, чтобы найтиКомбинаторика - правила, формулы и примеры с решением возьмем производную от обеих частей равенства (9):

Комбинаторика - правила, формулы и примеры с решением

и, подставив х = 0 в равенство (10), получимКомбинаторика - правила, формулы и примеры с решением Тогда Комбинаторика - правила, формулы и примеры с решениемДругие коэффициенты находят аналогично. Если продифференцироватьКомбинаторика - правила, формулы и примеры с решением раз равенство (8), то получим:

Комбинаторика - правила, формулы и примеры с решением

Подставляя в последнее равенство х = 0, имеем

Комбинаторика - правила, формулы и примеры с решением

Комбинаторика - правила, формулы и примеры с решением

Ориентир:

В каждом ряду по краям стоят единицы, а каждое из остальных чисел равно сумме двух чисел, находящихся над ним справа и слева

Умножим обе части равенства (11) на Комбинаторика - правила, формулы и примеры с решением и найдем коэффициент

Комбинаторика - правила, формулы и примеры с решением. Подставляя найденные значения Комбинаторика - правила, формулы и примеры с решением

1, 2, …,Комбинаторика - правила, формулы и примеры с решением) в равенство (8), получаем равенство (7).Комбинаторика - правила, формулы и примеры с решением

Записывая степень двучлена по формуле бинома Ньютона для небольших значений п, биномиальные коэффициенты можно вычислять по треугольнику Паскаля (табл. 25, см. также табл. 24).

Например,Комбинаторика - правила, формулы и примеры с решением

Так какКомбинаторика - правила, формулы и примеры с решением формулу бинома Ньютона можно записать в виде:

Комбинаторика - правила, формулы и примеры с решением

а учитывая, чтоКомбинаторика - правила, формулы и примеры с решением, еще и так:

Комбинаторика - правила, формулы и примеры с решением

Если в формуле бинома Ньютона (12) заменить х на (-х), то получим формулу возведения в степень разности а – х:

Комбинаторика - правила, формулы и примеры с решением. Например, (Комбинаторика - правила, формулы и примеры с решением (знаки членов разложения чередуются!).

Свойства биномиальных коэффициентов

1. Число биномиальных коэффициентов (а следовательно, и число слагаемых) в разложении Комбинаторика - правила, формулы и примеры с решением-й степени бинома равно Комбинаторика - правила, формулы и примеры с решением + 1, поскольку разложение содержит все степени х от 0 до Комбинаторика - правила, формулы и примеры с решением (и других слагаемых не содержит).

2. Коэффициенты членов, равноудаленных от начала и конца разложения, равны между собой, посколькуКомбинаторика - правила, формулы и примеры с решением

3. Сумма всех биномиальных коэффициентов равна 2″.

Комбинаторика - правила, формулы и примеры с решениемДля обоснования полагаем в равенстве (13) (или в равенстве (7)) значения а = х = 1 и получаем Комбинаторика - правила, формулы и примеры с решением

Например, Комбинаторика - правила, формулы и примеры с решением

4. Сумма биномиальных коэффициентов, стоящих на четных местах, равна сумме биномиальных коэффициентов, стоящих на нечетных местах,

Комбинаторика - правила, формулы и примеры с решением Для обоснования возьмем в равенстве (13) значения а =1, х = —1. Получаем

Комбинаторика - правила, формулы и примеры с решением

Тогда Комбинаторика - правила, формулы и примеры с решением

Примеры решения задач:

Пример №51

По формуле бинома Ньютона найдите разложение степени Комбинаторика - правила, формулы и примеры с решением

Комментарий:

Для нахождения коэффициентов разложения можно использовать треугольник Паскаля или вычислять их по общей формуле. По треугольнику Паскаля коэффициенты равны: 1, 6, 15, 20, 15, б, 1. Учитывая, что при возведении в степень разности знаки членов разложения чередуются, получаем

Комбинаторика - правила, формулы и примеры с решениемДля упрощения записи ответа можно избавиться от иррациональности в знаменателях полученных выражений (см. решение) или сначала учесть, что ОДЗ заданного выражения: х > 0, и тогдаКомбинаторика - правила, формулы и примеры с решением То есть заданное выражение можно записать так: Комбинаторика - правила, формулы и примеры с решениеми возвести в степень последнее выражение.

Решение:

Комбинаторика - правила, формулы и примеры с решением

Пример №52

В разложении степени Комбинаторика - правила, формулы и примеры с решениемнайти член, содержащий Комбинаторика - правила, формулы и примеры с решением

Решение:

► ОДЗ: Комбинаторика - правила, формулы и примеры с решением > 0. ТогдаКомбинаторика - правила, формулы и примеры с решением

Общий член разложения: Комбинаторика - правила, формулы и примеры с решением

По условию член разложения должен содержатьКомбинаторика - правила, формулы и примеры с решением, следовательно,

Комбинаторика - правила, формулы и примеры с решением. Отсюда Комбинаторика - правила, формулы и примеры с решением

Тогда член разложения, содержащий Комбинаторика - правила, формулы и примеры с решением, равенКомбинаторика - правила, формулы и примеры с решением

Комментарий:

На ОДЗ (b > 0) каждое слагаемое в заданном двучлене можно записать как степень с дробным показателем. Это позволит проще записать общий член разложения степениКомбинаторика - правила, формулы и примеры с решением: Комбинаторика - правила, формулы и примеры с решением (где Комбинаторика - правила, формулы и примеры с решением = 0, 1, 2, …, Комбинаторика - правила, формулы и примеры с решением), выяснить, какой из членов разложения содержит Комбинаторика - правила, формулы и примеры с решением, и записать его.

Чтобы упростить запись общего члена разложения, удобно отметить, чтоКомбинаторика - правила, формулы и примеры с решением

Зачем нужна комбинаторика

Для решения задач с использованием классического определения вероятности необходимо знать основные правила и формулы комбинаторики -раздела математики, изучающего методы решения комбинаторных задач – т.е. задач, связанных с подсчетом числа различных комбинаций.

Пусть Комбинаторика - правила, формулы и примеры с решением – элементы конечного множества. Сформулируем два важных правила, часто применяемых при решении комбинаторных задач.

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

Если элемент Комбинаторика - правила, формулы и примеры с решением может быть выбран Комбинаторика - правила, формулы и примеры с решением способами, элемент /Комбинаторика - правила, формулы и примеры с решением способами, …, элемент Комбинаторика - правила, формулы и примеры с решением способами, то выбор одного из элементов Комбинаторика - правила, формулы и примеры с решением может быть осуществлен пКомбинаторика - правила, формулы и примеры с решениемспособами.

Пример №53

В группе 30 студентов. Известно, что 5 из них на экзамене по математике получили оценку «отлично», 10 – оценку «хорошо», остальные -«удовлетворительно». Сколько существует способов выбрать одного студента, получившего на экзамене оценку «отлично» или «хорошо»?

Решение:

Студент, получивший оценку «отлично» может быть выбранКомбинаторика - правила, формулы и примеры с решениемспособами, оценку «хорошо» – Комбинаторика - правила, формулы и примеры с решением способами. По правилу суммы существует Комбинаторика - правила, формулы и примеры с решением способов выбора одного студента, получившего на экзамене оценку «отлично» или «хорошо». Комбинаторика - правила, формулы и примеры с решением

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

Если элемент Комбинаторика - правила, формулы и примеры с решениемможет быть выбран Комбинаторика - правила, формулы и примеры с решением способами, после этого элемент Комбинаторика - правила, формулы и примеры с решением может быть выбран Комбинаторика - правила, формулы и примеры с решением способами после каждого такого выбора элемент Комбинаторика - правила, формулы и примеры с решением может быть выбран Комбинаторика - правила, формулы и примеры с решением способами, то выбор всех элементовКомбинаторика - правила, формулы и примеры с решением в указанном порядке может быть осуществлен Комбинаторика - правила, формулы и примеры с решением способами.

Пример №54

В группе 30 студентов. Необходимо выбрать старосту, его заместителя и профорга. Сколько существует способов это сделать?

Решение:

Старостой может быть выбран любой из 30 студентов, его заместителем – любой из оставшихся 29, а профоргом – любой из оставшихся 28 студентов, т.е. Комбинаторика - правила, формулы и примеры с решением По правилу произведения общее число способов выбора старосты, его заместителя и профорга равно Комбинаторика - правила, формулы и примеры с решением = = 24360 способов. ◄

Пусть дано множество из n различных элементов. Из этого множества могут быть образованы подмножества из m элементов (0 ≤ m ≤n). Например, из 5 элементов a, b, c, d, e могут быть отобраны комбинации по 2 элемента – ab, bc, cd, ba и т.д., по 3 элемента – abc, cbd, cba и т.д.

Если комбинации из n элементов по m отличаются либо составом элементов, либо порядком их расположения (либо и тем и другим), то такие комбинации называют размещениями из n элементов по m. Число размещений из n элементов по m находится по формуле Комбинаторика - правила, формулы и примеры с решением где n! равно произведению n первых чисел натурального ряда, т.е. n! = 1·2·…·n.

Пример №55

Сколько можно записать двузначных чисел, используя без повторения цифры от 1 до 5?

Решение:

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

Комбинаторика - правила, формулы и примеры с решением Если комбинации из n элементов по m отличаются только с о с т а в о м элементов (порядок их расположения не имеет значения), то такие комбинации называют сочетаниями из n элементов по m.

Число сочетаний из n элементов по m находится по формуле Комбинаторика - правила, формулы и примеры с решением

Пример №56

Необходимо выбрать в подарок две из пяти имеющихся различных книг. Сколькими способами можно это сделать?

Решение:

Из смысла задачи следует, что порядок выбора книг не имеет значения. Здесь важен только их состав. Поэтому в данном случае комбинации книг представляют собой сочетания из 5 книг по 2. Число таких комбинаций Комбинаторика - правила, формулы и примеры с решением Если в размещениях из n элементов по m некоторые из элементов (или все) могут оказаться одинаковыми, то такие размещения называют размещениями с повторениями из n элементов по m. Число размещений с повторениями равно Комбинаторика - правила, формулы и примеры с решением

Пример №57

Сколько можно записать трехзначных чисел, которые не содержат цифр 0 и 5?

Решение:

В данном случае трехзначное число является комбинацией из восьми цифр (0 и 5 не учитываются) по три цифры. При этом некоторые из цифр (или все) могут повторяться. Поэтому в данном случае трехзначные числа является размещениями с повторениями из восьми цифр по три. Число таких размещений с повторениями Комбинаторика - правила, формулы и примеры с решением Если в сочетаниях из n элементов по m некоторые из элементов (или все) могут оказаться одинаковыми, то такие сочетания называют сочетаниями с повторениями из n элементов по m. Число сочетаний с повторениями равно Комбинаторика - правила, формулы и примеры с решением где Комбинаторика - правила, формулы и примеры с решением определяется по формуле (1.6).

Пример №58

В почтовом отделении продаются открытки восьми видов. Сколькими способами можно купить в нем три открытки?

Решение:

Учитывая, что порядок выбора открыток не имеет значения, а важен только их состав, причем некоторые из открыток (или все) могут оказаться одинаковыми, искомое число способов находим по формуле числа сочетаний с повторениями Комбинаторика - правила, формулы и примеры с решением Если комбинации из n элементов отличаются только порядком расположения элементов, то такие комбинации называют перестановками из n элементов. Число перестановок из n элементов находится по формуле Комбинаторика - правила, формулы и примеры с решением

Пример №59

Порядок выступления 5 участников конкурса определяется жребием. Сколько различных вариантов жеребьевки при этом возможно?

Решение:

Каждый вариант жеребьевки отличается только порядком участников конкурса, т.е. является перестановкой из 5 элементов. Их число равно Комбинаторика - правила, формулы и примеры с решением Если в перестановках из общего числа n элементов есть k различных элементов, при этом 1-й элемент повторяетсяКомбинаторика - правила, формулы и примеры с решением раз, 2-й элемент – Комбинаторика - правила, формулы и примеры с решением раз, k-й элемент – Комбинаторика - правила, формулы и примеры с решением раз, причемКомбинаторика - правила, формулы и примеры с решением, то такие перестановки называют перестановками с повторениями из n элементов. Число перестановок с повторениями равно Комбинаторика - правила, формулы и примеры с решением

Пример №60

Сколько можно составить шестизначных чисел, состоящих из цифр 3, 5, 7, в которых цифра 3 повторяется 3 раза, цифра 5 – 2 раза, цифра 7 – 1 раз?

Решение:

Каждое шестизначное число отличается от другого порядком следования цифр (причем Комбинаторика - правила, формулы и примеры с решением а их сумма равна 6), т.е. является перестановкой с повторениями из 6 элементов. Их число равно

Комбинаторика - правила, формулы и примеры с решением

  • Классическое определение вероятности
  • Геометрические вероятности
  • Теоремы сложения и умножения вероятностей
  • Формула полной вероятности 
  • Математическая обработка динамических рядов 
  • Корреляция – определение и вычисление
  • Элементы теории ошибок
  • Методы математической статистики

Число размещений без повторений

Число размещений
без повторений из
n
по
k
– это число
способов, сколькими можно из n
различных элементов построить векторов
с k
различными координатами.

Число размещений
без повторений находится по формуле:

.

Пример:
Сколькими способами можно построить
3-значное число с различными цифрами,
не содержащее цифры 0?

Количество цифр
,
размерность вектора с различными
координатами

Число размещений с повторениями

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

Число размещений
с повторениями находится по формуле:

.

Пример:
Сколько слов длины 6 можно составить из
26 букв латинского алфавита?

Количество букв
,
размерность вектора

Число перестановок без повторений

Число перестановок
без повторений из
n
элементов

– это число способов, сколькими можно
расположить на n
различных местах n
различных элементов.

Число перестановок
без повторений находится по формуле:

.

Замечание:
Мощность искомого множества А
удобно искать по формуле:
,
гдех
– число способов выбрать нужные места;
у
– число
способов расположить на них нужные
элементы; z – число
способов расположить остальные элементы
на оставшихся местах.

Пример.
Сколькими способами можно расставить
на книжной полке 5 различных книг? В
скольких случаях две определенные книги
А и В окажутся рядом?

Всего способов
расставить 5 книг на 5-ти местах – равно
= 5! = 120.

В задаче х
– число способов выбрать два места
рядом, х = 4;
у
– число
способов расположить две книги на двух
местах, у = 2! = 2;
z – число
способов расположить остальные 3 книги
на оставшихся 3-х местах,  = 3! = 6.
Значит
=
48.

Число сочетаний без повторений

Число сочетаний
без повторений из
n
по
k
– это число
способов, сколькими можно из n
различных элементов выбрать k
штук без учета порядка.

Число сочетаний
без повторений находится по формуле:

.

Свойства:

1)
;
2);
3);

4)
;
5);
6).

Пример.
В урне 7 шаров. Из них 3 белых. Наугад
выбирают 3 шара. Сколькими способами
это можно сделать? В скольких случаях
среди них будет ровно один белый.

Всего способов
.
Чтобы получить число способов выбрать
1 белый шар (из 3-х белых) и 2 черных шара
(из 4-х черных), надо перемножитьиТаким образом искомое количество
способов

Упражнения

1. Из 35 учащихся
класс по итогам года имели “5” по
математике – 14 человек; по физике – 15
человек; по химии – 18 человек; по
математике и физике – 7 человек; по
математике и химии – 9 человек; по физике
и химии – 6 человек; по всем трем предметам
– 4 человек. Сколько человек имеют “5”
по указанным предметам? Сколько человек
не имеет “5” по указанным предметам?
Имеет “5” только по математике? Имеет
“5” только по двум предметам?

2. В группе из 30
студентов каждый знает, по крайней мере,
один иностранный язык – английский или
немецкий. Английский знают 22 студента,
немецкий – 17. Сколько студентов знают
оба языка? Сколько студентов знают
немецкий язык, но не знают английский?

3. В 20 комнатах
общежития института Дружбы Народов
живут студенты из России; в 15 – из Африки;
в 20 – из стран Южной Америки. Причем в
7 – живут россияне и африканцы, в 8 –
россияне и южноамериканцы; в 9 – африканцы
и южноамериканцы; в 3 – и россияне, и
южноамериканцы, и африканцы. В скольких
комнатах живут студенты: 1) только с
одного континента; 2) только с двух
континентов; 3) только африканцы.

4. Каждый из 500
студентов обязан посещать хотя бы один
из трех спецкурсов: по математике, физике
и астрономии. Три спецкурса посещают
10 студентов, по математике и физике –
30 студентов, по математике и астрономии
– 25; спецкурс только по физике – 80
студентов. Известно также, что спецкурс
по математике посещают 345 студентов, по
физике – 145, по астрономии – 100 студентов.
Сколько студентов посещают спецкурс
только по астрономии? Сколько студентов
посещают два спецкурса?

5. Староста курса
представил следующий отчет по физкультурной
работе. Всего – 45 студентов. Футбольная
секция – 25 человек, баскетбольная секция
– 30 человек, шахматная секция – 28
человек. При этом, 16 человек одновременно
посещают футбольную и баскетбольную
секции, 18 – футбольную и шахматную, 17 –
баскетбольную и шахматную, 15 человек
посещают все три секции. Объясните,
почему отчет не был принят.

6. В аквариуме 11
рыбок. Из них 4 красных, остальные золотые.
Наугад выбирают 4 рыбки. Сколькими
способами это можно сделать? Найти число
способов сделать это так, чтобы среди
них будет: 1) ровно одна красная; 2) ровно
2 золотых; 3) хотя бы одна красная.

7. В списке 8 фамилий.
Из них 4 – женские. Сколькими способами
их можно разделить на две равные группы
так, чтоб в каждой была женская фамилия?

8. Из колоды в 36
карт выбирают 4 . Сколько способов сделать
это так, чтобы: 1) все карты были разных
мастей; 2) все карты были одной масти;
3) 2 красные и 2 черные.

9. На карточках
разрезной азбуки даны буквы К, К, К, У,
У, А, Е, Р. Сколько способов сложить их в
ряд так, что бы получилось «кукареку».

10. Даны карточки
разрезанной азбуки с буквами О, Т, О, Л,
О, Р, И, Н, Г, О, Л, О, Г. Сколько способов
сложить их так, что бы получилось слово
«отолоринголог».

11. Даны карточки
нарезной азбуки с буквами Л, И, Т, Е, Р,
А, Т, У, Р, А. Сколько способов сложить их
в ряд так, что бы получилось слово
«литература».

12. 8 человек
становятся в очередь. Сколько способов
сделать это так, что бы два определенных
человека А и Б оказались: 1) рядом; 2) на
краях очереди;

13. 10 человек садятся
за круглый стол на 10 мест. Сколькими
способами это можно сделать так, чтоб
рядом оказались: 1) два определенных
человека А и Б; 2) три определенных
человека А, Б и С.

14. Из 10 арабских
цифр составляют 5-значный код. Сколькими
способами это можно сделать так, чтобы:
1) все цифры были разными; 2) на последнем
месте четная цифра.

15. Из 26 букв
латинского алфавита (среди них 6 гласных)
составляется шестибуквенное слово.
Сколькими способами это можно сделать
так, чтобы в слове были: 1) ровно одна
буква «а»; 2) ровно одна гласная буква;
ровно две буквы «а»; в) ровно две гласные.

16. Сколько
четырехзначных чисел делятся на 5?

17. Сколько
четырехзначных чисел с различными
цифрами делятся на 25?

19. Брошены 3 игральные
кости. В скольких случаях выпала:
1) ровно 1 «шестерка»; 2) хотя бы
одна «шестерка».

20. Брошены 3 игральные
кости. В скольких случаях будет: 1) все
разные; 2) ровно два одинаковых числа
очков.

21. Сколько слов с
различными буквами можно составить из
алфавита а, в, с, d.
Перечислить их все в лексикографическом
порядке: abcd,
abcd….

Соседние файлы в папке Дискретная математика

  • #
  • #
  • #
  • #
  • #
  • #
  • #

Перестановки, размещения и сочетания. Формулы.

Чтобы в материале было легче ориентироваться, добавлю содержание данной темы:

  1. Введение. Множества и выборки.
  2. Размещения без повторений из $n$ элементов по $k$.
  3. Размещения с повторениями из $n$ элементов по $k$.
  4. Перестановки без повторений из $n$ элементов
  5. Перестановки с повторениями.
  6. Сочетания без повторений из $n$ элементов по $k$.
  7. Сочетания с повторениями из $n$ элементов по $k$.

Введение. Множества и выборки.

В этой теме рассмотрим основные понятия комбинаторики: перестановки, сочетания и размещения. Выясним их суть и формулы, по которым можно найти их количество.

Для работы нам понадобятся кое-какие вспомогательные сведения. Начнём с такого фундаментального математического понятия как множество. Подробно понятие множества было раскрыто в теме “Понятие множества. Способы задания множеств”.

Очень краткий рассказ про множества: показатьскрыть

Рассмотрим некое непустое конечное множество $U$, мощность которого равна $n$, $|U|=n$ (т.е. в множестве $U$ имеется $n$ элементов). Введём такое понятие, как выборка (некоторые авторы именуют её кортежем). Под выборкой объема $k$ из $n$ элементов (сокращённо $(n,k)$-выборкой) будем понимать набор элементов $(a_1, a_2,ldots, a_k)$, где $a_iin U$. Выборка называется упорядоченной, если в ней задан порядок следования элементов. Две упорядоченные выборки, различающиеся лишь порядком элементов, являются различными. Если порядок следования элементов выборки не является существенным, то выборку именуют неупорядоченной.

Заметьте, что в определении выборки ничего не сказано про повторения элементов. В отличие от элементов множеств, элементы выборки могут повторяться.

Для примера рассмотрим множество $U={a,b,c,d,e}$. Множество $U$ содержит 5 элементов, т.е. $|U|=5$. Выборка без повторений может быть такой: $(a,b,c)$. Данная выборка содержит 3 элемента, т.е. объём этой выборки равен 3. Иными словами, это $(5,3)$-выборка.

Выборка с повторениями может быть такой: $(a,a,a,a,a,c,c,d)$. Она содержит 8 элементов, т.е. объём её равен 8. Иными словами, это $(5,8)$-выборка.

Рассмотрим ещё две $(5,3)$-выборки: $(a,b,b)$ и $(b,a,b)$. Если мы полагаем наши выборки неупорядоченными, то выборка $(a,b,b)$ равна выборке $(b,a,b)$, т.е. $(a,b,b)=(b,a,b)$. Если мы полагаем наши выборки упорядоченными, то $(a,b,b)neq(b,a,b)$.

Рассмотрим ещё один пример, немного менее абстрактный 🙂 Предположим, в корзине лежат шесть конфет, причём все они различны. Если первой конфете поставить в соответствие цифру 1, второй конфете – цифру 2 и так далее, то с конфетами в корзине можно сопоставить такое множество: $U={1,2,3,4,5,6}$. Представьте, что мы наугад запускаем руку в корзинку с целью вытащить три конфеты. Вытащенные конфеты – это и есть выборка. Так как мы вытаскиваем 3 конфеты из 6, то получаем (6,3)-выборку. Порядок расположения конфет в ладони совершенно несущественен, поэтому эта выборка является неупорядоченной. Ну, и так как все конфеты различны, то выборка без повторений. Итак, в данной ситуации говорим о неупорядоченной (6,3)-выборке без повторений.

Теперь подойдём с иной стороны. Представим себе, что мы находимся на фабрике по производству конфет, и на этой фабрике производятся конфеты четырёх сортов. Множество $U$ в этой ситуации таково: $U={1,2,3,4 }$ (каждая цифра отвечает за свой сорт конфет). Теперь вообразим, что все конфеты ссыпаются в единый жёлоб, около которого мы и стоим. И, подставив ладони, из этого потока отбираем 20 конфет. Конфеты в горсти – это и есть выборка. Играет ли роль порядок расположения конфет в горсти? Естественно, нет, поэтому выборка неупорядоченная. Всего 4 сорта конфет, а мы отбираем двадцать штук из общего потока – повторения сортов неизбежны. При этом выборки могут быть самыми различными: у нас даже могут оказаться все конфеты одного сорта. Следовательно, в этой ситуации мы имеем дело с неупорядоченной (4,20)-выборкой с повторениями.

Рассмотрим ещё пару примеров. Пусть на кубиках написаны различные 7 букв: к, о, н, ф, е, т, а. Эти буквы образуют множество $U={к,о,н,ф,е,т,а}$. Допустим, из данных кубиков мы хотим составить “слова” из 5 букв. Буквы этих слов (к примеру, «конфе», «тенко» и так далее) образуют (7,5)-выборки: $(к,о,н,ф,е)$, $(т,е,н,к,о)$ и т.д. Очевидно, что порядок следования букв в такой выборке важен. Например, слова «нокфт» и «кфтон» различны (хотя состоят из одних и тех же букв), ибо в них не совпадает порядок букв. Повторений букв в таких «словах» нет, ибо в наличии только семь кубиков. Итак, набор букв каждого слова представляет собой упорядоченную (7,5)-выборку без повторений.

Еще один пример: мы составляем всевозможные восьмизначные числа из четырёх цифр 1, 5, 7, 8. Например, 11111111, 15518877, 88881111 и так далее. Множество $U$ таково: $U={1,5,7,8}$. Цифры каждого составленного числа образуют (4,8)-выборку. Порядок следования цифр в числе важен, т.е. выборка упорядоченная. Повторения допускаются, поэтому здесь мы имеем дело с упорядоченной (4,8)-выборкой с повторениями.

Размещения без повторений из $n$ элементов по $k$

Размещение без повторений из $n$ элементов по $k$ – упорядоченная $(n,k)$-выборка без повторений.

Так как элементы в рассматриваемой выборке повторяться не могут, то мы не можем отобрать в выборку больше элементов, чем есть в исходном множестве. Следовательно, для таких выборок верно неравенство: $n≥ k$. Количество размещений без повторений из $n$ элементов по $k$ определяется следующей формулой:

$$
begin{equation}
A_{n}^{k}=frac{n!}{(n-k)!}
end{equation}
$$

Что обозначает знак “!”? : показатьскрыть

Пример №1

Алфавит состоит из множества символов $E={+,*,0,1,f}$. Определим количество таких трёхсимвольных слов в этом алфавите, которые не содержат повторяющихся букв.

Решение

Под трёхсимвольными словами будем понимать выражения вида “+*0” или “0f1”. В множестве $E$ пять элементов, поэтому буквы трехсимвольных слов образуют (5,3)-выборки. Первый вопрос: эти выборки упорядочены или нет? Слова, которые отличаются лишь порядком букв, полагаются различными, поэтому порядок элементов в выборке важен. Значит, выборка является упорядоченной. Второй вопрос: допускаются повторения или нет? Ответ на этот вопрос даёт условие: слова не должны содержать повторяющихся букв. Подводим итоги: буквы каждого слова, удовлетворяющего условию задачи, образуют упорядоченную (5,3)-выборку без повторений. Иными словами, буквы каждого слова образуют размещение без повторений из 5 элементов по 3. Вот примеры таких размещений:

$$
(+,*,f), ; (*,+,f), ; (1,+,0)
$$

Нас же интересует общее количество этих размещений. Согласно формуле (1) количество размещений без повторений из 5 элементов по 3 будет таким:

$$
A_{5}^{3}=frac{5!}{(5-3)!}=frac{5!}{2!}=60.
$$

Т.е. можно составить 60 трёхсимвольных слов, буквы которых не будут повторяться.

Ответ: 60.

Размещения с повторениями из $n$ элементов по $k$

Размещение с повторениями из $n$ элементов по $k$ – упорядоченная $(n,k)$-выборка с повторениями.

Количество размещений с повторениями из $n$ элементов по $k$ определяется следующей формулой:

$$
begin{equation}
bar{A}_{n}^{k}=n^k
end{equation}
$$

Пример №2

Сколько пятизначных чисел можно составить из множества цифр ${5,7,2}$?

Решение

Из данного набора цифр можно составить пятизначные числа 55555, 75222 и так далее. Цифры каждого такого числа образуют (3,5)-выборку: $(5,5,5,5,5)$, $(7,5,2,2,2)$. Зададимся вопросом: что это за выборки? Во-первых, цифры в числах могут повторяться, поэтому мы имеем дело с выборками с повторениями. Во-вторых, порядок расположения цифр в числе важен. Например, 27755 и 77255 – разные числа. Следовательно, мы имеем дело с упорядоченными (3,5)-выборками с повторениями. Общее количество таких выборок (т.е. общее количество искомых пятизначных чисел) найдём с помощью формулы (2):

$$
bar{A}_{3}^{5}=3^5=243.
$$

Следовательно, из заданных цифр можно составить 243 пятизначных числа.

Ответ: 243.

Перестановки без повторений из $n$ элементов

Перестановка без повторений из $n$ элементов – упорядоченная $(n,n)$-выборка без повторений.

По сути, перестановка без повторений есть частный случай размещения без повторений, когда объём выборки равен мощности исходного множества. Количество перестановок без повторений из $n$ элементов определяется следующей формулой:

$$
begin{equation}
P_{n}=n!
end{equation}
$$

Эту формулу, кстати, легко получить, если учесть, что $P_n=A_{n}^{n}$. Тогда получим:

$$
P_n=A_{n}^{n}=frac{n!}{(n-n)!}=frac{n!}{0!}=frac{n!}{1}=n!
$$

Пример №3

В морозилке лежат пять порций мороженого от различных фирм. Сколькими способами можно выбрать порядок их съедения?

Решение

Пусть первому мороженому соответствует цифра 1, второму – цифра 2 и так далее. Мы получим множество $U={1,2,3,4,5}$, которое будет представлять содержимое морозилки. Порядок съедения может быть таким: $(2,1,3,5,4)$ или таким: $(5,4,3,1,2)$. Каждый подобный набор есть (5,5)-выборка. Она будет упорядоченной и без повторений. Иными словами, каждая такая выборка есть перестановка из 5 элементов исходного множества. Согласно формуле (3) общее количество этих перестановок таково:

$$
P_5=5!=120.
$$

Следовательно, существует 120 порядков выбора очередности съедения.

Ответ: 120.

Перестановки с повторениями

Перестановка с повторениями – упорядоченная $(n,k)$-выборка с повторениями, в которой элемент $a_1$ повторяется $k_1$ раз, $a_2$ повторяется $k_2$ раза так далее, до последнего элемента $a_r$, который повторяется $k_r$ раз. При этом $k_1+k_2+ldots+k_r=k$.

Общее количество перестановок с повторениями определяется формулой:

$$
begin{equation}
P_{k}(k_1,k_2,ldots,k_r)=frac{k!}{k_1!cdot k_2!cdot ldots cdot k_r!}
end{equation}
$$

Пример №4

Слова составляются на основе алфавита $U={a,b,d}$. Сколько различных слов из семи символов может быть составлено, если в этих словах буква “a” должна повторяться 2 раза; буква “b” – 1 раз, а буква “d” – 4 раза?

Решение

Вот примеры искомых слов: “aabdddd”, “daddabd” и так далее. Буквы каждого слова образуют (3,7)-выборку с повторениями: $(a,a,b,d,d,d,d)$, $(d,a,d,d,a,b,d)$ и т.д. Каждая такая выборка состоит из двух элементов “a”, одного элемента “b” и четырёх элементов “d”. Иными словами, $k_1=2$, $k_2=1$, $k_3=4$. Общее количество повторений всех символов, естественно, равно объёму выборки, т.е. $k=k_1+k_2+k_3=7$. Подставляя эти данные в формулу (4), будем иметь:

$$
P_7(2,1,4)=frac{7!}{2!cdot 1!cdot 4!}=105.
$$

Следовательно, общее количество искомых слов равно 105.

Ответ: 105.

Сочетания без повторений из $n$ элементов по $k$

Сочетание без повторений из $n$ элементов по $k$ – неупорядоченная $(n,k)$-выборка без повторений.

Общее количество сочетаний без повторений из $n$ элементов по $k$ определяется формулой:

$$
begin{equation}
C_{n}^{k}=frac{n!}{(n-k)!cdot k!}
end{equation}
$$

Пример №5

В корзине размещены карточки, на которых написаны целые числа от 1 до 10. Из корзины вынимают 4 карточки и суммируют числа, написанные на них. Сколько различных наборов карточек можно вытащить из корзины?

Решение

Итак, в данной задаче исходное множество таково: $U={1,2,3,4,5,6,7,8,9,10}$. Из этого множества мы выбираем четыре элемента (т.е., четыре карточки из корзины). Номера вытащенных элементов образуют (10,4)-выборку. Повторения в этой выборке не допускаются, так как номера всех карточек различны. Вопрос вот в чём: порядок выбора карточек играет роль или нет? Т.е., к примеру, равны ли выборки $(1,2,7,10)$ и $(10,2,1,7)$ или не равны? Тут нужно обратиться к условию задачи. Карточки вынимаются для того, чтобы потом найти сумму элементов. А это значит, что порядок карточек не важен, так как от перемены мест слагаемых сумма не изменится. Например, выборке $(1,2,7,10)$ и выборке $(10,2,1,7)$ будет соответствовать одно и то же число $1+2+7+10=10+2+1+7=20$. Вывод: из условия задачи следует, что мы имеем дело с неупорядоченными выборками. Т.е. нам нужно найти общее количество неупорядоченных (10,4)-выборок без повторений. Иными словами, нам нужно найти количество сочетаний из 10 элементов по 4. Используем для этого формулу (5):

$$
C_{10}^{4}=frac{10!}{(10-4)!cdot 4!}=frac{10!}{6!cdot 4!}=210.
$$

Следовательно, общее количество искомых наборов равно 210.

Ответ: 210.

Сочетания с повторениями из $n$ элементов по $k$

Сочетание с повторениями из $n$ элементов по $k$ – неупорядоченная $(n,k)$-выборка с повторениями.

Общее количество сочетаний с повторениями из $n$ элементов по $k$ определяется формулой:

$$
begin{equation}
bar{C}_{n}^{k}=frac{(n+k-1)!}{(n-1)!cdot k!}
end{equation}
$$

Пример №6

Представьте себе, что мы находимся на конфетном заводе, – прямо возле конвейера, по которому движутся конфеты четырёх сортов. Мы запускаем руки в этот поток и вытаскиваем двадцать штук. Сколько всего различных “конфетных комбинаций” может оказаться в горсти?

Решение

Если принять, что первому сорту соответствует число 1, второму сорту – число 2 и так далее, то исходное множество в нашей задаче таково: $U={1,2,3,4}$. Из этого множества мы выбираем 20 элементов (т.е., те самые 20 конфет с конвейера). Пригоршня конфет образует (4,20)-выборку. Естественно, повторения сортов будут. Вопрос в том, играет роль порядок расположения элементов в выборке или нет? Из условия задачи следует, что порядок расположения элементов роли не играет. Нам нет разницы, будут ли в горсти располагаться сначала 15 леденцов, а потом 4 шоколадных конфеты, или сначала 4 шоколадных конфеты, а уж потом 15 леденцов. Итак, мы имеем дело с неупорядоченной (4,20) выборкой с повторениями. Чтобы найти общее количество этих выборок используем формулу (6):

$$
bar{C}_{4}^{20}=frac{(4+20-1)!}{(4-1)!cdot 20!}=frac{23!}{3!cdot 20!}=1771.
$$

Следовательно, общее количество искомых комбинаций равно 1771.

Ответ: 1771.

Комбинаторика в школе теперь изучается с начальной школы.

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

Рассмотрим сегодня, чем отличаются следующие условия: перестановка, размещение, сочетание.

Перестановка

Берутся все элементы и меняются только их места.

Например:

Сколько трехзначных чисел можно составить из цифр 1, 2, 6 без повторения цифр в числе?

Чтобы получить трехзначные числа без повторения необходимо переставить данные цифры.

126, 162, 216, 261, 621, 612.

Всего 6 вариантов.

Если речь пойдет о четырехзначном числе, то комбинаций получится гораздо больше. Но это количество подчиняется закону:

Перестановка, размещение и сочетание в комбинаторике. Разбираемся, в чем отличия

“!” – знак факториала.

Факториал числа — это произведение натуральных чисел от 1 до самого числа (включая данное число).

Сколько четырехзначных чисел можно получить из цифр 3, 7 , 4, 2 без повторения цифр в числе?

Перестановка, размещение и сочетание в комбинаторике. Разбираемся, в чем отличия

А теперь тоже самое, только с небольшим подвохом.

Сколько четырехзначных чисел можно получить из цифр 3, 0 , 4, 2 без повторения цифр в числе?

Подумайте какие числа необходимо исключить из подсчета и какое их количество?

Размещение

Размещения – это упорядоченные совокупности элементов, отличающиеся друг от друга либо составом, либо порядком элементов.

Для более простого понимания размещения рассмотрим следующий пример.

Есть буквы А, Б, В и Г. Сколько комбинаций из 2ух различных букв можно получить?

AБ, АВ, АГ, БА, БВ, БГ, ВА, ВБ, ВГ, ГА, ГБ, ГВ

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

В данном примере n=4, k=2, т.е. это размещение из 4 по 2 без повторения.

Общая формула, по которой можно всегда рассчитать число размещений без повторения:

Перестановка, размещение и сочетание в комбинаторике. Разбираемся, в чем отличия

Для создания 3-значного пароля используются символы из алфавита {+,*,A,!,2}. Сколько всего паролей без повторения символов можно составить?

По условию задачи n=5, k=3.

Перестановка, размещение и сочетание в комбинаторике. Разбираемся, в чем отличия

А если элементы могут повторяться?

Тогда

Перестановка, размещение и сочетание в комбинаторике. Разбираемся, в чем отличия

Смотрите как поменяется решение, если убрать одну фразу из задачи

Для создания 3-значного пароля используются символы из алфавита {+,*,A,!,2}. Сколько всего паролей без повторения символов можно составить?

Перестановка, размещение и сочетание в комбинаторике. Разбираемся, в чем отличия

Сочетание

Сочетание отличается от размещения тем, что в этом случае не важен порядок элементов.

В классе 4 человека (Петя, Света, Игорь, Ваня) наиболее успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде?

В данном случае комбинация ПС и СП будет одной и той же (Света и Петя)

Давайте посмотрим сколько сочетаний можно получить в данном примере:

ПС, ПИ, ПВ, СИ, СВ, ИВ

Т.е. всего 6 вариантов.

Есть и для сочетаний своя формула:

Перестановка, размещение и сочетание в комбинаторике. Разбираемся, в чем отличия

В классе 8 человек наиболее успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде?

Перестановка, размещение и сочетание в комбинаторике. Разбираемся, в чем отличия

Заданий связанных с комбинаторикой на экзамене в 9-ом классе НЕТ, но они могут косвенно встретиться в задании 10 на теорию вероятности.

Понимание таких тем будет полезно в дальнейшем…

Всем успешной подготовки

Продолжение следует…

Не забудь нажать на пальчик вверх после прочтения и подписаться. За это отдельная благодарность

(✿◠‿◠)

Перестановка, размещение и сочетание в комбинаторике. Разбираемся, в чем отличия

Добавить комментарий