Дипломная работа: Факультативный курс по теме "Элементы комбинаторики" для 8 класса

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

Если объект а можно выбрать m способами, а объект b – k способами (не такими, как а ), то выбор «либо а , либо b » можно осуществить m + k способами.

п(А+В)=п(А)+п(В)

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

Решение: по условию задачи яблоко можно выбрать пятью способами, апельсин – четырьмя. Так как в задаче речь идет о выборе «либо яблоко, либо апельсин», то его, согласно правилу суммы, можно осуществить 5+4=9 способами.

Правило произведения

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

Если объект а можно выбрать m способами, а объект b - k способами, то пару ( a , b ) можно выбрать m ∙ k способами.

п(А × В)=п(А) × п(В)

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

Задача: сколько трехзначных чисел можно составить, используя цифры 7, 4 и 5?

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

Правила суммы и произведения – это общие правила решения комбинаторных задач. Кроме них в комбинаторике пользуются формулами для подсчета числа отдельных видов комбинаций, которые встречаются наиболее часто. Рассмотрим некоторые из них и, прежде всего те, знание которых необходимо [24, 72].

Размещения

С теоретико-множественной точки зрения запись любого двузначного числа – это кортеж длины двух. Записывая различные двузначные числа с помощью цифр 7, 4 и 5, мы по сути дела образовывали из данных трех цифр различные кортежи длины двух с повторяющимися элементами. В комбинаторике такие кортежи называют размещениями с повторениями из трех элементов по два элемента.

Размещение с повторениями из k элементов по m элементов – это кортеж длины m , составленный из m элементов k - элементного множества.

=k^m

Из определения следует, что два размещения из k элементов по m элементов отличаются друг от друга либо составом элементов, либо порядком их расположения.

Например, два двузначных числа из перечисленных выше (а это размещения из трех элементов по два) отличаются друг от друга либо составом элементов (74 и 75), либо порядком их расположения (74 и 47).

Задача: сколько всевозможных двузначных чисел можно записать, используя цифры 7, 4 и 5?

Решение: пользуясь формулой =k^m , легко подсчитать, сколько двузначных чисел можно записать, используя цифры 7, 4 и 5. так как речь идет о размещениях с повторениями их трех элементов по два, то =3² =9.

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

Размещение без повторений из k элементов по m элементов – это кортеж длины m , составленный из неповторяющихся элементов множества, в котором k элементов.

,

m множителей

Задача: сколько всевозможных трехзначных чисел можно записать, используя цифры 7, 4 и 5, так, чтобы цифры в записи числа не повторялись?

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

=3(3-1)∙(3-2)=3∙2∙1=6.

Эти числа таковы: 745, 754, 475, 457, 547, 574.