Элементы комбинаторики. Правила умножения и сложения (стр. 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 |
, - отрицание