Алгоритм решения комбинаторных задач

Правило суммы
Если элемент x можно выбрать способами nx и если элемент y можно выбрать ny способами, то выбор «либо x, либо y» можно осуществить способами nx+ ny.
Nx=4
Ny=5
Выбираем один шар
Любой цвет
Nx +Ny=4+5=9 способов

Пример 1
В коробке 10 тетрадей в клетку и 5 тетрадей в линию. Сколькими способами можно выбрать одну тетрадь?

Правило произведения
Если элемент x можно выбрать nx способами и если после его выбора элемент y можно выбрать ny способами, то выбор упорядоченной пары (x, y) можно осуществить nx∙ ny способами.
Nx=4
Ny=5
Выбираем пару шаров
Синий и рыжий
Nx ∙Ny=4∙5=20 способов

Пример 2
В магазине "Все для чая'' есть 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить чашку с блюдцем?

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

Перестановки без повторений
Перестановками без повторений из n различных элементов называются все возможные последовательности этих n элементов. Число перестановок без повторений из n элементов равняется
по определению

Перестановки без повторений
6 различных перестановок

Пример 3
Сколько различных гирлянд можно сделать из 10 светодиодов разного цвета?

Перестановки с повторениями
Перестановки с повторением из n элементов k типов
число элементов 1-го типа n1;
число элементов 2-го типа n2; …;
число элементов k-го типа nk,
все возможные последовательности исходных n элементов. Число перестановок с повторениями обозначают
подсчитывают так:

Перестановки с повторениями
n1=2
n2=1
n=n1+n2=2+1=3
3 различные перестановки

Пример 4
Дворовая футбольная команда выбирает капитана и его заместителя. Сколькими способами это можно сделать, если в команде 11 человек?

Пример 5
Сколько различных гирлянд можно сделать, если у нас 5 красных, 7 синих и 4 желтых светодиода?
Сколько различных гирлянд получится, если замкнуть гирлянду из предыдущей задачи в кольцо?

Размещения
(выборки)

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

Размещения без повторений
n=3
Выбираем два шара
m=2
Порядок выбора важен!
6 различных выборок

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

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

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

Размещения с повторениями
k=2
n=3
8 вариантов выборок

Пример 8
Назовем натуральное число "симпатичным", если в его записи встречаются только нечетные цифры. Сколько существует четырехзначных "симпатичных" чисел?

Сочетания

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

Сочетания без повторений
n=3
Выбираем два шара
m=2
Порядок выбора не важен!
3 сочетания

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

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

Сочетания с повторениями
k=2
m=3
4 варианта сочетаний

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

Один выбор (анализ) элементов или несколько? Если один, то см. п.3
Каким союзом варианты выбора (анализа) соединяются? «И» – правило произведения, «или» – правило суммы.
Для каждого выбора задаются следующие вопросы:
Все элементы используются? Если «да», то это перестановки. Переходим к п. 5.
Порядок выбора элементов важен? Если «да», то это размещения, «нет» – сочетания.
Есть ли одинаковые элементы? Если «да» – то формула с повторениями, «нет» – без повторений.

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

Пример 12
У людоеда в подвале томятся 25 пленников.
а) Сколькими способами он может выбрать трех из них себе на завтрак, обед и ужин?
б) А сколько есть способов выбрать троих, чтобы отпустить на свободу?

Пример 13
Волонтеры разделились на две равные группы для розыска заблудившегося ребенка. Среди них только 4 знакомы с местностью. Каким числом способов они могут разделиться так, чтобы в каждую группу вошло 2 человека, знающих местность, если всего их 16 человек?

Пример 14
Сколько существует натуральных чисел, меньших 25610, таких, что в записи каждого числа в двоичной системе счисления будет равное количество единиц и значащих нулей. В ответе укажите целое число.