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

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

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

Пример. Пусть требуется составить набор из ручки, карандаша и линейки. Имеется:

5 различных ручек,

7 различных карандашей,

10 различных линеек.

Сколькими способами можно составить требуемый  набор?

            Решение. Действием в данном случае является составление набора из ручки, карандаша и линейки; действие распадается на три этапа (части): выбрать ручку, выбрать линейку и выбрать карандаш. Первую часть действия – выбрать ручку – можно выполнить пятью способами, вторую часть действия – выбрать карандаш – можно выполнить семью способами, третью часть действия – выбрать линейку – можно выполнить десятью способами. Тогда все действие можно выполнить

Число способов. Т.е. возможно 350 вариантов такого набора.

            Пример. Сколько существует наборов длины  из нулей и единиц?

            Решение. Действием в данном случае является составление набора длины  из нулей и единиц.

Набор будет составлен, если все  позиций (мест) будут заполнены нулями и единицами. Действие распадается на  частей: заполнить первую позицию, вторую и т.д., заполнить -ю позицию. Первую часть действия – написать первую компоненту - можно двумя способами: можно написать 0, а можно написать 1, написать вторую компоненту тоже можно двумя способами, и так все  мест в наборе: на каждом месте можно написать либо 0 либо 1:

            Тогда все действие согласно комбинаторному принципу умножения можно выполнить  числом способов:

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

Пример.

Выборкой объема  из множества  называется всякая последовательность из  элементов множества .

Если элементы в выборке не повторяются, то выборка называется бесповторной, иначе – выборкой с повторениями

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

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

Рассмотрим бесповторную выборку

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

Например, на множестве из трех элементов  возможны следующие перестановки: .

Число различных перестановок без повторений из  элементов обозначается  и равно , т.е.

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

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

.

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

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

Теорема.

Число размещений без повторений из  элементов по   равно:

.

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

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

1)      

Доказательство.  Поскольку  и , то утверждаемое очевидно.

2)      (без доказательства).

Значения  могут быть найдены не расчетом по формуле количества сочетаний, а с помощью так называемого треугольника Паскаля. (Блез Паскаль (1623 – 1662) – французский математик).

            Этот треугольник имеет вид:

1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

Закономерность его построения такова: складывая две рядом стоящие числа, получаем число, стоящее ниже между ними. Первая строчка – значения числа сочетаний из 1 (), вторая – из 2 ( - слева направо), и т.д.

Рассмотрим выборку с повторениями

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

1.      Число различных перестановок на элементах такой выборки равно:

- число перестановок с  повторениями на множестве из  элементов

2.      Сочетание с повторениями из  элементов по   - неупорядоченная выборка  элементов с возвращением из множества, содержащего  элементов:

 - число различных сочетаний  с повторениями из   элементов по

3.      Размещения с повторениями из  элементов по  - расположение  различных шаров по  различным ячейкам

  - число различных размещений с повторениями

Пример. Сколько различных 4-буквенных слов можно составить из символов ?

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

Пример. Сколько различных перестановок можно составить из букв слова АБАКАН?

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

.

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

 элементов первого вида,

 элементов второго вида,

…

 элементов -го вида

равно:

Пример. Сколько перестановок можно получить из букв слова КОЛОКОЛА?

Решение. Требуется найти число перестановок с повторениями на множестве из 8 букв, среди которых:

буква К повторяется 2 раза;

буква О повторяется 3 раза;

буква Л повторяется 2 раза

буква А повторяется 1 раз.

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

Пример. Сколькими способами можно составить набор из 5 шоколадок, если имеются шоколадки трех сортов в количестве по 10 штук каждого вида?

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

Пример. Сколькими способами можно рассадить 7 человек по 9 вагонам?

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

Эту же задачу можно решить, применяя комбинаторный принцип умножения: действие – рассадить 7 человек распадается на 7 этапов: разместить первого пассажира, разместить второго пассажира, …, разместить седьмого пассажира. Первый этап – размещение первого пассажира можно выполнить 9 способами, второго пассажира тоже можно разместить  9 способами, и т.д. :

Пример. Сколькими способами можно рассадить 7 человек по 9 вагонам по одному в вагон?

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

Эту же задачу можно решить, применяя комбинаторный принцип умножения: действие – рассадить 7 человек распадается на 7 этапов: разместить первого пассажира, разместить второго пассажира, …, разместить седьмого пассажира. Первый этап – размещение первого пассажира можно выполнить 9 способами, второго пассажира тоже можно разместить  9 способами, и т.д. :

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

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

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

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

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

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

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

Пример. Номер автомобиля состоит из трех букв и трех цифр. Сколько различных номеров можно составить, используя 10 цифр и алфавит в 30 букв.

            Очевидно, что количество всех возможных комбинаций из 10 цифр по 4 равно 10.000.

            Число всех возможных комбинаций из 30 букв по две равно .

Если учесть возможность того, что буквы могут повторяться, то число повторяющихся комбинаций равно 30 (одна возможность повтора для каждой буквы). Итого, полное количество комбинаций по две буквы равно 900.

            Если к номеру добавляется еще одна буква из алфавита в 30 букв, то количество комбинаций увеличивается в 30 раз, т.е. достигает 27.000 комбинаций.

            Окончательно, т.к. каждой буквенной комбинации можно поставить в соответствие числовую комбинацию, то полное количество автомобильных номеров равно 270.000.000.

© Е.Г. Hикифорова

К следующему разделу
К оглавлению