Сколькими способами можно выбрать трех дежурных из группы в 20 человек: Сколькими способами можно выбрать трёх дежурных из группы в 20 человек?

Построение полного потока в транспортной сети. Нахождение корней уравнения

Министерство образования Российской Федерации Международный институт «ИНФО-Рутения»

РГГРУ

Контрольная работа

Дискретная математика

Минина Н.В.

г. Старая Русса

Контрольное задание №1

Задача №1. Дано одношаговое рекуррентное соотношение с начальным условием . Найти 7-й член последовательности

Решение. Чтобы найти 7-й член последовательности по рекуррентному соотношению, нужно найти все предыдущие. Нулевой член последовательности задан. Чтобы найти первый элемент, поставим в правую часть рекуррентного соотношения. Такая подстановка соответствует присваиванию и можно найти и т.д. Следовательно:. Поставив , получим . .

.

.

.

.

.

Ответ: .

Задача №2. Вычислить

Решение.

.

Задача №3. Решить уравнение

истинность логический карта карно

Решение.

.

После сокращения получаем . Найдем корни полученного уравнения: .

Ответ: .

Задача №4. Сколькими способами можно выбрать трех дежурных из группы в 20 человек

Решение. Поскольку порядок в выборке из трех дежурных является не существенным, такая выборка будет неупорядоченной. Поэтому, количество способов, которыми можно выбрать трех дежурных из группы в 20 человек определится сочетанием из 20 человек по 3 дежурным. В результате получим .

Ответ: 1140 способов.

Задача №5. Даны 2 множества: . Найти их

)Объединение .Ответ: ;)Пересечение .Ответ: ;)Разность .Ответ :;)Симметричную разность .Ответ: .

Контрольное задание №2

Задача №1. Построить полный поток в транспортной сети G, приведенной на рисунке (цифрами даны пропускные способности дуг)

Решение. Начинаем с нулевого потока, пологая .

При нулевом потоке отсутствуют насыщенные дуги. Выделим в G простую цепь и увеличим потоки по дугам на 3 до насыщения дуги (). В результате получим поток , содержащий одну насыщенную дугу.

. Пометим ее крестиком и удалим из орграфа, который снова обозначим .

Выделим в простую цепь и увеличим потоки по дугам этой цепи на 3 до насыщения дуги (). В результате получим поток , величина которого равна и который содержит насыщенную дугу . Удалим эту насыщенную дугу из и оставшийся орграф обозначим .

Выделим в простую цепь и увеличим потоки по дугам этой цепи на 2 до насыщения дуги (). В результате получим поток , величина которого равна и который содержит насыщенную дугу . Удалим эту насыщенную дугу из и оставшийся орграф обозначим .

Выделим в простую цепь и увеличим потоки по дугам этой цепи на 3 до насыщения дуги (). В результате получим поток , величина которого равна и который содержит насыщенную дугу . Удалим эту насыщенную дугу из и оставшийся орграф обозначим .

Выделим в простую цепь и увеличим потоки по дугам этой цепи на 2 до насыщения дуги (). В результате получим поток , величина которого равна и который содержит насыщенную дугу . Удалим эту насыщенную дугу из и оставшийся орграф обозначим .

В оставшемся не существует пути их , который не содержал бы насыщенных дуг, т.е. поток является полным и его величина равна 13.

Задача №2. По данному логическому выражению построить таблицу истинности без предварительного упрощения функции

.

Построим таблицу истинности по частям, предварительно построив таблицу истинности для каждой конъюнкции, а затем в последнем столбце запишем логическую сумму (дизъюнкцию) соответствующих значений трех конъюнкций .

АВСF0001000000110000010000000110000010010000101101011100000011101011

Логические переменные А, В и С принимают всего значений, причем в таком порядке, что если перевести приведенные триады из двоичной системы в десятичную то получим числа от 0 до 7. В столбцах 5, 6 и 7 приведены элементарные конъюнкции, значения которых определяются перемножение соответствующих логических переменных. Значения дизъюнкций, приведенное в 8 столбце таблицы, определяется суммой соответствующих конъюнкций.

Задача №3. Функция задана десятичными эквивалентами единичных значений. Представить эту функцию в виде СДНФ или в виде СКНФ.

.

Поскольку в списке 14 чисел, т.е. 14 эквивалентов единичных значений, следовательно нулевых значений два (16-14=2). Поэтому по таблице истинности целесообразней строить СКНФ.

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

NF10001020010030011040100050101060110070111081000091001110101011110110*1211000*131101014111011511111

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

Справа напротив этих строк показаны полные элементарные функции, которые на соответствующих наборах равны нулю. СКНФ находится как конъюнкция этих дизъюнкций и будет иметь вид:

.

Задача №4. Упростить логические выражения с помощью карты Карно

.

Известно, что конъюнкции соответствует пересечение областей карты Карно, соответствующих сомножителям, а дизъюнкции соответствует объединение областей, соответствующих слагаемым. Конъюнкции второго ранга на карте Карно соответствует 4 клеточки. Затененная область на рис. 1,2,3 соответствует конъюнкциям соответственно. На рис.4 показано пересечение областей, соответствующих множителям . В соответствующих клетках пересечения областей стоят единицы и штриховкой показана область клеток для переменной .

ВВ А

А

С С

DDРис.1. Область Рис.2. Область

Клетки имеющие затенение и штриховку одновременно соответствуют исходной функции. Объединив эти три единицы в две пары, получим представление исходной функции в виде дизъюнкции двух конъюнкций третьего ранга .

ВВ А

А

С11 С

1 DDРис.3. Область Рис.4. Заполнение карты Карно

Теги: Построение полного потока в транспортной сети. Нахождение корней уравнения  Контрольная работа  Математика
Просмотров: 44615
Найти в Wikkipedia статьи с фразой: Построение полного потока в транспортной сети. Нахождение корней уравнения

3.3 Перестановки.

Пусть n(А) = m. Перестановкой без повторений из m элементов называется всякое упорядоченное m – элементное множество.

Число различных перестановок из m элементов равно произведению последовательных натуральных чисел от 1 до m включительно, то есть

Пример. Сколько различных пятизначных чисел можно записать с помощью цифр 0, 1, 2, 3, 4, если ни одна цифра в записи числа не повторяется дважды?

Решение. Число всех возможных перестановок из пяти цифр равно Р₅ = 5!. А поскольку цифра нуль не может занимать первое место, то искомое число есть:

Р₅ — Р₄ = 5! – 4! = 120 – 24 = 96.

Перестановкой с повторениями из элементов a, b,…,l, в которой эти элементы повторяются соответственно m₁, m₂, …, m_k раз, называется кортеж длины m = m₁ + m₂ +…+ m_k, среди компонент которого a встречается m₁ раз, b — m₂ раза и так далее l — m_k раз.

Обозначают число перестановок с повторениями символом

Число различных перестановок с повторениями из элементов a, b,…,l, в которой эти элементы повторяются соответственно m₁, m₂, …, m_kраз, определяется по формуле

Пример. Сколько восьмизначных чисел можно записать с помощью цифр 1, 3, 5 при условии, что цифра 1 повторяется в каждом числе четыре раза, цифры 3 и 5 – по 2 раза?

Решение. Искомое число является числом различных перестановок с повторениями из цифр 1, 3, 5, в которых цифра 1 повторяется четыре раза, а цифры 3 и 5 – по два раза. Поэтому по формуле имеем: .

3.4 Сочетания.

Всякое k-элементное подмножество m-элементного множества (km) называется сочетанием без повторений из m элементов по k.

Число различных сочетаний из m элементов по k обозначается символом

Пример.

Сколькими способами можно выбрать из 30 учащихся трех дежурных?

Решение. Так как порядок выбора дежурных не играет роли, то в задаче речь идет о выделении из множества, в котором 30 элементов подмножеств, содержащих по три элемента, то есть о сочетаниях без повторений из тридцати элементов по три.

Следовательно, .

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

Число различных сочетаний с повторениями из m элементов по k элементов будем обозначать символом .

Число различных сочетаний с повторениями из m типов элементов по k элементов определяется по формуле

Пример. В почтовом отделении продаются открытки четырех видов. Сколькими способами можно купить здесь 9 открыток?

Решение. Число способов купить открытки равно числу различных сочетаний с повторениями из 4 элементов по 9, то есть равно .

3.5 Число подмножеств конечного множества.

Пусть n(А) = m.

Число всех подмножеств множества А равно 2ⁿ.

Упражнение 6.

1. В классе 30 человек, посещающих факультативные занятия по физике и математике. Известно, что углубленно изучают оба предмета 10 человек, а математику – 25. Сколько человек посещают факультативные занятия только по физике?

2. Из 50 студентов 20 знают немецкий язык, а 15 — английский. Каким может быть число студентов, знающих оба языка; знающих хотя бы один язык?

3. Из 100 человек английский язык изучают 28, немецкий – 30, французский — 10 человек, немецкий и французский – 5, немецкий и английский – 15, английский и французский – 6 человек. Все три языка изучают 3 студента. Сколько студентов изучает только один язык? Сколько студентов не изучает ни одного языка?

4.

Задания для самостоятельной работы по теме «Комбинаторика» .

1. Расписание одного дня содержит 5 уроков по разным предметам. Определить количество таких расписаний при выборе из 11 предметов.

2. Комиссия состоит из председателя, его заместителя и еще пяти человек. Сколькими способами члены комиссии могут распределить между собой обязанности председателя и заместителя?

3. Сколькими способами можно выбрать трех дежурных из группы в 20 человек?

4. Сколько различных звукосочетаний можно взять на десяти выбранных клавишах рояля, если каждое звукосочетание может содержать от трех до десяти звуков?

5.В вазе стоят 10 красных и 5 розовых гвоздик. Сколькими способами можно выбрать из вазы пять гвоздик одного цвета?

6. Номера трамвайных маршрутов иногда обозначаются двумя цветными фонарями. Какое количество различных маршрутов можно обозначить, если использовать фонари восьми цветов?

7. Чемпионат, в котором участвуют 16 команд, проводится в два круга (т.е. каждая команда дважды встречается с любой другой). Определить, какое количество встреч следует провести.

8. Замок открывается только в том случае, если набран определенный трехзначный номер. Попытка состоит в том, что набирают наугад три цифры из заданных пяти цифр. Угадать номер удалось только на последней из всех возможных попыток. Сколько попыток предшествовало удачной?

9. Из группы в 15 человек выбирают четырех участников эстафеты 800 + 400 + 200 + 100. Сколькими способами можно расставить спортсменов по этапам эстафеты?

10. Команда из пяти человек выступает на соревнованиях по плаванию, в которых участвуют еще 20 спортсменов. Сколькими способами могут распределиться места, занятые членами этой команды?

11. Сколькими способами можно расположить на шахматной доске две ладьи так, чтобы одна не могла взять другую? (Одна ладья может взять другую, если она находится с ней на одной горизонтали или на одной вертикали шахматной доски.)

12. Две ладьи различного цвета расположены на шахматной доске так, что каждая может взять другую. Сколько существует таких расположений?

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

14. Тридцать человек разбиты на три группы I, II и III по десять человек в каждой. Сколько может быть различных составов групп?

15. Сколько четырехзначных чисел, делящихся на 5, можно составить из цифр 0, 1, 3, 5, 7, если каждое число не должно содержать одинаковых цифр?

16. Сколько различных светящихся колец можно сделать, расположив по окружности 10 разноцветных лампочек (кольца считаются одинаковыми при одинаковом порядке следования цветов)?

17. На книжной полке помещается 30 томов. Сколькими способами их можно расставить, чтобы при этом первый и второй тома не стояли рядом?

18. Четыре стрелка должны поразить восемь мишеней (каждый по две). Сколькими способами они могут распределить мишени между собой?

19. Из группы в 12 человек ежедневно в течение 6 дней выбирают двух дежурных. Определить количество различных списков дежурных, если каждый человек дежурит один раз.

20. Сколько четырехзначных чисел, составленных из цифр 0, 1, 2, 3, 4, 5 содержат цифру 3 (цифры в записи чисел не повторяются)?

21. Десять групп занимаются в десяти расположенных подряд аудиториях. Сколько существует вариантов расписания, при которых группы 1 и 2 находились бы в соседних аудиториях?

22. В турнире участвуют 16 шахматистов. Определить количество различных расписаний первого тура (расписания считаются различными, если отличаются участниками хотя бы одной партии; цвет фигур и номер доски не учитываются).

23. Шесть ящиков различных материалов доставляются на пять этажей стройки. Сколькими способами можно определить материалы по этажам? В скольких вариантах на пятый этаж доставлен какой-либо один материал?

24. Два почтальона должны разнести 10 писем по 10 адресам. Сколькими способами они могут распределить работу?

Вероятность

— выберите $3$ человек из $100$ и выберите $3$ человек, каждого из группы по $100$. Как найти последнее?

Спросил 2 года, 11 месяцев назад

Изменено 2 года, 11 месяцев назад

Просмотрено 360 раз

$\begingroup$

Случай 1: Мы выбираем $3$ человек из одной группы, не заменяя и не заботясь о заказе. Это можно сделать несколькими способами: $n\choose3$, если $n$ — количество человек в группе. Таким образом, вероятность выбора конкретных $3$ человек из всех людей в группе составляет ${n\choose3}$, я думаю. 93$? Кроме того, какова тогда была бы вероятность того, что мы выберем именно этих трех людей из всех, кого мы могли бы выбрать?

• вероятность
• комбинаторика
• дискретная математика
• комбинации

$\endgroup$

4

$\begingroup$

Используйте более простой пример: предположим, что у вас есть две группы по $3$ человек в каждой (скажем, группы $\{A,B,C\} и ${D,E,F}$. Сколькими способами можно вы выбираете двух человек, по одному из каждой группы?

Ну, вы можете выбрать $A$ и $D$, или $A$ и $B$, или $A$ и $F$, или …. и я думаю, вы быстро увидите, что будет $9 $ возможные комбинации. Действительно, для комбинаций вы умножаете, а не складываете.

$\endgroup$

2

Зарегистрируйтесь или войдите в систему

Зарегистрируйтесь с помощью Google

Зарегистрироваться через Facebook

Зарегистрируйтесь, используя адрес электронной почты и пароль

Опубликовать как гость

Электронная почта

Требуется, но не отображается

Опубликовать как гость

Электронная почта

Требуется, но не отображается

Нажимая «Опубликовать свой ответ», вы соглашаетесь с нашими условиями обслуживания, политикой конфиденциальности и политикой использования файлов cookie

комбинаторика — Выберите 3 человека из группы 10

Спросил 1 год, 11 месяцев назад

Изменено 1 год, 11 месяцев назад

Просмотрено 863 раза

$\begingroup$

Моя проблема заключается в следующем: сколько существует способов сформировать комитет из $3$ человек из группы из $10$ человек? Мой ответ: мы выбираем $3$ человек; есть $10\умножить на 9\times 8=P(10,3)$ способов сделать это. 3 = 3!$.

$\endgroup$

$\begingroup$

Причина этого в том, что если вы сказали A,B,C,D и должны были выбрать 2, то вы можете сделать это, выбрав первую букву. Например, A с a есть 3 различных комбинации: AB, AC, AD. После A мы можем игнорировать A и перейти к B, так как каждая буква уже удалена с A. С B мы имеем: BC, BD. Наконец, поскольку мы игнорируем A и B, остается только одна последняя комбинация — CD. Суммируя все это вместе, мы получаем 6 различных комбинаций, что равно nCr(4,2).

Если бы вы выбирали 3 разных элемента из списка из 5, таких как A,B,C,D,E, вы использовали бы аналогичный подход:

ABC Начните с первой буквы A и второй буквы B

ABD Добавить Все комбинации с B и D

ABE

ACD

ACE

ADE

BCD Игнорируйте A и повторный процесс

BCE

BDE

CDE Игнорируйте A и B и финише потому что у вас есть A nCr (количество букв, сколько вы выбираете-1) количество раз раз, B nCr (количество букв-1, сколько вы выбираете-1) и C nCr (количество букв-2 ,сколько вы выбираете -1).