Смекни!
smekni.com

Элементы комбинаторики. Правила умножения и сложения (стр. 1 из 5)

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

Комбинаторика – раздел математики, в котором изучаются задачи выбора элементов из заданного множества и расположения их в группы по заданным правилам, в частности задачи о подсчете числа комбинаций (выборок), получаемых их элементов заданного множества. В каждой из них требуется подсчитать число возможных вариантов осуществления некоторого действия, ответить на вопрос: «Сколькими способами?» Многие комбинаторные задачи могут быть решены с помощью следующих 2х важных правил, называемых соответственно правилами умножения и сложения.

Правило умножения.

Если из нек множ первый объект (элемент х) можно выбрать n1 способами и после каждого такого выбора второй объект (элем у) можно выбр n2 способами, то оба объекта (х и у) в указ порядке можно выбрать n1*n2 способами.

Это правило распр-ся на случай трех и более объектов.

Пример: сколько трехзначных чисел можно составить из цифр 1,2,3,4,5, если: а) числа не повт; б) числа могут повтор.

Решение: а) 1ую цифру выбираем 5мя способами, 2ую – 4мя, 3 – 3мя 5*4*3=60 способов

б) 5*5*5=125 сособов

Правило сложения

Если некот объект х можно выбр n1 способами, а объект у можно выбр n2 способами, причем первые и вторые выборы таковы, что они взаимно искл друг друга и не могут быть получены одновременно, то объект хUу (х или у) можно выбр n1+n2 способами.

Пример: Четыре города M,N,P,K соединены дорогами так, что из Mв Nведут 5дорог, из N в K– 6 дорог, из M в P ведут 4 дороги, из P в К – 3 дороги.

Сколькими способами можно проехать из М в К?

Решение: Из М в К через N ведут 5*6=30 дорог, Из М в К через P ведут 4*3=12 дорог

Из М в К ведут 30+12=42 дороги.

2. Размещения, перестановки, сочетания.

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

Если элементы комбинации не повторяются.

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

Размещения с повторениями обозначаются Ã и вычисляются по формуле:

Примеры в 1ом вопросе!

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

Пример: Имеется 5 равных геом фигур: 3 желтых и 2 белых круга. Сколько различных узоров можно составить из этих кругов, располагая их в ряд?

Решение: Желтые круги будут повт 2! раз

Белые - 3! раз

Число разл узоров будет равно 5!/2!*3!=10

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

Где

Сочетаниями из 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}.

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

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

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

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

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

Область определения D(f) булевой функции n = 1 это совокупность двух точек 0 и 1 числовой прямой, т.е. одномерного куба

Если п = 2, то D(f) = {00,01,10,11}- это множество вершин квадрата, т. е. двухмерного куба

Если п = 3, то D(f) = {000,001,010,01 1,100,101,110,111}

множество вершин трёхмерного куба в декартовой системе координат.

На кортежах длины n можно составить

различных простейших булевых функций.

Если n=1, то число простейших булевых функций равно 4, если n=2, то их 16, если n=3, то их 256

Если n=1, то существует 4 простейших булевых функций:

- константа 0(тождественный 0)

- константа 1(тождественная 1)

- тождественная функция

- отрицание

5. Реализация булевых функций формулами.

0 0 1 1 0 0 1 0
0 1 1 0 0 1 1 0
1 0 0 1 0 1 0 1
1 1 0 0 1 1 1 0
0 0 1 0 1 0 0 1
0 1 0 1 0 1 0 1
1 0 1 0 0 1 0 1
1 1 1 0 1 0 0 1

,
- отрицание