В знаменитой басне И.Крылова "музыканты" менялись местами, чтобы улучшить качество исполнения музыки. Сколько по вашему существует способов рассадить участников квартета в один ряд? Другой пример. Вам предлагают сыграть в лотерею. Нужно отгадать 6 номеров из 49. Сколько существует возможных вариантов таких билетов? Этими вопросами и занимается комбинаторика. Особая примета комбинаторных задач - вопрос, который можно сформулировать так, чтобы он начинался словами: "Сколькими способами..."
Пусть имеется n объектов. Расставим их в ряд и назовем это расположение объектов перестановкой. Вопрос: "Сколько всего возможно перестановок из n объектов?
Начнем с простого. Попробуем определить число перестановок для одного предмета. Понятно, что если имеется один предмет, то существует и один способ перестановки. Отсюда выводим первую формулу
Р1=1, где
Р-расстановка, 1-число объектов.
Берем два предмета. Тоже понятно, что существует два варианта
Р2=2, т.е. два предмета (А и Б) можно расставить как АБ и БА
Теперь будем рассуждать следующим образом. Предмет А установим неподвижно. Второй предмет будем пристраивать к нему. В нашем примере объект Б можно пристроить либо спереди, либо сзади. Следовательно, число перестановок Р2 вдвое больше, чем Р1, т.е.
Р2=Р1*2=1*2
Добавляем новый объект В. В каждой перестановке из двух объектов А и Б можно пристроить третий элемент тремя способами:
поставить спереди, сзади или посередине
| АБ | БА |
| ВАБ АВБ АБВ | ВБА БВА БАВ |
Все получившиеся шесть перестановок разные. Отсюда
Р3=Р2*3=1*2*3
Продолжаю в том же духе, вы скоро заметите, что из каждой перестановки n-1 предметов можно получить n дополнительных перестановок, добавляя n-ый предмет либо спереди, либо сзади, либо между имеющимися предметами. Общая формула будет такой:
Рn=1*2*3*...*n=n!
Запись n! читают как n-факториал, что означает произведение всех натуральных чисел от 1 до n включительно.
Вернемся к нашим музыкантам. Зная формулу, мы без труда вычислим число всех возможных перестановок:
Р4=4!=1*2*3*4=24
На языке Visual Basic формула вычисления числа перестановок может выглядеть так:
Dim N, fact As Double Dim i As Integer N = Text1.Text ' берем число из текстого поля fact = 1 For i = 1 To N fact = fact * i Next i Print fact
Рассмотрим другой случай. Предположим, что музыканты сели не в ряд, а по кругу. Сколько получится перестановок? Порассуждаем. Принумеруем всех участников по часовой стрелке, начиная с мартышки. Пусть у нее будет постоянный номер, тогда как другие будут меняться, образуя новые сочетания. Значит, принумеровать различными способами мы можем только оставшихся троих участников
1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2