Сделай Сам Свою Работу на 5

Материалы для семинаров (для обязательного решения предлагаются задачи с номерами 1, 2, 7, 8, 9, 10, остальные задачи приведены в качестве дополнительного материала)





 

ОТВЕТЫ ДЛЯ САМОКОНТРОЛЯ

 

 

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

 

Задачи комбинаторики.

 

1. Найти количество объектов, удовлетворяющих некоторым условиям.

2. Занумеровать их и построить алгоритм нахождения элемента по номеру и номера по элементу.

 

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

 

Если А содержит n элементов, множество В содержит m элементов, то множество пар вида (ai, bj), где ai Î А, bj Î B, содержит mn элементов.

 

Пример

 

Сколько способов поставить две шахматные ладьи на доску 8х8 так, чтобы они не «били» друг друга?

Решение.

Есть 64 способа поставить первую ладью, и на каждый из них приходится по 49 способов поставить вторую ладью (поскольку первая ладья занимает одну клетку, и бьёт при этом 14 клеток, то остаётся 49 клеток для второй ладьи). Таким образом, получим 64 × 49 вариантов расстановки двух ладей.

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

64 × 49 / 2 = 1568.

Ответ. 1568.

Пример 2

 

Сколько существует трёхзначных чисел, у которых все цифры различны?



Решение. Для первой цифры 9 вариантов, от 1 до 9. Когда её выбрали, для второй цифры тоже 9 вариантов, поскольку она не должна совпасть с первой. Когда выбрали первые две цифры, то для третьей осталось 8 вариантов.

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

Ответ: 648.

Правило сложения

 

Идея рассуждения – разбить все варианты на группы, каждая из которых состоит из «одинаково устроенных» комбинаций.

 

Пример

 

Сколько способов поставить двух шахматных королей на доску 8х8 так, чтобы они не «били» друг друга?

 

Решение.

В данном случае количество полей, которое «бьёт» король, зависит от его положения на доске.

Если он в углу (4 варианта), то для второго короля свободны 60 полей, если у края доски (24 варианта), то свободны 58 полей, а если отстоит не в углу и не у края (36 вариантов), то свободны 55 полей.

Таким образом, получим 4 × 60 + 24 × 58 + 36 × 55 = 3612. Разделив это количество пополам (по той же причине, что в предыдущем примере), получим 1806.

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

Перестановкой называют упорядоченный набор чисел 1, 2, 3, … n, возможно, переставленных в другом порядке – например, 3, 2, 1, 4, 5, 6, …, n.



Первый элемент перестановки можно выбрать n способами, тогда второй останется (n-1) способов, на третий – (n-2) способа, и так далее до заключительного элемента, для которого останется ровно один вариант.

Таким образом, количество перестановок равно n(n-1)(n-2)× … × 2×1 = n!

 

Примечание. n! здесь и далее обозначает произведение всех целых чисел от 1 до n. В задачах по комбинаторике принято оставлять в ответе факториалы, степени, произведения, поскольку число в ответе задачи может оказаться большим, и его вычисление займёт слишком много времени.

 

Пример.

Сколько способов посадить 5 человек на 5 стульев, по одному человеку на стул?

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

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

 

Если множество содержит n элементов, а наборы должны содержать k элементов, то каждый элемент можем выбрать n способами, всего элементов k, поэтому количество размещений с повторениями равно nk.

 

Пример.

Сколько существует 4-значных чисел, все цифры в которых нечётны?

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

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

 

Если множество содержит n элементов, а наборы должны содержать k элементов, то первый элемент можем выбрать n способами, второй (n-1) способом, и так далее до элемента номер k, его можем выбрать (n – k +1) способом. Поэтому количество размещений без повторений равно n(n - 1)…( n – k +1) = n! / (n-k)!



Пример.

Сколько существует 4-значных чисел, все цифры в которых нечётны и различны?

Сочетания

- число k-элементных подмножеств n-элементного множества (читается как «число сочетаний из n по k»).

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

Упорядоченных наборов k элементов из n существует n!/(n-k)! Если будем рассматривать неупорядоченные наборы, то каждый из них сосчитаем по k! раз.

Поэтому неупорядоченных наборов в k! раз меньше, чем упорядоченных.

Поэтому количество неупорядоченных наборов вычисляется по формуле: n!/((n-k)!k!).

Пример.

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

 

Можно вычислять по формуле: 25!/(22!∙3!)

Можно и с помощью логических рассуждений. Первого дежурного можно выбрать 25 способами, второго – 24 способами, третьего – 22 способами. Всего получаем 25 ∙ 24 ∙ 22 способа.

 

Переход к дополнению

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

 

Пример.

 

Сколько существует 5-значных чисел, в которых есть хотя бы одна чётная цифра?

 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.