Методические рекомендации для проведения курса «Комбинаторика» (стр. 3 )

Решение: На первом шагу можно выбрать геометрическую фигуру. Этот выбор можно осуществить 4 способами. Потом надо выбрать одну из 32  букв и затем одну из 10 цифр. Всего получается 4 * 32 * 10 = 1280 комбинаций.

Пример 3: «Задача о домино»

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

Сколькими способами из 28 костей  домино можно выбрать 2 кости так, чтобы их можно было приложить друг к другу (т. е. чтобы какое – то число очков встречалось на обеих костях)?

Решение: Сначала выберем одну кость. Это можно сделать 28 способами. При этом в 7 случаях выбранная кость окажется «дублем» (00, 11,22, 33, 44, 55, 66), а в 21  случаем – костью с различными числами очков. В первом случае вторую кость можно выбрать 6 способами (например, если на первом шагу выбрана кость 11, то на втором шагу можно взять одну из костей 01, 12, 13, 14, 15, 16). Во втором же случае вторую кость можно выбрать 12 способами (для кости 35 – 03, 13, 23, 33, 34, 36, 05, 15, 25, 45, 55, 56). По правилу произведения в первом случае получаем 7*6=42 выбора, а во втором 21*12=252 выбора. Значит, по правилу суммы получаем 42+252=294 способа выбора пары.

Вывод: В решении задачи учитывался порядок, в котором выбирались кости. Поэтому каждая пара костей появлялась дважды (например, первый раз 01 и 16, второй 16 и 01). Если не учитывать порядок выбора костей, то получим вдвое меньше способов выбора, т. е. 147 способов.

§3. Основные формулы комбинаторики.

С помощью общих правил комбинаторики, можно решать задачи самых разных типов. Однако как в геометрии неудобно всегда сводить решение задачи к аксиомам, а удобно пользоваться теоремами, так и в комбинаторике вместо решения задачи по общим правилам часто удобнее пользоваться готовыми формулами, потому что некоторые типы задач встречаются значительно чаще других. Комбинациям, которые встречаются в этих задачах, присвоены особые названия – размещения, перестановки и сочетания.

3.1 Размещения

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

Рассмотрим задачу «Футбольное первенство»:

В первой группе «А» первенства России по футболу участвуют 17 команд. Разыгрываются медали: золотые, серебренные и бронзовые. Сколькими способами они могут быть распределены?

Решение: Данную задачу можно решить по правилу произведения, так как золотые медали может получить любая из 17 команд (17 возможностей).  Но если золотые медали уже получены какой-то командой, то остается 16 претендентов на серебреные  медали (16 возможностей). Если уже вручены золотые и серебреные медали, то бронзовые медали может получить одна из оставшихся 15 команд (15 возможностей). Значит, по правилу произведения получаем, что медали могут быть распределены 17*16*15=4080 способами.

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

Имеется n различных предметов. Сколько из них можно составить k-расстановок? При этом две перестановки считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке. Такие расстановки называют размещением без повторений, а их число обозначают:

При составлении k-размещений без повторений из n предметов нам надо сделать k выборов. На первом шагу можно выбрать любой из имеющихся n предметов. На втором шагу приходиться выбирать из оставшихся (n-1) предметов (повторять сделанный выбор нельзя). На третьем шагу, для выбора остается (n-2) свободных предметов, …, на k-м шагу – (n-k+1) предметов. Поэтому по правилу произведения получаем, что число k - размещений без повторения из n предметов выражается формулой:

  (1)

Следовательно, задачу о футбольном первенстве можно решить по формуле (1): способами.

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

Рассмотрим размещение с повторениями. Общий вид задач:

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

Расстановки данного типа называются k - размещениями с повторениями из элементов n видов, а число всех таких расстановок обозначается .

Если число видов равно n, а в каждое размешение входит k элементов, то можно составить n  размещений с повторениями,  можно записать формулу k - размещений с повторениями из элементов n видов:

  (2)

Доказать формулу можно с помощью математической индукции по k - числу

  элементов в размещении при фиксированном значении n.

Рассмотрим задачу «Секретный замок»

Для запирания сейфов и автоматических камер хранения применяют секретные замки, которые открываются лишь тогда, когда набрано некоторое «тайное слово». Это слово набирают с помощью одного или нескольких дисков, на которых нанесены буквы (или цифры). Пусть на диск нанесены 12 букв, а секретное слово состоит из 5 букв. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова?

Решение: По формуле (2) общее число комбинаций равно 

Значит, неудачных попыток может быть 248831. Обычно сейфы делают так, что после первой же неудачной попытки открыть их раздается сигнал тревоги.

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

а) Перестановки без повторений.

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

Но если брать расстановки, в которые входят все n элементов, то они могут отличаться друг от друга лишь порядком входящих в них элементов. Такие расстановки называются перестановками из n элементов, или n-перестановками. Число n-перестановок обозначается .

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

  (3)

Чтобы узнать, сколько перестановок можно составить из n элементов, надо перемножить все натуральные числа от 1 до n. Это произведение называется «n-факториал» и обозначается n!. Следовательно,

  (4)

(1! =1, 0! =1 из свойств факториала). Значит формулу (1) для числа размещений, можно записать через факториал:

  (5)

Т. к.

Рассмотрим  «Задачу о ладьях».

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

Решение: При таком расположении ладей на каждой горизонтали и каждой вертикали стоит по одной ладье. Возьмем одно из этих расположений и обозначим через а1 номер занятого поля на первой горизонтали, через а2 – на второй, …, через а8 – на восьмой горизонтали. Тогда (а1, а2, …, а8) является некоторой перестановкой чисел 1, 2, …, 8. Значит, число искомых расположений ладей равно числу перестановок чисел 1, 2, …,8, т. е.

= 8! =1*2*3*4*5*6*7*8 = 40 320.

Следовательно, ладьи можно расположить требуемым образом 40320 способами.

б) Перестановки с повторениями.

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

Общая задача формулируется следующим образом:

Имеются предметы k различных типов. Сколько перестановок можно сделать из n1 элементов первого типа, n2 элементов второго типа,… , nk элементов k-го типа?

Число элементов в каждой перестановке равно  n = n1 + n2 +…+ nk. Поэтому если бы все элементы были различны, то число перестановок равнялось бы n!. Но из-за того, что некоторые элементы совпадают, получится меньшее число перестановок. Элементы первого типа можно переставлять друг с другом n1! способами. Но так как все эти элементы одинаковы, то такие перестановки ничего не меняют. Точно так же ничего не меняет n2! перестановок элементов второго типа, …, nk! перестановок элементов k-го типа.

Перестановки элементов первого типа, второго типа и т. д. можно делать независимо друг от друга. Поэтому элементы перестановки можно переставлять друг с другом n1! n2!… nk! способами, так что бы перестановка осталась неизменной. Следовательно, множество всех n! перестановок распадается на части, состоящие из n1 n2! … nk! одинаковых перестановок каждая. Значит, число различных перестановок с повторениями, которые можно сделать из данных элементов, равно:

  (6)

где n=n1+n2+…+nk.

Задача: Сколько перестановок можно сделать из букв слова “мама”?