Элементы комбинаторики (Учебное пособие)


ГБОУ СПО «АМТ» КК
Учебное пособие
Элементы комбинаторики
для студентов специальности
«Программирование в компьютерных системах»
Автор: Беляева Татьяна Юрьевна
Содержание
Введение 3
1. Основные понятия комбинаторики 3
1.1. Понятие о комбинаторике 3
1.2. Задача, приводящая к понятию факториала. Определение факториала 3
1.3. Основные правила комбинаторики 4
2. Соединения без повторений 5
2.1. Размещения без повторений 5
2.2. Перестановки без повторений 6
2.3. Сочетания без повторений 6
3. Соединения с повторениями 7
3.1. Размещения с повторениями 7
3.2. Перестановки с повторениями 7
3.3. Сочетания с повторениями 8
4. Бином Ньютона 9
4.1. Треугольник Паскаля 9
4.2. Бином Ньютона 9
4.3. Свойства разложения бинома 10
Задания для самостоятельного решения 12
Ответы
Тест для самоконтроля 13
14
Контрольные вопросы 16
Контрольные задания 17

Введение
Теория вероятностей и математическая статистика – две неразрывно связанные математические дисциплины. В настоящее время их знание необходимо специалистам самых различных профессий. Умение формулировать цель своей деятельности и предпринимать шаги для ее достижения – характерная особенность компетентного, конкурентно способного специалиста, а теория вероятностей и математическая статистика, как никакая другая дисциплина, способствуют позитивным изменениям личности.
Знание закономерностей массовых случайных явлений (предмет теории вероятностей) и важнейших методов и приёмов обработки результатов наблюдений (изучает математическая статистика) необходимо современному программисту при разработке алгоритмов решения практических задач. Изучение же теории вероятностей и математической статистики немыслимо без предварительного знакомства с основами комбинаторики.
Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». Сегодня комбинаторные методы используются для решения проблем теории информации, задач линейного программирования, для решения транспортных задач и много другого. Комбинаторные задачи представляют богатый материал для изучения основных конструкций, методов и приемов программирования, позволяют показать не только красоту математики, но и возможности новых компьютерных технологий при решении практических математических задач. Задачи дискретной математики, к которым относятся многие задачи практического программирования, часто сводятся к перебору различных комбинаторных конфигураций объектов и выбору среди них наилучшего, с точки зрения условия той или иной задачи. Поэтому знание алгоритмов генерации наиболее распространенных комбинаторных конфигураций является необходимым условием успешного решения задач в целом.
1. Основные понятия комбинаторики
1.1. Понятие о комбинаторике
Опр. Комбинаторика – раздел математики, изучающий различные комбинации элементов, обладающие определёнными свойствами.
Основной вопрос комбинаторики - сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов.
(!!) В отличие от множеств комбинации элементов могут содержать одинаковые (повторные) элементы.
1.2. Задача, приводящая к понятию факториала.
Определение факториала
Рассмотрим решение задачи: «Сколько разных n-значных чисел можно записать из n разных цифр?»
Из одной цифры (1) можно получить лишь одно однозначное число: 1.
Из 2-х цифр (1 и 2) можно получить 2 двузначных числа: 12 и 21. Это можно рассматривать так: к предыдущему случаю с числом 1 можно дописать 2 справа или слева, т.е. предыдущий случай надо умножить на 2 (1·2).
Из 3 цифр (1,2 и 3) можно получить 6 трехзначных чисел: 312, 132, 123 и 321, 231, 213. Это можно рассматривать так: к предыдущему случаю в каждом из двузначных чисел 3 можно дописать или слева, или справа, или посредине. Т.е. предыдущий случай надо умножить на 3 (1·2·3).
Нетрудно заметить закономерность: в каждом следующем случае ответ будет в n раз больше, чем в предыдущем. Получаем формулу для произвольного числа n: 1·2·3·...·(n-1)·n.
Ответ: 1·2·3·...·(n-1)·n
Опр. Произведение всех натуральных чисел от 1 до п включительно называется п-факториалом и обозначается п!
154876516827500
Т.о.: п! = 1∙2∙3∙…∙п
(!!) Считается, что о! = 1.
(!!) Факториал отрицательного числа не существует.
Основное свойство факториала: п! = (п - 1)!·п
Пример 1. Вычислите:
4!; б) 5!+4!3!; в) 7!∙4!10!8!3!∙5!- 9!7!∙2!.
/ а) 1∙2∙3∙4=24;
б) 3!(4∙5+4)3!=24
в) 5!∙6∙7∙3!∙4∙8!8!∙9∙10∙3!∙5!- 7!∙2!∙3∙4∙9!9!∙10∙7!∙2!= 2815- 65= 23 /
Пример 2. Упростите выражение:
5!m(m+1)∙m+1!m-1!∙3!, где т ∈N
/ 3!∙4∙5m(m+1)∙m-1!∙m∙m+1m-1!∙3!=20/
Пример 3. Решите уравнение: m!-m-1!m+1!= 16, где т ∈N
/ (m-1)!∙(m-1)(m-1)!∙m∙(m+1)= 16; 6∙m-1= m2+m; m2-5m+6=0; m1= 2; m2= 3 /
1.3. Основные правила комбинаторики
При решении комбинаторных задач часто применяются два важных правила.
Правило сложения: Если некоторый элемент «а» можно выбрать т числом способов, а другой элемент «в» – п числом способов, то выбор элемента «либо а, либо в» можно сделать (т + п) числом способов.
Задача 1. В группе 20 девушек и 5 юношей. Каким числом способов можно выбрать старосту?
/ Старостой может быть выбрана одна из 20 девушек или один из 5 юношей, а значит, общее число способов выбора старосты равно 20+5=25/
Правило умножения: Если некоторый элемент «а» можно выбрать т числом способов, а затем элемент «в» – п числом способов, то выбор пары «а и в» можно осуществить (т∙п) числом способов.
Задача 2. В группе 30 человек. Необходимо выбрать старосту и профорга. Сколькими способами это можно сделать?
/ Старостой может быть выбран любой из 30 учащихся, т.е. существует 30 способов выбора старосты. После того как староста уже выбран, профоргом можно выбрать любого из оставшихся 29 учащихся. Таким образом, одному способу выбора старосты соответствуют 29 способов выбора профорга. Следовательно, общее число способов выбора старосты и профорга равно 30 ∙29 = 870. /
(!!) Правила сложения и умножения имеют место для любого конечного числа элементов.
Задача 3. Сколько трёхзначных чётных чисел можно составить из цифр 0,1,2,3,4,5,6, если цифры могут повторяться?
/ При составлении трёхзначного числа авс из данных цифр вместо а можно взять любую цифру, кроме нуля (6 возможностей), вместо в можно взять любую из них (7 возможностей), вместо с можно взять любую из цифр 0,2.4.6 (4 возможности). Т.о., согласно правилу умножения, имеем 6∙7∙4= 168 способов составить число, удовлетворяющее условию задачи. /
(!!) Часто при решении комбинаторных задач работают оба правила.
Задача 4. Имеются 20 изделий 1-го сорта и 30 изделий 2-го сорта. Необходимо выбрать два изделия одного сорта. Сколькими способами это можно сделать?
/ По правилу умножения, два изделия 1-го сорта можно выбрать 20∙19=380 способами. Аналогично. Два изделия 2-го сорта можно выбрать 30∙29=870 способами. Т.к. по условию задачи следует выбрать два изделия одного сорта, неважно какого, то общее число способов выбора изделий одного сорта равно 380 + 870 = 1250. /
2. Соединения без повторений
Опр. Каждая конкретная комбинация, составленная из элементов данного конечного множества, называется выборкой или соединением.
При этом если выбирают т элементов из п различных элементов, то говорят, что они образуют соединение из п элементов по т. В зависимости от того, входят в соединение все п элементов или только их часть, а так же от того, имеет ли значение порядок элементов в соединении или нет, различают 3 вида соединений: размещения, перестановки и сочетания.
2.1. Размещения без повторений
Опр. Размещениями из п элементов по т (0≤m≤n) называются соединения, содержащие т различных элементов и отличающиеся или составом, или порядком их расположения.
Обозначение: Аnm («а из эн по эм»)
Выведем формулу для подсчёта Аnm.Ясно, что на первое место можно поместить любой из п эл-тов. Т.о., Аn1 = п.
Если на первом месте стоит один из п элементов, то на второе место можно поместить один из (п-1) оставшихся элементов. А значит, согласно правилу умножения, Аn2=nn-1.Рассуждая аналогично, получим: Аn3 = n(n-1)(n-2)
Аn4 = n(n-1)(n-2)(n-3)
…………………………
Аnm= n(n-1)(n-2)…(n-(m-1))
Выведем более универсальную формулу, для чего умножим и разделим произведение, стоящее в правой части формулы, на (п-т)!. Получим:
192024060198100Аnm = nn-1n-2…n-m-1n-m!n-m!= nn-1n-2…n-m+1n-mn-m-1…2·1n-m!= n!n-m!Итак: Аnm = n!n-m!
Задача 5. Сколько различных трёхзначных натуральных чисел можно составить из цифр 1, 3, 5, 7 и 9 при условии, что каждая из цифр в написании числа встречается не более одного раза?
/ Эта задача сводится к выбору и размещению на три разные позиции трёх из пяти различных цифр. Следовательно, А53= 60 /
2.2. Перестановки без повторений
Опр. Размещения из п элементов по п называются перестановками из п элементов.
Обозначение: Pn («пэ из эн»)
Так как любая перестановка содержит все п элементов, то различные перестановки отличаются друг от друга только порядком элементов.
Выведем формулу для подсчёта Рп.
314896528511500Рп = Аnn = n!n-n! = n!0!= n!1=n!Таким образом, Pn = n!
Задача 6. Сколькими способами можно расставить на полке в один ряд семь книг разных авторов?
/ Рп = 7! = 5040 /
2.3. Сочетания без повторений
Опр. Сочетаниями из п элементов по т (0≤m≤n) называются соединения т различных элементов, отличающиеся лишь составом (порядок не играет роли).
Обозначение: Cnm («цэ из эн по эм»)
Выведем формулу для подсчёта Cnm.Если взять все сочетания из п элементов по т и в каждом из них упорядочить элементы всеми возможными способами (сделать все перестановки), то получатся все размещения из п элементов по т.
Значит, Anm= Cnm∙PmОтсюда, Cnm= AnmPm= n!n-m!m! = n!n-m!m!232981518986400
Таким образом: Cnm = n!n-m!m!
(!!) Очевидно: Cn0= 1 и Cnn=1Задача 7. Сколькими способами читатель может выбрать две книжки из пяти имеющихся?
/ C52= 5!3!∙2!=…=10 /
3. Соединения с повторениями
Пусть дано множество М = а1;…;аn. Из данных п элементов составим комбинацию, в которой а1 встречается т1 раз, а2 – т2 раз и так далее до ап, который встречается тп раз. Обозначим т =m1 + m2 + … + mn.
3.1. Размещения с повторениями
В случае размещений какие-то тi могут оказаться равны нулю, поэтому т может оказаться как меньше п, так и равно п или больше п.
Число различных размещений из п элементов по т с повторениями обозначим Аnm. Найдём это число.
Пусть т = 1. На одно место можно поместить любой из п элементов, поэтому имеется п возможностей, т.е. Аn1=n.229171580010000Для выбора второго элемента имеется п возможностей, т.к. один и тот же элемент можно выбрать снова. А значит, два элемента из п элементов можно выбрать п·п=п2 числом способов, т.е. Аn2 = п2. Рассуждая аналогично, приходим к формуле:
Аnm = пm
Задача 8. Сколько различных трёхзначных чисел можно составить из цифр 1 и 2?
/ А23 = 23 = 8 (111, 112,…) /
Задача 9. Сколько различных двузначных чисел можно составить из цифр 1, 2, 3?
/ А32 = 32 = 9 /
3.2. Перестановки с повторениями
В случае перестановок в соединении присутствуют все элементы, поэтому m обязательно больше п. Если т = п, то каждый элемент встречается ровно один раз, что соответствует перестановкам без повторений
Число всех перестановок из т элементов с повторениями принято обозначать Рm1,m2,…,mn. Найдём это число.
Если бы все т элементов были между собой различны, то таких перестановок было бы т! = (т1 + т2 + … + тп)! Но так как не все элементы различны, то их будет меньше.
Если бы все т1 элементы были бы различны, то число перестановок возросло бы т1! раз. Если бы все т2 элементы были бы различны, то число перестановок возросло бы т2! Раз. А если бы т1 и т2 элементы были бы различны, то число перестановок возросло бы т1!·т2! раз. Учитывая все mi, получим, что число перестановок возросло бы в т1!·т2!·…· тп! раз. А значит, искомое число во столько раз меньше.
196786510795100
Итак: Рm1,m2,…,mn = (m1 +m2 + … + mn)! m1!∙m2!∙…∙mn!
Задача 10. Сколько различных пятизначных чисел можно составить из цифр 1, 2, 3, если 1 встречается 1 раз, 2 – 2 раза, 3 – 2раза?
/ Р1,2,2= (1 +2 + 2)! 1!∙2!∙2!= 30 /
Задача 11. Сколькими способами можно переставить буквы в слове «математика», чтобы получить всевозможные различные наборы букв?
/ Т.к. в слове «математика» десять букв, из них «м» встречается 2 раза, «а» - 3 раза, «т» - 2 раза, «е», «и» и «к» - по разу, то задача сводится к вычислению Р2,3,2,1,1,1 = 10!2!∙3!∙2!∙1!∙1!∙1! = 151200 /
3.3. Сочетания с повторениями
Число сочетаний из п элементов по т с повторениями обозначают Сnm. Найдём его.
Так как порядок расположения элементов не существенен, то сначала будем писать все а1, затем – а2 и так далее. Каждому такому сочетанию поставим во взаимно-однозначное соответствие символ (двоичную перестановку из элементов 0 и 1):
11…1m1011…1m20…011…1mnОчевидно, единиц записано т1 + т2 + … + тп = т штук, а нулей – (п – 1). Если какой-то элемент не входит в наше сочетание, то вместо соответствующей групы единиц пишется нуль.
Например: М = {a;b;c}
aabccc (11010111)
aaaacc (11110011)
bbbccc (01110111)
bbbbbb (01111110)
Т.о., различных сочетаний столько, сколько можно составить двоичных перестановок из цифр 0 и 1 с повторениями, т.е. Сnm= Pm,n-1.
1853565-6286500А значит, Cnm= m+n-1!m!n-1!
Задача 12. Имеются конфеты трёх сортов в коробках. Сколько можно составить различных наборов из пяти коробок?
/ C35= 7!5!∙2!=…=21 /
4. Бином Ньютона
4.1. Треугольник Паскаля
Формула Cnm = n!n-m!m! имеет несколько следствий:
Cn0= Cnn=1Cnm= Cnn-m – правило симметрии
Cnm= Cn-1m-1+Cn-1m - правило Паскаля
Последняя формула позволяет последовательно находить числа Cnm. Действительно,
- при п = 2 и т = 1 получим: С21= С10+ С11=1+1=2- при п = 3 и т = 1: С31= С20+ С21=1+2=3
- при п = 3 и т = 2: С32= С21+ С22=2+1=3
- при т = 4 и т = 1: С41= С30+ С31=1+3=4
- при т = 4 и т = 2: С42= С31+ С32=3+3=6
- при т = 4 и т = 3: С43= С32+ С33=3+1=4 и т.д.
Если числа Cnm расположить в виде следующей треугольной таблицы C00 C10 C11 C20 C21 C22
C30 C31 C32 C33 . . . . . . . . . . . .,
то в начале и в конце каждой строки будут стоять единицы, а остальные места могут быть легко последовательно заполнены таким образом, что на каждом месте в каждой строке стоит число, равное сумме двух чисел, стоящих над ним в предыдущей строке. Описанная таблица называется треугольником Паскаля. Первые шесть строк его выглядят так:
1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
4.2. Бином Ньютона
Числа, стоящие в 3-ей и 4-ой строках треугольника Паскаля, появляются при возведении двучлена (бинома) а + в в квадрат и в куб. Действительно, формулы
(а+в)2 = а2+2ав+в2 и (а+в)3 = а3+3а2в+3ав2+в3 можно записать так:
(а+в)2 = С20а2+С21ав+С22в2
(а+в)3 = С30а3+С31а2в+С32ав2+С33в3
Можно доказать, что аналогичные формулы справедливы для любой натуральной степени бинома, т.е.:
47244010160000
(a+b)n = Cn0an+Cn1an-1b+Cn2an-2b2+…+Cnman-mbm+…+CnnbnИспользуя знак суммы, эту формулу можно записать так:
119634014414500
(a+b)n = nm=0Cnman-mbm - формула Ньютона
Правая часть формулы Ньютона называется разложением натуральной степени бинома.
Коэффициенты Cnm называются биномиальными коэффициентами.
Пример 4. Возведите в 7-ю степень двучлен (х+1).
/ (х+1)7 =7m=0C7mх7-m1m= C70х710 + C71х611 + C72х512+ C73х413 + C74х314 + C75х215 + C76х116 + C77х017= х7 + 7х6 + 21х5 + 35х4 + 35х3 + 21х2 + 7х + 1 /
4.3. Свойства разложения бинома
Число всех членов разложения на 1 больше показателя степени бинома, т.е. равно п+1.
Сумма показателей степеней «а» и «в» каждого члена разложения равна показателю степени бинома (п-т+т=п). При этом показатель степени при «а» в любом следующем члене разложения на единицу меньше, чем в предыдущем, а показатель степени «в» – на единицу больше.
Общий член разложения (обозначим его Тт+1) имеет вид:
161544014922500
Тт+1 = Cnman-mbm , где m = 0,n.
Т обозначает член разложения, а индекс т+1 – его порядковый номер в разложении бинома, считая слева направо. Так,
Т1 = Cn0anТ2 = Cn1an-1b………………
Тп+1 = CnnbnБиномиальные коэффициенты членов разложения, равноотстоящих от концов разложения, равны между собой. Это следует из правила симметрии Cnm= Cnn-m. а) Если показатель степени бинома - чётное число(n = 2k), то число членов разложения равно 2k+1, при этом биномиальные коэффициенты первых k+1 членов разложения возрастают, а последних k+1 членов – убывают, и разложение имеет один наибольший биномиальный коэффициент Сnk.
б) Если показатель степени бинома - нечётное число(n = 2k+1), то число членов разложения равно 2k+2, при этом биномиальные коэффициенты первых k+1 членов разложения возрастают, а последних k+1 членов – убывают, и наибольшее значение принимают два равных между собой биномиальных коэффициента Сnk и Сnk+1.
6) Сумма биномиальных коэффициентов всех членов разложения равна 2п.
Действительно, если а = в = 1, то 2п = (1+1)п = Сn0+Cn1+…+Cnn.
7) Сумма биномиальных коэффициентов разложения, стоящих на нечётных местах, равна сумме биномиальных коэффициентов членов, стоящих на чётных местах, и равна 2п-1.
Пример 5. Найдите 4-ый член разложения (3а+ 13а)9.
/ Т4 = Т3+1 = С93 3а613а3 = … = 84а /

Задания для самостоятельного решения
1. В президиум избрали 3 человека. Каким числом способов они могут распределить обязанности председателя, секретаря и члена?
2. Сколько всех четырёхзначных чисел можно составить из цифр 1, 5, 6, 7?
3. Сколько существует двузначных чисел, имеющих обе чётные цифры?
4. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?
5. Сколько существует шестизначных чисел, которые делятся на 5?
6. Сколько различных натуральных чисел можно составить из цифр 1, 2, 3, 4, 5 при условии, что любая из цифр в написании числа встречается не более одного раза?
7. Любой телефонный номер состоит из пяти цифр. Сколько всего телефонных номеров, не содержащих других цифр, кроме 1, 2 и 3?
8. Сколькими способами можно расположить в ряд 2 зелёные и 4 красные лампочки?
9. Сколькими способами можно выбрать четыре монеты из 4-х пятикопеечных и 4-х десятикопеечных монет?
10. Сколькими способами можно разместить 8 пассажиров в 2 вагона?
11. В кондитерской имеется 5 сортов пирожных. Сколькими способами можно выбрать набор из 4-х пирожных?
12. Сколькими способами можно переставить буквы в слове какао, чтобы получились новые слова?
13. Вычислите:
А73+ А63+ А53; 2) А65+А64А63; 3) Р6÷Р7-Р3;
4) С149+С1410С1510; 5) Р6С75+С74С107; 6) C53∙C42+ C42∙C31+C31∙C20;
7) (P5A54+ P4A53)· С54.
14. Упростите: 1) Ank(n-k)!n-1!; 2) 2PnPn-2∙P2; 3) 1n!-1n+1!∙n!
15. Решите уравнение:
An-23=4An-32;
Pn+2=132Ank∙Pn-k;
5Cn3= Cn+24;
Аn4=6An-22;An4∙Pn-4=42Pn-2.16. Решите систему: Am-2n ÷Am-2n-1=3,Cm-2n÷Cm-2n-1=0,6.17. Найдите разложение степени бинома:
1) (а - 2b)5; 2) (x + x)6.
18. Найдите 9-ый член разложения степени бинома (1x+ x)12.
19. Найдите наибольший коэффициент многочлена (a + 1)10.
20. Найдите два средних члена разложения (a3 + ab)21.
21. Найдите номер члена разложения бинома (3х+ 1х)16, не содержащего х.
22. Найдите 7-ой член разложения бинома (а2а+ 3аа)п, если биномиальный коэффициент 3-го члена равен 36.
Ответы
1. 6 2. 256 3. 20 4. 900 5. 180000 6. 325 7. 243 8. 15
9. 5 10. 256 11. 70 12. 30 13. 1) 390; 2) 9; 3) 120839; 4) 1; 5) 115;
6) 81; 7) 7 14. 1) n; 2) n2 – n; 3) nn+1 15. 1) 6; 2) 10; 3) 3; 14; 4) ∅;
5)7 16. п = 5, т = 9 17. 1) а5-10а4в+40а3в2-80а2в3+80ав4-32в5; 2) х6+6х5х+15х5+20х4х+15х4+6х3х+х3 18. 495 x4 19. 252
20. Т11 = C2110 a43 b10 и Т12 = C2111 a41 b11 21. Т5 22. Т7 = 84а3а
Тест для самоконтроля
Задание № 1. (выберите один вариант ответа) Сократите дробь
Варианты ответов:
1) 2) 103) 1
Задание № 2. (выберите один вариант ответа) Вычислите: 6! -5!
Варианты ответов:
1) 600 2) 300 3)1
Задание № 3. (выберите варианты ответов согласно тексту задания) Установите соответствие между видом соединения (без повторения) и формулой для его вычисления.
А) перестановки Б) сочетания В) размещения
Варианты ответов:
1) 2) 3)
Задание № 4. (выберите один вариант ответа) Чему равно С102?
Варианты ответов:
1) 452) 903) 55
Задание № 5. (выберите один вариант ответа) Решите уравнение: Аn2 = 42.
Варианты ответов:
1) 7 2) 6 3) 6 и 7
Задание № 6. (выберите один вариант ответа) Сколькими способами можно из 6 открыток выбрать 3?
Варианты ответов:
1) 1202) 203) 18
Задание № 7. (выберите один вариант ответа) В футбольном турнире участвуют пять команд. Найдите число вариантов распределения призовых мест.
Варианты ответов:
1)202) 1203) 60
Задание № 8. (выберите один вариант ответа) Пете на день рождения подарили 5 новых дисков с играми, а Вале папа привез 6 дисков из командировки. Сколькими способами они могут обменять 3 любых диска одного на 3 диска другого?
Варианты ответов:
1) 30 2) 200 3) 330
Задание № 9. (выберите один вариант ответа) Сколько существует обыкновенных дробей, числитель и знаменатель которых – простые различные числа, не большие 20? (1 не является простым числом)
Варианты ответов:
1) 80 2) 56 3) 20
Задание № 10. (выберите один вариант ответа) Сколькими способами можно расставить 5 различных книг на полке, чтобы две определенные книги стояли рядом?
Варианты ответов:
1) 242) 1203) 48
Задание № 11. (выберите один вариант ответа) Сколькими способами можно закрасить 6 клеток таким образом, чтобы 3 клетки были красными, а 3 оставшиеся были закрашены (каждая своим цветом) былым, черным и зеленым?
Варианты ответов:
1) 1802) 1203) 240
Задание № 12. (выберите один вариант ответа) Каждый телефонный номер состоит из 5 цифр. Сколько всего телефонных номеров, содержащих только цифры 2, 3, 5 и 7?
Варианты ответов:
1) 562) 625 3) 1024

Контрольные вопросы
1. Что такое комбинаторика?
2. Сформулируйте правило умножения.
3. Сформулируйте правило сложения.
4. Что называется п – факториалом?
5. Что называется размещениями из п элементов по т?
6. Запишите формулу для подсчёта числа размещений из п элементов по т без повторений (с повторениями).
7. Что называется перестановками из т элементов?
8. Запишите формулу для числа перестановок из п элементов без повторений (с повторениями).
9. Что называется сочетаниями из п элементов по т?
10. Запишите формулу для числа сочетаний из п элементов по т без повторений (с повторениями).
11. В чем состоит правило симметрии?
12. Запишите правило Паскаля.
13. Запишите формулу разложения натуральной степени бинома (формулу Ньютона).
14. Как связано число всех членов разложения со степенью бинома?
15. Какой вид имеет общий член разложения?
16. Сколько наибольших биномиальных коэффициентов имеет разложение, если показатель степени является нечетным (четным) числом?
17. Чему равна сумма всех биномиальных коэффициентов разложения? Биномиальных коэффициентов, стоящих на четных (нечетных) местах?

Контрольные задания
В киоске продают 5 видов конвертов и 4 вида марок. Сколькими способами можно купить конверт и марку?
В футбольной команде (11 человек) нужно выбрать капитана и его заместителя. Сколькими способами это можно сделать?
Сколькими способами могут восемь человек стать в очередь к театральной кассе?
Позывные радиостанции должны начинаться с буквы W. 1) Скольким радиостанциям можно присвоить различные позывные, если позывные состоят из трех букв, причем эти буквы могут повторяться? 2) Если позывные состоят из четырех букв, которые не повторяются?
Сколько существует 9-значных чисел, цифры которых расположены в порядке убывания (то есть каждая следующая меньше предыдущей)?
Сколько семизначных чисел не содержат цифры 2?
Сколько существует 3-значных чисел, в запись которых входит ровно одна цифра 5?
В автомашине 7 мест. Сколькими способами семь человек могут усесться в эту машину, если занять место водителя могут только трое из них?
Из цифр 1, 2, 3, 4, 5 составляются всевозможные числа, каждое из которых содержит не менее трех цифр. Сколько таких чисел можно составить, если повторения цифр в числах запрещены?
Сколькими способами можно расставить на полке семь книг, если (а) две определенные книги должны всегда стоять рядом, (б) эти две книги не должны стоять рядом?
Номер автомобиля состоит из трех букв и трех цифр. Сколько различных номеров можно составить, используя 10 цифр и алфавит в 30 букв.
Сколькими способами из восьми человек можно избрать комиссию, состоящую из пяти членов?
Сколько четырехбуквенных слов можно образовать из букв слова сапфир? 2) Сколько среди них таких, которые не содержат буквы р? 3) Сколько таких, которые начинаются с буквы с и оканчиваются буквой р?
Начальник транспортного цеха пригласил несколько человек на совещание. Каждый участник совещания, входя в кабинет, пожимал руки всем присутствующим. Сколько человек участвовало в совещании, если было всего 78 рукопожатий?
Сколько существует шестизначных чисел, в записи которых есть хотя бы одна чётная цифра?

Приложенные файлы

  • docx file1.doc
    Размер файла: 87 kB Загрузок: 6