Презентация, доклад по математике на тему Элементы комбинаторики

с повторениями.
3. Упорядоченные множества. Размещения и перестановки без повторений.
4. Сочетания без повторений и их свойства. Треугольник Паскаля.

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

содержит m элементов (n(В)=m). Тогда, если АВ=, то
n(АВ)=n(A)+n(B). (1)
это утверждение в комбинаторике называют правилом суммы. Его формулируют следующим образом:
Если элемент a можно выбрать k способами, а элемент b - m способами, причем любой способ выбора a отличается от любого способа выбора b, то выбор «a или b» можно сделать k+m способами.

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

плод можно выбрать 8+6 =14 способами.

2) Имеются две урны, в первой содержится 7 белых шаров, а во второй - 4 черных шара. Сколько вариантов выбора одного шара, независимо от цвета (11=7+4).

Например, объединение множеств А ={а,b,c,d,e}, В={d,e,f,g}
состоит лишь из семи элементов АВ={а,b,c,d,e,f,g},
а не 5+4=9 элементов.
Это объясняется тем, что элементы d и e принадлежат А и В,
а в объединение эти элементы входят один раз.
Поэтому из суммы 5+4 приходится вычесть 2,
то есть число элементов пересечения А и В.
Для любых двух конечных множеств А и В имеет место равенство:

n(АÈВ)=n(А)+n(В)-n(АÇВ) (2)

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

При этом 27 учеников увлекаются обоими видами спорта. Сколько учеников увлекаются хотя бы одним видом спорта?

В – множество «волейболистов», n(В)=40
n(АВ)=27 множество студентов увлекающихся обоими видами спорта.
Тогда имеем: n(А)-n(АВ)=50-27=23 - увлекаются только футболом
n(В)-n(АВ)=40-27=13 - увлекаются только волейболом,
Следовательно, 13+23+27=63 - увлекаются хотя бы одним видом спорта, или, используя формулу (2), имеем:
n(АВ)=n(А)+n(В)-n(АВ)=50+40-27=63

А В

А={х1,х2,…,хm} и Y={y1,y2,…,уk}
Запишем все пары в виде следующей таблицы
(х1; у1), (х1; у2),…,(х1; уk)
(х2; у1), (х2; у2),…,(х2; уk)
………………………….
(хm; у1), (хm; у2),…,(хm; уk)
Видно, что таблица состоит из m строк, в каждой из которых содержится k элементов. Значит общее число пар mk
Итак, число упорядоченных пар, которые можно составить из элементов m множества А и k множества В, равно mk, то есть
n(АВ)=n(А)n(В) (3)

Указанное равенство позволяет сформулировать правило произведения:
Если элемент а можно выбрать m способами, а b - k способами, то пару (a;b) можно выбрать mk способами.

в С 2 дороги. Сколькими способами можно пройти из А в С?

С

В

А

В в С – буквами а и в.
Тогда каждый вариант пути из А в С задается парой, состоящей из числа и буквы.

Рассматривая различные варианты, получаем, что пар 32=6
[(1;а), (1;в),(2;а),(2;в),(3;а),(3;в)]

длины k, составленных из элементов m - множества Х.
Чтобы решить задачу, надо найти число кортежей в декартовом произведении ХХ…Х, содержащих k множителей. По правилу произведения число элементов в декартовом произведении ХХ…Х равно k
n(X) n(X)… n(X).

k
Причем n(X)=m. Тогда n(ХХ…Х)=mm…m=mk
 
k

 Итак, число кортежей длины k, составленных из элементов m - множества Х, равно mk.

Опр. Кортежи длины k, составленные из элементов m - множества, называют размещениями с повторениями из m элементов по k, а их число таких кортежей обозначают
 
(4)

Сколько 4-х-значных чисел можно составить из цифр 1,2,3,4,5,6?
Решение:

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

(5)

Например: Сколько всевозможных четырехзначных чисел можно составить из цифр 1,3,5,7.

Решение: