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

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

Комбинаторные методы применяются в

теории кодирования, планировании эксперимента, топологии, математической логике, теории игр, кристаллографии, биологии, статистической физике, экономике и т.д. Комбинаторика является основой для изучения теории вероятностей и математической статистики.

жизни привилегированных слоев общества большое место занимали азартные игры (карты,

кости). Были широко распространены лотереи. Возникали вопросы: сколькими способами можно выбросить данное число очков, бросая две или три кости, или сколькими способами можно получить двух королей? Эти и другие проблемы оказались движущей силой в развитии комбинаторики.
Теоретические исследования вопросов комбинаторики предприняли Паскаль и Ферма, Бернулли, Лейбниц и Эйлер и др.

организовал Берлинскую академию наук и стал её первым президентом.

В

1666 году вводит термин "комбинаторика" в   своей диссертации об искусстве комбинаторики, в которой решает основные комбинаторные задачи.

1.07.1646 - 14.11.1716

n способами, а объект В – m способами, то выбор

«или А, или В» может быть осуществлен n+m способами.

Задача. На тарелке лежат 5 яблок и 4 апельсина. Сколькими способами можно выбрать один плод?
Решение: 5 + 4 = 9

конфет и 4 пачки печенья. Сколькими способами можно составить набор,

состоящий из коробки конфет и пачки печенья?
Решение: 5  4 = 20

n способами и после каждого из таких выборов объект В

– m способами, то выбор «А и В» в указанном порядке может быть осуществлен n  m способами.

блюд, выставленных на столе у П.П. Петуха, если бы на каждый

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

решили использовать флаг в виде горизонтальных полос одинаковых по ширине,

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

Чем данная задача отличается от предыдущей?

чисел называют факториалом и обозначают через n!
n! = 123…(n2)(n1)n
0! =

1
1! = 1
2! = 12 = 2
3! = 123 = 6
4! = 1234 = 24 и т.д.

Овчинникова Р.П.Элементы дискретной математики

множества по k (0 kn) элементов называется k-элементное подмножество, в

котором важен порядок расположения элементов.
Пример. {1,2,3,4,5} – n=5 элементов
Размещения по k=1: 1, 2, 3, 4, 5
Размещения по k=2: 12, 13, 14, 15, 21, 23, 24, 25, 31, 32, 34, 35, 41, 42, 43, 45, 51, 52, 53, 54
Размещения по k=3: 123, 124, 125, 132, 134, 135, 142, 143, 145, 152, 153, 154, …512, 513, 514, 521, 523, 524, 531, 532, 534, 541, 542, 543
Размещения по k=4: 1234, 1235, 1243, 1245, 1324, 1325, …

элементов из некоторого множества.

Пример. {1,2,3,4,5} – n=5 элементов
Перестановки: 12345,

12354, 12435, 12453, 12534, 12543, 13245, 13254, 13425, 13452, 13524, 13542, …

множества по k (0 kn) элементов называется k-элементное подмножество, в

котором не важен порядок расположения элементов.
Пример. {1,2,3,4,5} – n=5 элементов
Сочетания по k=1: {1}, {2}, {3}, {4}, {5}
Сочетания по k=2: {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5}
Сочетания по k=3: {1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {3,4,5}
Сочетания по k=4: {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}

6 стульев. Было решено каждый вечер перед ужином рассаживаться на

эти 6 стульев по-новому. Сколько дней члены семьи смогут делать это без повторений?

№1

№2

№3

№4

№5

№6

6

5

4

3

2

1

6•5•4•3•2•1=

720дн.

-почти 2 года

наборов из двух предметов?

С помощью перечисления: ab, ac, ad, af,

bc, bd, bf, cd, cf, df — 10 наборов. По формуле: порядок предметов здесь не важен и элементы повторятся не могут, поэтому число различных наборов равно

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

выполнения лабораторной работы, состоящей из 3 хорошистов, 1 отличника и 1 троечника.

Задача: Имеется 4 чашки, 5 блюдец, 6 ложек (все чашки, блюдца, ложки различны). Сколькими способами можно накрыть стол к чаю на 3 человека, если каждый получает 1 чашку, 1 блюдце и 1 ложку.