Скачиваний:
91
Добавлен:
15.06.2014
Размер:
193.02 Кб
Скачать

2 Основные понятия комбинаторики

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

2.1 Основные виды комбинаторных конфигураций

Пусть имеется множество из n элементов, из которого извлекается k элементов (выборка из n по k). Если условия выбора каждого элемента одинаковы (т.е. и первый, и второй, …, и k-й элементы выбираются из n элементов), то говорят, что имеет место выборка с повторениями. Другими словами, при выборке с повторениями каждый выбранный элемент возвращается обратно во множество и может быть выбран снова.

Простейший пример выборки с повторениями – числа (например, десятичные): они составляются из n=10 элементов (цифр), причем цифры в числе могут повторяться.

При выборке без повторений выбранный элемент не возвращается в исходное множество и не может быть выбран снова. Таким образом, при выборке без повторений первый элемент выбирается из n элементов, второй – из n-1, третий – из n-2, …, k-й – из (n-k+1) элемента.

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

Основные формулы для подсчета количества комбинаторных конфигураций (выборок из n по k):

  • размещения с повторениями: ;

  • размещения без повторений: ;

  • сочетания с повторениями: ;

  • сочетания без повторений: ;

Если рассматриваются различные варианты размещения всех n элементов некоторого множества, то такие размещения называются перестановками. Основные формулы для подсчета количества перестановок следующие:

  • если все элементы множества различны: ;

  • если среди n элементов имеется m1 одинаковых элементов первого типа, m2 одинаковых элементов второго типа, …, mr одинаковых элементов r-го типа, m1+m2+…+mr = n: .

Кроме того, для подсчета количества комбинаторных конфигураций применяются следующие правила:

  • правило суммы: если некоторый элемент можно выбрать m способами, а некоторый другой элемент – n способами, то один из них можно выбрать m+n способами;

  • правило произведения: если некоторый элемент можно выбрать m способами, а после этого некоторый элемент можно выбрать n способами, то комбинацию этих двух элементов можно выбрать mn способами.

Пример 2.1 – Дано множество A = {a, b, c}. Приведем примеры подсчета количества различных комбинаторных конфигураций, которые можно получить из него, а также примеры самих этих конфигураций.

Перестановки: P3 = 3! = 6. Эти перестановки следующие: abc, acb, bac, bca, cab, cba.

Размещения с повторениями из 3 по 2: (aa, bb, cc, ab, ba, ac, ca, bc, cb).

Размещения без повторений: = 6 (ab, ba, ac, ca, bc, cb).

Сочетания с повторениями: (aa, bb, cc, ab, ac, bc).

Примечание – Так как в данном случае рассматриваются сочетания (а не размещения), конфигурация ab эквивалентна ba, ac эквивалентно ca, bc эквивалентно cb.

Сочетания без повторений: (ab, ac, bc).

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

Пример 2.2 – Используя правила комбинаторики, найти, сколько двузначных чисел можно составить из цифр 0, 1, 2, …, 9.

Первую цифру можно выбрать девятью способами (так как можно выбрать любую цифру, кроме нуля). Вторую – десятью способами (на втором месте в двузначном числе может располагаться любая цифра). Таким образом, по правилу произведения, имеется 910 = 90 комбинаций.

Пример 2.3 – Найти, сколько четырехзначных чисел можно составить из цифр 0, 1, 2, …, 9.

Эту задачу можно решить аналогично предыдущей: первую цифру можно выбрать девятью способами, каждую последующую – десятью, поэтому всего имеется 9101010 = 9000 комбинаций.

Рассмотрим другой способ решения этой задачи. Первую цифру можно выбрать девятью способами. Выбор трех других цифр – это размещение с повторениями из 10 по 3. Это размещение, так как числа из одинаковых цифр, расположенных в разном порядке – это разные числа (например, 315 и 531). Это размещение с повторениями, так как цифры, составляющие число, могут повторяться (например, 515). Это размещение из 10 по 3, так как выбираются три цифры из десяти (хотя выбранные цифры могут и совпадать). Количество размещений с повторениями определяется по формуле: . Таким образом, комбинацию из трех цифр (т.е. вторую, третью и четвертую цифры для четырехзначного числа) можно выбрать 1000 способами. Первую цифру, как отмечено выше, можно выбрать девятью способами. Таким образом, всего имеется 91000 = 9000 комбинаций.

Пример 2.4 – Найти, сколько четырехзначных чисел можно составить из цифр 0, 1, 2, …, 9, причем в числе не должно быть одинаковых цифр.

Первую цифру можно выбрать девятью способами. Выбор трех других цифр – это размещение без повторений из 10 по 3. Количество таких размещений определяется по формуле: = 8910 = 720. Таким образом, всего можно составить 9720 = 6480 чисел.

Пример 2.5 – Найти, сколько четырехзначных чисел можно составить, используя цифры 6, 7, 8, 9 ровно по одному разу.

Такая комбинация цифр представляет собой перестановку из четырех элементов (цифр). Их количество определяется как P4 = 4! = 24.

Пример 2.6 – Найти, сколько четырехзначных чисел можно составить, используя цифру 7 ровно два раза, а цифры 6 и 8 – ровно по одному разу.

Такая комбинация цифр представляет собой перестановку из четырех элементов (цифр), среди которых имеется один элемент первого типа (цифра 6), два – второго типа (цифра 7), один – третьего типа (цифра 8). Количество таких перестановок определяется по формуле: . Перечислим эти перестановки (т.е. возможные четырехзначные цифры): 6778, 6787, 6877, 7678, 7687, 7867, 7876, 7768, 7786, 8776, 8767, 8677.

Пример 2.7 – На предприятии работают 5 человек с высшим образованием и 20 – со средним. Найти, сколькими способами можно составить группу из 6 человек, из которых 2 человека должны иметь высшее образование, остальные 4 - среднее.

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

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

По правилу произведения определяем, что общее количество вариантов формирования группы равно 104845 = 48450.

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

Рассмотрим случай, когда в группу включается только один человек с высшим образованием. Его можно выбрать пятью способами (одного из пяти имеющихся на предприятии). Остальные 5 человек со средним образованием могут быть выбраны 15504 способами. Таким образом, всего имеется 515504 = 77520 вариантов выбора.

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

В данном случае требуется составить группу, в которую будет включен или один, или два человека с высшим образованием (и, соответственно, пять или четыре – со средним). Поэтому общее количество вариантов выбора такой группы определяется по правилу суммы: 77520 + 48450 = 125970 вариантов.

Пример 2.9 – На предприятии имеются пять вакансий. На работу могут приниматься лица как с высшим, так и со средним специальным образованием. Найти, сколько имеется вариантов заполнения вакансий.

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

В данном случае имеет место сочетание с повторениями из 2 по 5. Это сочетание, так как в данном случае представляет интерес только состав принятых на работу (т.е. количество имеющих высшее и среднее специальное образование), но не порядок их приема. Это сочетание с повторениями, так как среди принятых на работу будет несколько человек с одинаковым образованием. Это сочетание из 2 по 5, так как группа из пяти человек составляется из людей, имеющих один из двух видов образования (высшее или среднее специальное). Количество таких сочетаний определяется следующим образом: =6. Таким образом, имеется шесть вариантов заполнения вакансий. Перечислим эти варианты (буквой В обозначен случай, когда принятый на работу имеет высшее образование, С – среднее специальное): ВВВВВ, ВВВВС, ВВВСС, ВВССС, ВСССС, ССССС.

Примечание – Следует еще раз обратить внимание, что здесь важен только состав принятых на работу, но не порядок их приема. Поэтому, например, вариант ВВВСС (принято на работу три человека с высшим образованием и два – со средним специальным) можно записать и как ВВССВ, СВСВВ и т.д.

Соседние файлы в папке Часть лекций Батин Н В (Мет пособие)