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

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

Рассмотрим примеры.

Пример 1. Трудовой коллектив из 30 человек должен выбрать руководителя и его заместителя. Сколько существует способов их выбора, если каждый член коллектива может быть либо руководителем, либо его заместителем?

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

  • 29 человек может быть выбран заместителем. Значит, любой из
  • 30 способов выбора руководителя может осуществляться с 29 способами выбора его заместителя. Поэтому существует 30 29 =

= 870 способов выбора руководителя и заместителя.

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

Обозначим преподавателей буквами А, В, С, D, Fи выпишем возможные варианты состава комиссии:

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

Будем ставить старшего преподавателя на первое место. Тогда сформируются следующие множества:

Пусть имеется множество, состоящее из п элементов.

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

В примере 3 каждая пара элементов является размещением из пяти элементов по два.

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

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

Для т элементов будет п(п - )(п - 2) ... (п - т + 1) способов формирования т элементов. Таким образом, общее число размещений из п элементов по т определится по формуле

Умножим и разделим выражение (1.1) на (п- т), где (п- т) =

= 1-2-3 ... (п — т). Тогда получим

Формула (1.2) определяет число размещений из п элементов по т.

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

На основании формулы (1.1) при т = п получается число перестановок из п элементов:

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

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

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

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

откуда

Подсчитаем, например, С30:

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

Если в размещениях из п элементов по два первый элемент может быть выбран п способами, то и второй элемент тоже может выбираться п способами, так как на втором месте может оказаться любой элемент. Поэтому число размещений из п элементов по два будет А„ = п2. Если взять комбинации, состоящие из трех элементов, и предположить, что все элементы могут повторяться, то получается формула Д3 = г? и т.д.

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

Если теперь рассмотреть сочетания из п элементов по т и предположить, что в комбинации возможны повторения, т.е. выбор элементов комбинации осуществляется не только по одному разу из п элементов, но и еще до - 1) раза одного из этих элементов, то общее число элементов, из которых осуществляется комбинация, следует увеличить до (п + т - 1) элементов.

ю

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

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

Аналогично происходит и с остальными элементами, которые могут встречаться п2, п3,..., пк раз (л, + п2 + ... + пк = п). Поэтому общее число перестановок с повторениями подсчитывается по формуле

Пример 5. Существует набор, состоящий из 10 наименований элементов для рекламного стенда магазина. На стенде имеется 6 мест, на которых выбранные элементы устанавливаются в определенном занумерованном порядке. При этом элемент одного и того же наименования может претендовать на любое место. Сколько существует комбинаций такого стенда?

В данном случае имеют место размещения из 10 наименований по 6 элементов в комбинации с повторениями. Число этих размещений будет равно

Пример 6. Производится набор комбинаций из 10 наименований цветов по 5 штук в букете. Сколько существует комбинаций таких букетов?

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

Пример 7. Имеется шестизначная кодовая комбинация, состоящая из трех цифр 1, 3, 5, в которой цифра 1 встречается один раз, цифра 3 — два раза и цифра 5 — три раза. Сколько существует комбинаций таких наборов?

В данном случае имеют место перестановки с повторениями. Их число будет равно

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >