ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
I. Для решения следующих задач используйте принципы умножения и сложения
1.Сколькими способами могут восемь человек стать в очередь к театральной кассе?
2.Позывные радиостанции должны начинаться с буквы W. Скольким радиостанциям можно присвоить различные позывные, если позывные состоят из 3 латинских букв, причем эти буквы могут повторяться? Если позывные состоят из 4 букв, которые не повторяются?
3.В автомашине 7 мест. Сколькими способами 7 человек могут усесться в эту машину, если занять место водителя могут только 3 из них?
4.В классе 30 одноместных парт. Сколькими способами можно рассадить на них шестерых школьников?
5.У нас есть 3 письма, каждое из которых мы можем послать по 6 различным адресам. Сколькими способами можно осуществить рассылку писем, если никакие 2 письма нельзя посылать по одному адресу? Сколькими способами можно разослать письма, если по одному адресу разрешается посылать более одного письма?
6.Сколько существует пятизначных чисел? Сколько среди них таких, которые начинаются цифрой 2 и оканчиваются цифрой 4? Которые не содержат цифры 5? Которые делятся на 5?
7.Сколько пятизначных чисел можно составить из цифр 1, 2, 4, 6, 7, 8, если никакую цифру не использовать более одного раза? Сколько среди этих чисел будет четных? Сколько нечетных?
8.Из цифр 1, 2, 3, 4, 5 составляются всевозможные числа, каждое из которых содержит не менее трех цифр. Сколько таких чисел можно составить, если повторения цифр в числах запрещены?
9.5 мальчиков и 5 девочек рассаживаются в ряд на 10 подряд расположенных мест, причем мальчики садятся на нечетные места, а девочки на четные. Сколькими способами они могут это сделать?
10.Сколькими способами 3 различных подарка A, В и С можно выдать каким-то трем из 15 лиц, если никто не должен получить более одного подарка? Если подарок A должно получить вполне определенное лицо?
11.Энциклопедия состоит из 9 томов — с 1-го по 9-й. Сколькими способами ее можно поставить на полке в беспорядке, т. е. так, чтобы тома не следовали один за другим в порядке их номеров?
12.Сколькими различными способами из восьми книг можно отобрать несколько, но не менее одной?
13.Сколько сигналов можно поднять на мачте, имея 4 флага различных цветов, если каждый сигнал должен состоять не менее чем из двух флагов?
14.В забеге участвуют 5 мальчиков. Сколькими способами могут распределиться два первых места?
II. Для решения следующих задач используйте формулы для перестановок и размещений
1.Сколько слов можно образовать из букв слова фрагмент, если слова должны состоять:
(а) из 8 букв, (б) из 7 букв, (в) из 3 букв?
2.Студенту необходимо сдать 4 экзамена в течение десяти дней. Сколькими способами можно составить ему расписание экзаменов?
3.Доказать, что число трехбуквенных слов, которые можно образовать из букв, составляющих слово «гипотенуза», равно числу всех возможных перестановок букв, составляющих слово «призма».
4.Сколько существует различных автомобильных номеров, которые состоят из 5 цифр, если первая из них не равна нулю? Если номер состоит из одной буквы, за которой следуют четыре цифры, отличные от нуля?
5.Три дороги соединяют города А и В, четыре дороги соединяют В и С. Сколькими способами можно совершить поездку из А в С через В и вернуться в А также через В?
6.Сколькими способами можно расставить на полке семь книг, если: (а) 2 определенные книги должны всегда стоять рядом, б) эти 2 книги не должны стоять рядом?
7.Сколько 5-буквенных слов можно образовать, используя для этого 10 различных букв, если: (а) никакую букву нельзя использовать в одном слове более одного раза, (б) повторения букв разрешены. Сколько в последнем случае встретится слов, в которых на самом деле есть повторения?
8.Сколько различных трехбуквенных слов можно образовать, используя буквы, составляющие вашу фамилию, причем эти слова должны начинаться и оканчиваться согласными, а в середине должна стоять гласная буква?
III. Для решения следующих задач используйте формулы для сочетаний
1.Сколькими способами из восьми человек можно избрать комиссию, состоящую из пяти членов?
2.Подрядчику нужны 4 плотника, а к нему с предложением своих услуг обратились 10. Сколькими способами он может выбрать среди них четверых?
3.Компания из 20 мужчин разделяется на три группы, в первую из которых входят 3 человека, во вторую — 5 и в третью — 12. Сколькими способами они могут это сделать? (Ответ записать в виде произведения сомножителей, не вычисляя его.)
4.Сколькими способами можно отобрать несколько фруктов из семи яблок, четырех лимонов и девяти апельсинов? (Фрукты одного вида считаем неразличимыми.)
5.Сколькими способами из 9 книг можно отобрать 4? Сколькими способами это можно сделать, если в число отобранных должна входить некая определенная книга? Сколькими способами можно отобрать 4 книги так, чтобы определенная книга не входила в их число?
6.Колода карт содержит 52 различные карты. Сдача карт одному игроку состоит из 5 карт, порядок которых не важен. Запишите число всех возможных сдач одному игроку, используя факториалы.
7.Колода карт содержит 13 карт пиковой масти, 13 треф, 13 бубен и 13 червей. Сколькими способами можно сдать одному игроку 5 пик, 4 черви, 2 трефы и 2 пики? (Ответ записать в виде произведения сомножителей, не вычисляя его.)
8.Сколькими способами из пяти супружеских пар можно отобрать четырех человек, если:
(а) в число отобранных должны входить двое мужчин и две женщины;
(б) никакая супружеская пара не должна входить в это число?
IV. Для решения следующих задач используйте формулы для перестановок и сочетаний
1.Сколькими способами некто может выбрать три подарка из десяти различных предметов?
2.Сколькими способами можно распределить 15 различных предметов между тремя лицами, обозначенными А, В и С, если Адолжен получить 2 предмета, B— 3 предмета и С— 10 предметов?
3.Сколько четырехбуквенных слов можно образовать из букв слова сапфир? Сколько среди них таких, которые не содержат буквы р? Сколько таких, которые начинаются с буквы с и оканчиваются буквой р?
4.Сколько пятибуквенных слов, каждое из которых состоит из трех согласных и двух гласных, можно образовать из букв русского алфавита, составляющих слово уравнение?
5.Сколько слов, состоящих из двух гласных и двух согласных, можно образовать из букв слова функция?
6.Для участия в команде тренер отбирает 5 мальчиков из десяти. Сколькими способами он может сформировать команду, если (а) два определенных мальчика должны войти в команду, (б) нет никаких ограничений?
7.В течение 10 недель студенты сдают 10 экзаменов, в том числе 2 по математике. Сколькими способами можно распределить экзамены по неделям так, чтобы экзамены по математике не следовали один за другим?
8.У филателиста есть 8 разных канадских марок и 10 разных марок США. Сколькими способами он может отобрать три канадские и три американские марки и наклеить их в альбом на шесть пронумерованных мест?
V. Для решения следующих задач используйте формулы для перестановок и сочетаний с повторениям
1.Найти число перестановок, образованных из всех букв слова комиссия.
2.Сколько различных перестановок можно образоватьизо всех букв слова перестановка? Сколько из них начинается с буквы п и оканчивается буквой а?
3.Найти число всех возможных перестановок букв слова зоология. Сколько среди них таких, в которых три буквы о стоят рядом? Сколько таких, в которых в точности две буквы о стоят рядом?
4.Найти число различных способов, которыми можно выписать в один ряд 6 плюсов и 4 минуса.
5.Сколькими способами можно расположить в один ряд три красных мяча, четыре черных мяча и три белых мяча так, чтобы мячи, лежащие на краях, были одного цвета?
СЛОВАРЬ ТЕРМИНОВ
Combinatorics | Комбинаторика |
Product rule | Принцип умножения |
Sum Rule | Принцип сложения |
Permutations | Размещение |
Combinations | Сочетание |
Arrangement | Расстановка |
Repetitions | Повторение |
Mutually exclusive | Взаимоисключающие |
The order of the articles | Порядок элементов |
Introduction
Combinatorics is the study of collections of objects. Specifically, counting objects, arrangement, derangement, etc. of objects along with their mathematical properties. Counting objects is important in order to analyze algorithms and compute discrete probabilities. Originally, combinatorics was motivated by gambling: counting configurations is essential to elementary probability.A simple example: How many arrangements are there of a deck of 52 cards? In addition, combinatorics can be used as a proof technique. A combinatorial proof is a proof method that uses counting arguments to prove a statement.
Product rule
If two events are not mutually exclusive (that is, we do them separately), then we apply the product rule.
Theorem (Product Rule)
Suppose a procedure can be accomplished with two disjoint subtasks. If there are ways of doing the first task and
ways of doing the second, then there are
ways of doing the overall procedure.
Example 1
You are trying to construct a schedule. You have 3 courses you could take at 8:30, and 2 courses you could take at 9:30. How many different possible schedules are there?
Solution
The answer is the product of 3 and 2, or 6. It is easy to see how this rule is derived, if you simply produce a diagram of the possibilities. Suppose that the available courses at 8:30 are labeled A, B, and C, and the available courses at 9:30 are D and E. You obtain 6 possible pathways, as
shown on the following picture.
Sum Rule
If two events are mutually exclusive, that is, they cannot be done at the same time, then we must apply the sum rule.
Theorem (Sum Rule)
If an event can be done in
ways and an event
can be done in
ways and
and
are mutually exclusive, then the number of ways of both events occurring is
Example
If there are 3 different courses offered in the morning and 2 different course offered in the afternoon. There will be 3 + 2 choices for a student to enroll in only one course.