Реферат: Элементы комбинаторики. Правила умножения и сложения

Где

Сочетаниями из n-элементов по m элементов в каждом называются такие комбинации, каждая из которых состоит из mэлементов, выбранных из данных n элементов, и которые отличаются друг от друга хотя бы одним элементом.

Пример: Сколькими способами можно выбрать 3 представителей учебной группы в студ совет, если в группе 25чел.

Сочетаниями из n-элементов по m с повторениями назыв такие комбинации, каждая из которых состоит из mэлементов из данных n элементов, причем один и тот же элемент может входить в комбинацию более одного раза.

Обозначается – Č и вычисл по форм:

3. Бином Ньютона.

Бином Ньютона – это формула, представляющая выражение в виде многочлена.

Она имеет вид:

Её можно записать иначе:

, где - число сочетаний из nэлементов по k,

Известные формулы сокращенного умножения: квадрат суммы, квадрат разности, куб суммы, куб разности являются частными случаями бинома Ньютона.

Когда степень бинома невелика, коэффициенты многочлена могут быть получены с помощью треугольника Паскаля.

Любой элемент треугольника паскаля, распол в n-ой строке на k-ом месте выражает ,

Где отчет nведется от 1, а отчет k ведется от 0.

Пример : Представить в виде многочлена

Решение:

4. Булевы функции. Определение. Примеры.

Алгебра логики, выстроенная в XIX веке, долго существовала как абстрактная, хотя и очень красивая наука. Но в середине XX века оказалось, что она имеет конкретное и очень важное применение в современной жизни. Булева алгебра в настоящее время служит основой для описания логики работы аппаратных и программных средств ЭВМ. Она ис­пользует логические переменные, которые принимают лишь два значения 0 и 1. Аналогично и ЭВМ использует лишь сигналы 0 и 1, воспринимая их как логические переменные.

Рассмотрим множество В = {0;1}.

Тогда В² = {(0;0),(0;1),(1;0),(1;1). Снимем разделительный к внутри каждой пары и уберём скобки. Тогда В² = {00, 01,10,11}. Аналогично В³ = Вх В² ={000,001,010,011,100,101,110,111} и т. д.,

Каждому элементу множества В ⁿ поставим в соответствие единст­венный элемент множества В - {0; 1}. Полученное соответствие наз булевой функцией . Элементы множества В ⁿ являются значениями аргумента булевой функции. Они представляют собой наборы, состоящие из нулей и единиц, и называются кортежами. Длиной кортежа назы­вается число цифр, образующих кортеж. Множество В ⁿ - область определения функции

Множества значений булевой функции, вообще говоря это значение функции В = {0;1}.

Задание булевой функции в виде таблицы, в которой указаны значения каждой переменной кортежа и значение самой функции, называется заданием таблицей истинности или матричным заданием булевой функции.

Геометрическая интерпретация отражает геометрический способ задания булевых функций.