Зан. 9-10. Комбинаторика
.doc
Комбинаторика – область математики, в которой изучаются различные комбинации из элементов данного множества и определяется их количество.
Комбинацией из элементов данного множества называется подмножество данного множества, имеющее заданное свойство.
Пример1. Дано множество {∆;∟;√}. 1) Составить различные двухэлементные подмножества данного множества.
Пример2. Есть 5 различных коробок конфет и 4 различные коробки с печеньем. Сколькими способами можно выбрать в подарок: а) коробку конфет или коробку печенья; 5+4=9(подарков)
б) набор из коробки конфет и коробки печенья? а+в1 а+в2 а+в3 а+в4 - 4 подарка; 4+4+4+4+4= 4 ∙5 =20 (подарков)
Правила сложения и умножения или → +
и → ∙
Правило суммы. Если некоторый объект А можно выбрать m способами, а объект В – k способами (независимо от выбора А ), то объект «А или В» можно выбрать (m+k) способами.
Задача1. Сколько существует способов выбора одного карандаша из коробки, содержащей 5 красных, 7 синих и 3 зелёных карандаша. Решение. Один карандаш, по правилу суммы, можно выбрать 5+7+3=15 способами.
Правило произведения. Если некоторый объект А можно выбрать т способами, а после каждого такого выбора другой объект В можно выбрать k способами, то пары объектов А и В можно выбрать способами.
Задача 2. Сколько существует трёхзначных чисел с разными цифрами?
Решение. В десятичной системе исчисления десять цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. На первом месте может стоять любая из девяти цифр (кроме нуля). На втором месте – любая из оставшихся 9 цифр, кроме выбранной. На последнем месте – любая из оставшихся 8 цифр. По правилу произведения, трёхзначных чисел имеют разные цифры.
Задача 3. Из-за проигрышей волейбольной команды тренер решил на каждой игре по-новому расставлять игроков. Сколько должно пройти игр, чтобы испытать все варианты?
Опр.1. Произведение п первых последовательных натуральных чисел называется п факториал. Обозначение: n! = 1 × 2 × 3 × … × n
Опр.2. Множества, отличающиеся от исходного множества, порядком расположения его элементов, называются перестановками. Обозначение: Рп
Утверждение. Число перестановок определяется по формуле Рп = n ! ( n факториал)
Задача 3. Р6=6!=1∙2∙3∙4∙5∙6=720(игр)
Опр.3. Упорядоченные т-элементные подмножества данного множества из п элементов называются размещениями из п элементов по т. Обозначение Апт ,п>m
Утверждение. Число размещений определяется по формуле Апт =п∙(п-1)∙…∙(п-(т-1)) или
(из п факториал надо убрать хвост произведения из (п-т) факториал при помощи деления)
Замечание. Апт=Рп, п=т
Задача 4 . Сколько различных трехзначных чисел можно составить из цифр 1,2,3,4,5 и 7 (без повторения цифр)
п=6 , т=3, порядок элементов в подмножестве - важен
Опр.4. Неупорядоченное т-элементное подмножество данного множества из п элементов называется сочетанием из п элементов по т. Обозначение. Сnm, п>m
Утверждение. Число сочетаний определяется по формуле
Задача 5. Из десяти студентов нужно выбрать троих для работы в приемной комиссии с абитуриентами. Сколькими способами это можно сделать?
1) п=10; 2) т=3; 3) порядок в подмножестве не важен. Вывод: сочетания. Формула:
Схема решения комбинаторных задач
Задача 6. Из 10 кандидатов нужно избрать: а) 3-х членов команды факультета для участия в университетском конкурсе «Что? Где? Когда?»; в) капитана, аналитика и интерпретатора (для презентации) для участия команды факультета в педагогической олимпиаде. Сколькими способами это можно сделать? а) С103=720/6=120 , в)А103=10∙9∙8=720
Элементы комбинаторики
-
У мамы 3 яблока и 2 груши. Каждый день она дает сыну по одному фрукту. Сколькими способами это можно сделать в первый день?, за 5 дней?
-
В турнире участвуют 5 человек. Сколькими способами могут распределиться места между ними?
-
Сколько способов рассадки 12-ти гостей за круглым столом?, на каруселе?
-
Из цифр 1,2,3,4,5 составлены 5-тизначные числа, не кратные 5, не содержащие одинаковых цифр. Сколько существует таких чисел?
-
30 книг: 27 книг различных авторов и 3-хтомник одного автора, помещены на одной полке. Сколькими способами можно расставить книги на полке так, чтобы книги одного автора стояли вместе?
-
Сколькими способами из 40 учеников класса можно выделить актив в следующем составе: староста, учебный сектор, редактор стенгазеты?
-
В шахматном турнире участвуют 5 школьников и 15 студентов. Сколькими способами могут распределяться места, занятые в турнире школьниками, если известно, что никакие 2 участника не набрали одинакового количества очков?
-
Четверо студентов сдают экзамен. Сколькими способами им могут быть поставлены отметки, если известно, что никто из них не получит неудовлетворительную оценку?
-
Сколькими способами можно выбрать 3 ленты разных цветов из 5-ти лент разных цветов?
-
В шахматном турнире принимают участие 12 шахматистов. Сколько будет сыграно партий, если любые два участника встретятся между собой только один раз?
-
На шахматном турнире, проводившемся в один круг, была сыграна 91 партия. Сколько участников было на турнире?
-
Из отряда солдат в 40 человек, среди которых есть рядовой Иванов, назначаются в караул 3 человека. Сколькими способами может быть составлен караул? В скольких случаях в число караульных попадёт рядовой Иванов?
-
Из города А в город В ведет 5 дорог, а из В в С – три дороги. Сколько путей, проходящих через В, ведет из А в С?
-
Сколькими способами можно из 15 солдат и 4 офицеров назначить в патруль трех солдат и одного офицера?
-
На железной дороге 25 станций. На каждом билете печатаются станция отправления и станция назначения. Сколько всего различных билетов нужно оформить, если: а) каждый билет действителен только в указанном направлении; б) каждый билет годен либо на поездку «туда», либо на поездку «обратно»?
-
В некоторой стране номера автомобилей состоят из двух букв, за которыми следуют две цифры, например АВ-53. Сколько различных номеров можно составить, если использовать 5 букв и 6 цифр (цифры и буквы в одном номере не повторяются)
-
От двух спортивных обществ, в каждом из которых по 40 фехтовальщиков, надо выделить по 3 фехтовальщика для участия в соревнованиях. Сколькими способами это можно сделать?
-
Собрание из 100 человек выбирает председателя, секретаря и трёх членов редакционной комиссии. Сколькими способами это можно сделать?
-
В кружке художественного слова занимаются 15 человек, в фортепьянном – 10, в вокальном – 13, в фотокружке – 20 человек. Сколькими способами можно составить бригаду из 4 чтецов, 3 пианистов,5 певцов и одного фотографа?
-
Для полета в космос необходимо укомплектовать следующий экипаж: командир корабля, первый помощник, второй помощник, два бортинженера и врач. Командная тройка может быть выбрана из 25 готовящихся к полету летчиков, два бортинженера – из 20 специалистов, врач – из 8 медиков. Сколькими способами можно укомплектовать экипаж?
-
Из четырёх математиков и пяти филологов требуется выбрать комиссию в составе четырёх человек при условии, что в комиссию войдёт хотя бы один математик и хоть один филолог. Сколькими способами это можно сделать?
-
Из 4 инженеров и 9 экономистов составляют комиссию, состоящую из 7 человек. Сколькими способами это можно сделать, если в комиссию должны войти хотя бы 2 инженера?
-
Сколько чётных пятизначных чисел можно образовать из цифр 0,1,2,3,4 при условии, что каждая цифра входит в число 1 раз?
-
Студенту необходимо сдать 4 экзамена за 9 дней. Сколькими способами это можно сделать, если известно, что последний экзамен он сдаёт на девятый день?
-
Известно, что в комнате студенческого общежития живут трое студентов. У них есть 4 чашки, 5 блюдец и 6 чайных ложек (все чашки, блюдца и ложки отличаются друг от друга). Сформулируйте вопрос к этому условию, чтобы получилась задача, имеющая своим решением следующую формулу:
-
У дизайнера имеется 5 различных стульев и 7 рулонов обивочной ткани различных цветов. Сколькими способами он может осуществить обивку стульев, если каждый стул декорируется только одним цветом ткани?
-
Из состава конференции, на которой присутствуют 52 человека, надо избрать президиум в составе 5 человек и делегацию в составе трех человек. Сколькими способами может быть произведен выбор, если члены президиума могут войти в состав делегации? А если не могут?
-
Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт есть хотя бы 1 туз? Ровно 1 туз?
-
Сколько нечетных и сколько четных четырехзначных чисел можно составить из цифр числа 3694, если каждую цифру надо использовать один раз.
-
На первые две линии произвольным образом ставятся белые и черные фигуры (король и ферзь каждого цвета, по 2 ладьи, 2 слона, 2 коня). Сколькими способами это можно сделать? А если расставлять на всей доске? А если расставлять и все пешки?
-
На званый вечер приглашены 5 мужчин и 5 женщин. Напротив каждого места на стол необходимо поставить табличку с именем того, кто будет на этом месте сидеть, но никакие два лица одного пола не должны сидеть рядом. Сколькими способами можно расставить таблички?