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

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}.

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

Каждому элементу множества В ⁿ поставим в соответствие единст­венный элемент множества В - {0; 1}. Полученное соответствие наз

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать