Основы комбинаторики

Основные формулы

Предполагается, что m и n натуральные числа, причем m n.

Число перестановок из n элементов

(принято, что ).

При больших значениях n для приближенного вычисления применяется формула Стирлинга

,

или

.

Число сочетаний из n элементов по m

.

Справедливы следующие свойства сочетаний:

1. (свойство симметрии);
2. (свойство Паскаля);
3. .

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

.

Если среди n элементов есть одинаковые (i-тый элемент повторяется n_i раз), то число различных сочетаний равно

,

где .

Число размещений из n элементов по m определяется по формуле

,

или

.

Число размещений из n элементов по m с повторениями:

.

Бином Ньютона:

.

Принято (к+1) член бинома обозначать через Т_к, то есть

(к=0,1,2,...,n).

Полиномиальная формула

.

Примеры

Пример 1. Решить уравнение

.

Решение

По формулам имеем

Так как,

,

то .

Рассуждая аналогично, находим

.

Подставив в исходное уравнение выражения для и , приведя подобные члены, придем к уравнению

.

Решив это уравнение, находим: , .

Так как , то решением уравнения является .

Пример 2. На организацию соревнований выделено 760 условных денежных единиц (УДЕ). Сколько команд организаторы соревнований могут пригласить к себе, если команды встречаются между собой два раза, а на каждую игру выделяется 1 УДЕ?

Решение

Так как команды встречаются между собой два раза, то здесь необходимо применить формулу для размещений без повторений. В данном случае получаем или n(n-1)=760.

Получили квадратное уравнение n²-n-760=0.

Решив уравнение, находим .

Так как n N, то решением задачи будет n=23.

Варианты задачи №4

1. Сколько различных слов можно составить из пяти букв «а» и не больше, чем трех букв «в»?

2. Имеется по две монеты 5; 10; 50 копеек. Сколькими способами можно выбрать две из этих шести монет?

3. Для решения задачи с помощью ЭВМ используются в определенном порядке по две программы каждого из трех типов a, b, c. В списке указаны 88 последовательностей из шести программ: aabbcc; aabcbc; aacbbc;….Все ли такие последовательности вошли в список?

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

5. Сколькими способами можно обозначить треугольник, отмечая его вершины большими латинскими буквами?

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

7. Сколькими способами четверо юношей могут пригласить танцевать четырех из шести девушек?

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

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

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

11. Тридцать человек разбиты на три группы по 10 человек в каждой. Сколько может быть различных составов групп?

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

13. Восемь авторов должны написать книгу из 16 глав. Сколькими способами возможно распределение материала между авторами, если два человека напишут по три главы, четыре – по две, два – по одной главе книги?

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

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

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

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

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

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

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

21. Буквы азбуки Морзе состоят из символов (точек и тире). Сколько букв можно изобразить, если потребовать, чтобы каждая буква содержала не больше пяти символов?

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

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

24. Лифт останавливается на 10 этажах. Сколькими способами могут распределиться между этими остановками восемь пассажиров, находящихся в кабине лифта?

25. Из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 составляются пятизначные числа, не содержащие одинаковых цифр. Определить количество чисел, в которых присутствуют цифры 2, 4 и 5 одновременно.

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

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

28. Три автомашины № 1, 2, 3 должны доставить товар в шесть магазинов. Сколькими способами можно использовать машины, если грузоподъемность каждой из них позволяет взять товар сразу для всех магазинов, и если две машины в один и тот же магазин не направляются? Сколько существует вариантов маршрута, если решено использовать только машину № 1?

29. Поезд метро делает 16 остановок, на которых выходят все пассажиры. Сколькими способами могут распределиться между этими остановками 100 пассажиров, вошедших в поезд на конечной остановке?

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

Варианты задачи №5

Решить уравнения 1 – 13:

1. .

2. .

3. .

4. .

5. .

6. .

7. .

8. .

9. .

10. .

11. .

12. .

13. .

14. Показать, что при любом k сумма есть точный квадрат.

15. Доказать тождество .

16. Доказать тождество .

17. Сумма биномиальных коэффициентов равна 256. Найти коэффициент члена бинома Ньютона , который содержит .

18. Каков наибольший коэффициент разложения , если сумма всех коэффициентов равна 4096?

19. Сумма биномиальных коэффициентов разложения равна 64. Найти слагаемое, не содержащее x.

20. Сумма биномиальных коэффициентов с нечетными номерами в разложении равна 512. Найти слагаемое, не содержащее x.

21. Определить , если пятое слагаемое разложения не зависит от x.

22. В разложении имеется член, содержащий ab. Найти этот член.

23. В какую натуральную степень следует возвести бином , чтобы отношение четвертого слагаемого разложения к третьему было равно ?

24. При каком значении x четвертое слагаемое разложения в 20 раз больше m, если биномиальный коэффициент четвертого слагаемого относится к биномиальному коэффициенту второго слагаемого как 5:1?

25. Сумма коэффициентов второго и третьего слагаемых разложения равна 25,5. Написать член, не содержащий x.

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

27. Разность между третьими биномиальными коэффициентами разложений и равна 225. Найти число рациональных членов разложения .

28. Сумма третьего от начала и четвертого от конца биномиальных коэффициентов разложения равна 9900. Сколько рациональных членов содержится в этом разложении?

29. При каких значениях x четвертое слагаемое разложения больше двух соседних с ним слагаемых?

30. Найти k-й член разложения , если известно, что

1. Элементы математической логики

Основные понятия и формулы

Высказывание – это всякое утверждение, о котором имеет смысл говорить, что оно истинно или ложно.

В математической логике обычно истинность высказывания обозначается 1, ложность – 0.

Высказывания, истинные (ложные) во всех возможных ситуациях, называются абсолютно истинными (абсолютно ложными). Абсолютно истинные и абсолютно ложные высказывания называются логическими константами.

Одноместная логическая операция – отрицание: отрицание истинного ложно и наоборот (таблица 2). Отрицание - одноместная операция в том смысле, что из одного простого высказывания А строится новое высказывание `А или ØА (читается: не А).

Таблица 2 - Таблица истинности операции отрицания

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

Конъюнкция (логическое умножение): высказывание АÙВ (читается: А и В) истинно тогда и только тогда, когда истинны оба высказывания А и В (таблица 3).

Таблица 3 - Таблица истинности операции конъюнкции

		Ù

Дизъюнкция (логическое сложение) высказываний А и В - высказывание АÚВ (читается: А или В), которое истинно тогда и только тогда, когда истинно хотя бы одно из высказываний А или В (таблица 4).

Таблица 4 - Таблица истинности операции дизъюнкции

Альтернативная дизъюнкция (сложение по модулю 2) высказываний А и В - высказывание А В (читается: или А, или В), которое истинно тогда и только тогда, когда истинно только одно из высказываний А или В (таблица 5).

Таблица 5 - Таблица истинности операции альтернативной дизъюнкции

Импликация высказываний А и В - высказывание А®В (читается: если А, то В), которое ложно тогда и только тогда, когда А истинно, а В ложно (таблица 6). А называется посылкой, В – следствием.

Таблица 6 - Таблица истинности операции импликации

		®

Эквивалентность высказываний А и В - высказывание А В (читается А эквивалентно В), которое истинно тогда и только тогда, когда А и В оба истинны или оба ложны (таблица 7).

Таблица 7 - Таблица истинности операции эквивалентности

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

Стрелкой Пирса или антидизъюнкцией называется логическая операция, определяемая формулой .

Функцией алгебры логики от n переменных х₁,x₂,...,x_n называется функция f(x₁,x₂,...,x_n), принимающая значения 0 или 1, аргументы которой также принимают значения 0 или 1.

Функция алгебры логики f(x₁,x₂,...,x_n) может задаваться своей таблицей истинности, в каждой строке которой дается набор длины n значений логических переменных x₁,x₂,...,x_n и соответствующее значение функции алгебры логики.

Всего возможных наборов n логических переменных равно N=2ⁿ.

Всего функций алгебры логики от n логических переменных равно 2^N, где N=2ⁿ.

Функции f и g алгебры логики от n логических переменных x₁,x₂,...,x_n называются равносильными (f=g), если при каждом возможном наборе логических переменных значения f и g равны (таблицы истинности функций совпадают).

Если f(x)=0, то говорят, что f тождественно равна 0.

Если f(x)=1, то говорят, что f тождественно равна 1.

В алгебре логики знак конъюнкции Ù (логическое умножение) обычно опускается: xÙy=xy.

Важнейшие равносильности алгебры логики:

Суперпозиция основных логических функций

называется формулой.

Введем обозначение:

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

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).

Элементарная конъюнкция называется правильной, если в нее каждая переменная входит не более одного раза, включая ее вхождение под знаком отрицания.

Правильная элементарная конъюнкция называется полной относительно переменных x₁,x₂,...,x_n, если в нее каждая из этих переменных входит один и только один раз, быть может, со знаком отрицания.

Совершенной дизъюнктивной нормальной формой (СДНФ) относительно переменных x₁,x₂,...,x_n называется полная правильная ДНФ, в которой нет одинаковых элементарных конъюнкций.

Всякую функцию алгебры логики f(x₁,x₂,...,x_n), не равную тождественно нулю, можно представить совершенной дизъюнктивной нормальной формой:

,

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

Формула вида называется элементарной дизъюнкцией.

Всякая конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ).

Элементарная дизъюнкция называется правильной, если в нее каждая переменная входит не более одного раза, включая ее вхождение под знаком отрицания.

Правильная элементарная дизъюнкция называется полной относительно переменных x₁,x₂,...,x_n, если каждая из этих переменных входит в нее один и только один раз, быть может, со знаком отрицания.

Совершенной конъюнктивной нормальной формой (СКНФ) относительно переменных x₁,x₂,...,x_n называется полная, правильная КНФ, в которой нет одинаковых элементарных дизъюнкций.

Всякую функцию алгебры логики f(x₁,x₂,...,x_n), не равную тождественно 1, можно представить совершенной конъюнктивной нормальной формой:

,

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

Для упрощения ДНФ или КНФ рекомендуется применять следующие равносильности:

Примеры

Пример 1. Функция алгебры логики трех переменных f(x₁,x₂,x₃)=1 лишь при следующем наборе значений логических переменных:

Найти аналитическое выражение функции, оптимизировать её.

Решение

Так как функция равна 1 на трех из восьми возможных наборов значений переменных, то СДНФ рассматриваемой функции имеет вид:

.

Сгруппируем второе и третье дизъюнктивные слагаемые, вынесем за скобки общий множитель и в соотсетствии с равенством , получим:

.

Учитывая, что , приходим к следующему результату:

.

Если для реализации функции, полученной по СДНФ, необходимо выполнить 12 логических операций, то после оптимизации достаточно только шесть.

Пример 2. Функция алгебры логики трех переменных f(x₁,x₂,x₃)=0 лишь при следующем наборе значений логических переменных:

Найти оптимальное аналитическое выражение функции.

Решение

Количество наборов переменных, при которых значение функции равно 0 значительно меньше числа наборов значений переменных, при которых значение функции равно 1. Поэтому для решения задачи применим СКНФ. Тогда

.

Выполним преобразования. Обозначим . Тогда

= .

Таким образом, .

Раскрыв скобки, получим:

.

Окончательно получаем .

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

Варианты задачи №6

Составить таблицы истинности формул

1. ; .
2. ; .
3. ; .
4. ; .
5. ; .
6. ; .
7. ; .
8. ; .
9. ; .
10. ; .
11. ; .
12. ; .
13. ; .
14. ; .
15. ; .
16. ; .
17. ; .
18. ; .
19. ; .
20. ; .
21. ; .
22. ; .
23. ; .
24. ; .
25. ; .
26. ; .
27. ; .
28. ; .
29. ; .
30. ; .

Варианты задачи №7

Проверить двумя способами, будут ли эквивалентны указанные в вариантах формулы:

а) составлением таблиц истинности;

б) приведением к СДНФ или СКНФ с помощью эквивалентных преобразований

1. и .
2. и .
3. и .
4. и .
5. и .
6. и .
7. и .
8. и .
9. и .
10. и .
11. и .
12. и .
13. и .
14. и .
15. и .
16. и .
17. и .
18. и .
19. и .
20. и .
21. и .
22. и .
23. и .
24. и .
25. и .
26. и .
27. и .
28. и .
29. и .
30. и .

Варианты задачи №8

В вариантах 1-15 найти оптимальное аналитическое выражение функции алгебры логики, применяя СДНФ, если она равна 1 лишь при указанных в таблице наборах логических переменных, а в остальных случаях 0.

Таблица 8 – Варианты задачи №8

Продолжение таблицы 8

В вариантах 16-30 найти оптимальное аналитическое выражение функции алгебры логики, применяя СКНФ, если она равна 0 лишь при указанных в таблице наборах логических переменных, а в остальных случаях 1:

Продолжение таблицы 8

Продолжение таблицы 8

Поиск по сайту: