Специальные приемы, используемые
При решении комбинаторных задач
При решении комбинаторных задач помимо метода перебора вариантов и правил комбинаторики часто приходится использовать ряд приемов. К ним относятся: «фиксирование» элементов, «склеивание» элементов, подсчет «ненужных» вариантов.
Фиксирование» элементов
В условии некоторых задач говорится, что некоторые элементы должны занимать вполне определенные места в формируемой комбинации. В таких случаях следует уменьшить количество элементов и количество мест на число «фиксированных» элементов и найти количество способов расположения оставшихся элементов на оставшихся местах. Найденное количество останется умножить на число перестановок «фиксированных» элементов между собой на их местах.
Пример 3. Сколько различных шестизначных чисел, начинающихся с двух четных цифр, можно составить из цифр 1, 2, 3, 4, 5, 7, 9? Цифры в числе не повторяются.
Решение. Изобразим схематично условие задачи.
| 1ая цифра | 2ая цифра | 3ая цифра | 4ая цифра | 5ая цифра | 6ая цифра |
| 2 или 4 | … | … | … | … | |
«Фиксированные» элементы – это цифры 2 и 4 в первых двух разрядах шестизначного числа, тогда остаются пять цифр, которые нужно расставить по четырем местам.
Пусть n1 – число способов выбрать третью цифру в составляемом числе, а n2 – число способов выбрать четвертую цифру, и т.д. Тогда n1 =5, n2 =4, … и по правилу произведения получим: N1= n1∙n2∙n3 n4∙=5∙4∙3∙2=120 – число способов составить четыре последние цифры шестизначного числа.
|
|
|
«Фиксированные» цифры 2 и 4 в первых двух разрядах можно поставить N2 способами: N2=Р2=2!=1·2=2.
Тогда по правилу произведения окончательно получим:
N= N1· N2=120·2=240.
Ответ: 240.
Склеивание» элементов
В некоторых задачах требуется, чтобы два или более элементов в составляемой комбинации всегда стояли рядом. В таких случаях все эти элементы рассматривают как один новый («склеенный»), соответственно уменьшают число рассматриваемых элементов и находят количество способов расположения оставшихся элементов на оставшихся местах. Найденное количество способов умножают на число перестановок в «склейке».
Рассмотрим описанный прием на примере.
Пример 4. Сколькими способами можно расставить на витрине 8 игрушек в ряд, из которых 3 – это игрушечные зайцы, а остальные другие мягкие игрушки? При этом зайцы должны находиться рядом.
Решение. «Склеим» 3 зайцев, тогда число элементов, расставляемых на витрине, станет равным: 8 – 3 + 1 = 6. Если N1 – число способов переставить между собой 6 элементов, то N1=Р6=6!=720.
Количество перестановок в «склейке» N2 найдем как 3!, то есть N2=Р3=3!=6.
|
|
|
Тогда по правилу произведения окончательно получим:
N= N1· N2=720·6=4320.
Ответ: 4320.
Подсчет «ненужных» вариантов
В ряде случаев для того, чтобы найти число комбинаций, обладающих требуемым свойством, проще найти число комбинаций, не обладающих этим свойством, а затем вычесть его из общего числа возможных комбинаций.
Такая возможность может быть обоснована с помощью комбинаторного правила суммы.
Пример 5. Сколько имеется четырехзначных чисел, в записи которых есть хотя бы одна нечетная цифра?
Решение. Элементами исходного множества являются цифры от 0 до 9, а местами для их распределения – разряды от 1 до 4. Пусть N – это общее количество четырехзначных чисел, а N2 – количество четырехзначных чисел, состоящих только из четных цифр, то есть число «ненужных» вариантов. Тогда N1= N - N2 – количество чисел, имеющих в записи хотя бы одну нечетную цифру.
По правилу произведения найдем N и N2:
N=9·10·10·10=9000 и N2= 4·5·5·5=500.
Тогда окончательно получим: N1= N - N2 = 9000-500=8500.
Ответ: 8500.
Дата добавления: 2022-07-02; просмотров: 99; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!