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

Министерство образования, науки и молодежной политики Краснодарского края

ГБПОУ КК «АМТ»

Учебное пособие

Элементы комбинаторики

для студентов специальности

09.02.03 «Программирование в компьютерных системах»

Содержание

3

1.3.

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

4

2.

Соединения без повторений

6

2.1.

Размещения без повторений

5

2.2.

Перестановки без повторений

7

2.3.

Сочетания без повторений

7

3.

Соединения с повторениями

8

3.1.

Размещения с повторениями

8

3.2.

Перестановки с повторениями

8

3.3.

Сочетания с повторениями

9

4.

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

10

4.1.

Треугольник Паскаля

10

4.2.

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

10

4.3.

Свойства разложения бинома

11

Задания для самостоятельного решения

13

Ответы

Тест для самоконтроля

14

15

Контрольные вопросы

17

Контрольные задания

18

Введение

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

Знание закономерностей массовых случайных явлений (предмет теории вероятностей) и важнейших методов и приёмов обработки результатов наблюдений (изучает математическая статистика) необходимо современному программисту при разработке алгоритмов решения практических задач. Изучение же теории вероятностей и математической статистики немыслимо без предварительного знакомства с основами комбинаторики.

Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 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 до п включительно называется п-факториалом и обозначается п!

Таким образом: п! = 1∙2∙3∙…∙п

(!!) Считается, что о! = 1.

(!!) Факториал отрицательного числа не существует.

Основное свойство факториала: п! = (п - 1)!·п

Пример 1. Вычислите:

1. 4!; б) ; в) .

/ а) 1;

б)

в) /

Пример 2. Упростите выражение:

, где т

/ /

Пример 3. Решите уравнение: , где т

/ ; 6;2; 3 /

1.3. Основные правила комбинаторики

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

Правило сложения: Если некоторый элемент «а» можно выбрать т числом способов, а другой элемент «в» – п числом способов, то выбор элемента «либо а, либо в» можно сделать (т + п) числом способов.

Задача 1. В группе 20 девушек и 5 юношей. Каким числом способов можно выбрать старосту?

/ Старостой может быть выбрана одна из 20 девушек или один из 5 юношей, а значит, общее число способов выбора старосты равно 20+5=25/

(!!) При использовании правила суммы в такой формулировке нужно следить, чтобы ни один из способов выбора объекта А не совпадал с каким-нибудь способом выбора объекта В. Если такие совпадения есть, то правило суммы утрачивает силу и получается лишь (m+n-k) способов выбора, где k-число совпадений.

Задача 2. В техникуме работают 76 преподавателей. Из них 49 знают английский язык, 32 - немецкий и 15 - оба языка. Сколько преподавателей не знает ни английского, ни немецкого языков?

/ Английский или немецкий язык знают 49 + 32 – 15 = 66 преподавателей. А значит, не знают ни одного из этих языков 77 – 66 = 10 преподавателей. /

Правило умножения: Если некоторый элемент «а» можно выбрать т числом способов, а затем элемент «в» – п числом способов, то выбор пары «а и в» можно осуществить (т∙п) числом способов.

Задача 3. В группе 30 человек. Необходимо выбрать старосту и профорга. Сколькими способами это можно сделать?

/ Старостой может быть выбран любой из 30 учащихся, т.е. существует 30 способов выбора старосты. После того как староста уже выбран, профоргом можно выбрать любого из оставшихся 29 учащихся. Таким образом, одному способу выбора старосты соответствуют 29 способов выбора профорга. Следовательно, общее число способов выбора старосты и профорга равно 30 ∙29 = 870. /

(!!) Правила сложения и умножения имеют место для любого конечного числа элементов.

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

/ При составлении трёхзначного числа авс из данных цифр вместо а можно взять любую цифру, кроме нуля (6 возможностей), вместо в можно взять любую из них (7 возможностей), вместо с можно взять любую из цифр 0,2.4.6 (4 возможности). Т.о., согласно правилу умножения, имеем 6∙7∙4= 168 способов составить число, удовлетворяющее условию задачи. /

(!!) Часто при решении комбинаторных задач работают оба правила.

Задача 5. Имеются 20 изделий 1-го сорта и 30 изделий 2-го сорта. Необходимо выбрать два изделия одного сорта. Сколькими способами это можно сделать?

/ По правилу умножения, два изделия 1-го сорта можно выбрать 20∙19=380 способами. Аналогично. Два изделия 2-го сорта можно выбрать 30∙29=870 способами. Т.к. по условию задачи следует выбрать два изделия одного сорта, неважно какого, то общее число способов выбора изделий одного сорта равно 380 + 870 = 1250. /

Задача 6. Сколько однозначных, двузначных и трехзначных четных чисел можно составить из цифр 0,1,2,3, если цифры могут повторяться?

/ Очевидно, что из данных цифр можно составить только одно четное однозначное число – 2.

При составлении двузначного числа ав из данных цифр вместо а можно взять любую цифру, кроме нуля (3 возможности), вместо в можно взять взять любую из цифр 0 и 2 (2 возможности). Т.о, согласно правилу умножения, имеем 3∙2= 6 способов составить нужное нам число.

При составлении трехзначного числа авс из данных цифр вместо а можно взять любую цифру, кроме нуля (3 возможности), вместо в можно взять любую из них (4 возможности), вместо с можно взять любую из цифр 0 и 2 (2 возможности). Т.о., согласно правилу умножения, имеем 3∙4∙2= 24 способа составить число, удовлетворяющее условию задачи.

Применяя правило сложения, получим: 1 + 6 + 24 = 31/

2. Соединения без повторений

Опр. Каждая конкретная комбинация, составленная из элементов данного конечного множества, называется выборкой или соединением.

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

2.1. Размещения без повторений

Опр. Размещениями из п элементов по т (0) называются соединения, содержащие т различных элементов и отличающиеся или составом, или порядком их расположения.

Обозначение: («а из эн по эм»)

Выведем формулу для подсчёта .

Ясно, что на первое место можно поместить любой из п эл-тов. Т.о., = п.

Если на первом месте стоит один из п элементов, то на второе место можно поместить один из (п-1) оставшихся элементов. А значит, согласно правилу умножения,

Рассуждая аналогично, получим: = n(n-1)(n-2)

= n(n-1)(n-2)(n-3)

…………………………

= n(n-1)(n-2)…(n-(m-1))

Выведем более универсальную формулу, для чего умножим и разделим произведение, стоящее в правой части формулы, на (п-т)!. Получим:

=

Итак: =

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

/ Однозначных - = 5

Двузначных - = 5·4 = 20

Трехзначных - = 5·4·3 = 60

Четырёхзначных - = 5·4·3·2 = 120

Пятизначных - = 5·4·3·2·1 = 120

По правилу сложения: 5+20+60+120+120= 325 /

2.2. Перестановки без повторений

Опр. Размещения из п элементов по п называются перестановками из п элементов.

Обозначение: P_n («пэ из эн»)

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

Выведем формулу для подсчёта Р_п.

Р_п = = =

Таким образом: P_n = n!

Задача 8. Сколько существует четырехзначных чисел, состоящих из цифр 1,3,5 и 7 (без повторений).

/ Р₄ = 4! = 24 /

Задача 9. Сколькими способами можно расставить на полке в один ряд семь книг, среди которых четыре книги разных авторов и трёхтомник одного автора, так, чтобы книги трёхтомника стояли рядом?

/ Если считать трехтомник за одну книгу, то будет 5 книг, которые можно переставить Р₅ = 5! = 120 способами. Т.к. книги трёхтомника можно переставлять между собой Р₃ = 3! = 6 способами, то по правилу умножения, всего возможно 120·6 = 720 перестановок /

2.3. Сочетания без повторений

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

Обозначение: («цэ из эн по эм»)

Выведем формулу для подсчёта .

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

Значит,

Отсюда, =

Таким образом: =

(!!) Очевидно:

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

/ = =…=10 /

Задача 11. В соревнованиях по волейболу участвуют 8 команд. Насколько более продолжительным будет турнир, организованный по круговой системе, чем по олимпийской?

/ При проведении турнира по круговой системе каждый участник встречался с каждым и порядок их вхождения в пару не важен. Следовательно, по круговой системе потребуется провести 28 встреч (, а по олимпийской только - 7 (четыре встречи в финала, две - в полуфинале и одна в финале)/

3. Соединения с повторениями

Пусть дано множество М = . Из данных п элементов составим комбинацию, в которой а₁ встречается т₁ раз, а₂ – т₂ раз и так далее до а_п, который встречается т_п раз. Обозначим т =m₁ + m₂ + … + m_n.

3.1. Размещения с повторениями

В случае размещений какие-то т_i могут оказаться равны нулю, поэтому т может оказаться как меньше п, так и равно или больше п.

Число различных размещений из п элементов по т с повторениями обозначим . Найдём это число.

Пусть т = 1. На одно место можно поместить любой из п элементов, поэтому имеется п возможностей, т.е. .

Для выбора второго элемента имеется п возможностей, т.к. один и тот же элемент можно выбрать снова. А значит, два элемента из п элементов можно выбрать п·п=п² числом способов, т.е. = п². Рассуждая аналогично, приходим к формуле:

= п^m

Задача 12. Сколько различных трёхзначных чисел можно составить из цифр 1 и 2?

/ = 2³ = 8 (111, 112,…) /

Задача 13. Сколько различных двузначных чисел можно составить из цифр 1, 2, 3?

/ = 3² = 9 /

3.2. Перестановки с повторениями

В случае перестановок в соединении присутствуют все п элементов, поэтому обязательно больше п. Если т = п, то каждый элемент встречается ровно один раз, что соответствует перестановкам без повторений

Число всех перестановок из т элементов с повторениями принято обозначать m_1,m₂,…,m_n. Найдём это число.

Если бы все т элементов были между собой различны, то таких перестановок было бы т! = (т₁ + т₂ + … + т_п)! Но так как не все элементы различны, то их будет меньше.

Если бы все т₁ элементы были бы различны, то число перестановок возросло бы т₁! раз. Если бы все т₂ элементы были бы различны, то число перестановок возросло бы т₂! раз. А если бы т₁ и т₂ элементы были бы различны, то число перестановок возросло бы т₁!·т₂! раз. Учитывая все m_i, получим, что число перестановок возросло бы в т₁!·т₂!·…· т_п! раз. А значит, искомое число во столько раз меньше.

Итак: m_1,m₂,…,m_n =

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

/ = 30 /

Задача 15. Сколькими способами можно переставить буквы в слове «математика», чтобы получить всевозможные различные наборы букв?

/ Т.к. в слове «математика» десять букв, из них «м» встречается 2 раза, «а» - 3 раза, «т» - 2 раза, «е», «и» и «к» - по разу, то задача сводится к вычислению = = 151200 /

3.3. Сочетания с повторениями

Число сочетаний из п элементов по т с повторениями обозначают . Найдём его.

Так как порядок расположения элементов не существенен, то сначала будем писать все а₁, затем – а₂ и так далее. Каждому такому сочетанию поставим во взаимно-однозначное соответствие символ (двоичную перестановку из элементов 0 и 1):

00…0

Очевидно, единиц записано т₁ + т₂ + … + т_п = т штук, а нулей – (п – 1). Если какой-то элемент не входит в наше сочетание, то вместо соответствующей групы единиц пишется нуль.

Например: М = {a;b;c}

1. aabccc (11010111)

2. aaaacc (11110011)

3. bbbccc (01110111)

4. bbbbbb (01111110)

Т.о., различных сочетаний столько, сколько можно составить двоичных перестановок из цифр 0 и 1 с повторениями, т.е. _m,n-1.

А значит,

Задача 16. Имеются конфеты трёх сортов в коробках. Сколько можно составить различных наборов из пяти коробок?

/ = =…=21 /

4. Бином Ньютона

4.1. Треугольник Паскаля

Формула = имеет несколько следствий:

2. – правило симметрии

3. - правило Паскаля

Последняя формула позволяет последовательно находить числа . Действительно,

- при п = 2 и т = 1 получим:

- при п = 3 и т = 1:

- при п = 3 и т = 2:

- при т = 4 и т = 1:

- при т = 4 и т = 2:

- при т = 4 и т = 3: и т.д.

Если числа расположить в виде следующей треугольной таблицы

. . . . . . . . . . . .,

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

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ав+в² и (а+в)³ = а³+3а²в+3ав²+в³ можно записать так:

(а+в)² = а²+ав+в²

(а+в)³ = а³+а²в+ав²+в³

Можно доказать, что аналогичные формулы справедливы для любой натуральной степени бинома, т.е.:

(a+b)ⁿ =

Используя знак суммы, эту формулу можно записать так:

(a+b)ⁿ = - формула Ньютона

Правая часть формулы Ньютона называется разложением натуральной степени бинома.

Коэффициенты называются биномиальными коэффициентами.

Пример 4. Возведите в 7-ю степень двучлен (х+1).

/ (х+1)⁷ = + + + + + + = + 7 + 21 + 35 + 35 + 21 + 7х + 1 /

4.3. Свойства разложения бинома

1. Число всех членов разложения на 1 больше показателя степени бинома, т.е. равно п+1.

2. Сумма показателей степеней «а» и «в» каждого члена разложения равна показателю степени бинома (п-т+т=п). При этом показатель степени при «а» в любом следующем члене разложения на единицу меньше, чем в предыдущем, а показатель степени «в» – на единицу больше.

3. Общий член разложения (обозначим его Т_т+1) имеет вид:

Т_т+1 = , где m = .

Т обозначает член разложения, а индекс т+1 – его порядковый номер в разложении бинома, считая слева направо. Так,

Т₁ =

Т₂ =

………………

Т_п+1 =

4. Биномиальные коэффициенты членов разложения, равноотстоящих от концов разложения, равны между собой. Это следует из правила симметрии .

5. а) Если показатель степени бинома - чётное число(n = 2k), то число членов разложения равно 2k+1, при этом биномиальные коэффициенты первых k+1 членов разложения возрастают, а последних k+1 членов – убывают, и разложение имеет один наибольший биномиальный коэффициент .

б) Если показатель степени бинома - нечётное число(n = 2k+1), то число членов разложения равно 2k+2, при этом биномиальные коэффициенты первых k+1 членов разложения возрастают, а последних k+1 членов – убывают, и наибольшее значение принимают два равных между собой биномиальных коэффициента и .

6) Сумма биномиальных коэффициентов всех членов разложения равна 2^п.

Действительно, если а = в = 1, то 2^п = (1+1)^п = .

7) Сумма биномиальных коэффициентов разложения, стоящих на нечётных местах, равна сумме биномиальных коэффициентов членов, стоящих на чётных местах, и равна 2^п-1.

Пример 5. Найдите 4-ый член разложения ()⁹.

/ Т₄ = Т₃₊₁ = = … = 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. Вычислите:

1. ; 2) ; 3) ;

; 5) ; 6) ;

7) ()· .

14. Упростите: 1) ; 2) ; 3)

15. Решите уравнение:

1. ;

2. ;

3. ;

16. Решите систему:

17. Найдите разложение степени бинома:

1) (а - )⁵; 2) (x + )⁶.

18. Найдите 9-ый член разложения степени бинома ()¹².

19. Найдите наибольший коэффициент многочлена (a + 1)¹⁰.

20. Найдите два средних члена разложения (a³ + ab)²¹.

21. Найдите номер члена разложения бинома ()¹⁶, не содержащего х.

22. Найдите 7-ой член разложения бинома ()^п, если биномиальный коэффициент 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) ; 4) 1; 5) ;

6) 81; 7) 7 14. 1) n; 2) n² – n; 3) 15. 1) 6; 2) 10; 3) 3; 14; 4) ;

5)7 16. п = 5, т = 9 17. 1) ; 2) 18. 495 x⁴ 19. 252

20. Т₁₁ = a⁴³ b¹⁰ и Т₁₂ = a⁴¹ b¹¹ 21. Т₅ 22. Т₇ = 84

Тест для самоконтроля

Задание № 1. (выберите один вариант ответа) Сократите дробь

Варианты ответов:

1) 2) 10 3) 1

Задание № 2. (выберите один вариант ответа) Вычислите: 6! -5!

Варианты ответов:

1) 600 2) 300 3)1

Задание № 3. (выберите варианты ответов согласно тексту задания) Установите соответствие между видом соединения (без повторения) и формулой для его вычисления.

А) перестановки Б) сочетания В) размещения

Варианты ответов:

1) 2) 3)

Задание № 4. (выберите один вариант ответа) Чему равно ?

Варианты ответов:

1) 45 2) 90 3) 55

Задание № 5. (выберите один вариант ответа) Решите уравнение: = 42.

Варианты ответов:

1) 7 2) 6 3) 6 и 7

Задание № 6. (выберите один вариант ответа) Сколькими способами можно из 6 открыток выбрать 3?

Варианты ответов:

1) 120 2) 20 3) 18

Задание № 7. (выберите один вариант ответа) В футбольном турнире участвуют пять команд. Найдите число вариантов распределения призовых мест.

Варианты ответов:

1) 20 2) 120 3) 60

Задание № 8. (выберите один вариант ответа) Пете на день рождения подарили 5 новых дисков с играми, а Вале папа привез 6 дисков из командировки. Сколькими способами они могут обменять 3 любых диска одного на 3 диска другого?

Варианты ответов:

1) 30 2) 200 3) 330

Задание № 9. (выберите один вариант ответа) Сколько существует обыкновенных дробей, числитель и знаменатель которых – простые различные числа, не большие 20? (1 не является простым числом)

Варианты ответов:

1) 80 2) 56 3) 20

Задание № 10. (выберите один вариант ответа) Сколькими способами можно расставить 5 различных книг на полке, чтобы две определенные книги стояли рядом?

Варианты ответов:

1) 24 2) 120 3) 48

Задание № 11. (выберите один вариант ответа) Сколькими способами можно закрасить 6 клеток таким образом, чтобы 3 клетки были красными, а 3 оставшиеся были закрашены (каждая своим цветом) былым, черным и зеленым?

Варианты ответов:

1) 180 2) 120 3) 240

Задание № 12. (выберите один вариант ответа) Каждый телефонный номер состоит из 5 цифр. Сколько всего телефонных номеров, содержащих только цифры 2, 3, 5 и 7?

Варианты ответов:

1) 56 2) 625 3) 1024

Контрольные вопросы

1. Что такое комбинаторика?

2. Сформулируйте правило умножения.

3. Сформулируйте правило сложения.

4. Что называется п – факториалом?

5. Что называется размещениями из п элементов по т?

6. Запишите формулу для подсчёта числа размещений из п элементов по т без повторений (с повторениями).

7. Что называется перестановками из т элементов?

8. Запишите формулу для числа перестановок из п элементов без повторений (с повторениями).

9. Что называется сочетаниями из п элементов по т?

10. Запишите формулу для числа сочетаний из п элементов по т без повторений (с повторениями).

11. В чем состоит правило симметрии?

12. Запишите правило Паскаля.

13. Запишите формулу разложения натуральной степени бинома (формулу Ньютона).

14. Как связано число всех членов разложения со степенью бинома?

15. Какой вид имеет общий член разложения?

16. Сколько наибольших биномиальных коэффициентов имеет разложение, если показатель степени является нечетным (четным) числом?

17. Чему равна сумма всех биномиальных коэффициентов разложения? Биномиальных коэффициентов, стоящих на четных (нечетных) местах?

Контрольные задания

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

2. В футбольной команде (11 человек) нужно выбрать капитана и его заместителя. Сколькими способами это можно сделать?

3. Сколькими способами могут восемь человек стать в очередь к театральной кассе?

4. Позывные радиостанции должны начинаться с буквы W. 1) Скольким радиостанциям можно присвоить различные позывные, если позывные состоят из трех букв, причем эти буквы могут повторяться? 2) Если позывные состоят из четырех букв, которые не повторяются?

5. Сколько существует 9-значных чисел, цифры которых расположены в порядке убывания (то есть каждая следующая меньше предыдущей)?

6. Сколько семизначных чисел не содержат цифры 2?

7. Сколько существует 3-значных чисел, в запись которых входит ровно одна цифра 5?

8. В автомашине 7 мест. Сколькими способами семь человек могут усесться в эту машину, если занять место водителя могут только трое из них?

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

10. Сколькими способами можно расставить на полке семь книг, если (а) две определенные книги должны всегда стоять рядом, (б) эти две книги не должны стоять рядом?

11. Номер автомобиля состоит из трех букв и трех цифр. Сколько различных номеров можно составить, используя 10 цифр и алфавит в 30 букв.

12. Сколькими способами из восьми человек можно избрать комиссию, состоящую из пяти членов?

13. Сколько четырехбуквенных слов можно образовать из букв слова сапфир? 2) Сколько среди них таких, которые не содержат буквы р? 3) Сколько таких, которые начинаются с буквы с и оканчиваются буквой р?

14. Начальник транспортного цеха пригласил несколько человек на совещание. Каждый участник совещания, входя в кабинет, пожимал руки всем присутствующим. Сколько человек участвовало в совещании, если было всего 78 рукопожатий?

15. Сколько существует шестизначных чисел, в записи которых есть хотя бы одна чётная цифра?

2016