4 ложки 5 блюдец 6 ложек сколькими способами
Допустим, мы выбираем все n элементов из множества, содержащего n элементов, упорядоченным образом. Такие размещения n элементов называются перестановками n элементов . Число перестановок n элементов обозначается через P n .
Утверждение. P n = n !, где n! = 1·2·…·n — произведение всех натуральных чисел от 1 до n (читается «эн факториал»).
Доказательство. Будем строить произвольную перестановку n элементов. На первое место мы можем поставить любой из n элементов. После того, как первый элемент выбран, остается ( n -1) способ выбрать второй элемент из оставшихся. Для каждого способа выбрать первый и второй элементы есть ( n -2) способа выбрать третий элемент, и так далее. Если уже выбран ( n -1) элемент перестановки, остается единственный способ выбрать последний элемент. Таким образом, чтобы посчитать количество возможных перестановок n элементов, нужно все эти числа перемножить: P n = n ·( n -1)·( n -2)·…·2· 1 = n! . Утверждение доказано.
II. Размещения из n элементов по k
1. Пусть у нас есть множество из n элементов, из которых мы хотим выбрать упорядоченные k различных элементов (то есть выбрать первый элемент, второй элемент и так далее вплоть до k -го). Каждый способ это сделать называется размещением без повторений . Способы считаются различными, если хотя бы на одном месте в них стоят различные элементы. Число таких способов называется числом размещений без повторений и обозначается A n k (читается: «а из эн по ка»).
Утверждение.
| A n k | = | n ·( n -1)·…·( n — k +1) | = | n! |
| ( n — k ) ! |
Следствие. P n = A n n .
2. Число способов выбрать упорядоченные k элементов из n , если им разрешено повторяться, называется числом размещений с повторениями и обозначается как A n k . Формула для его нахождения приводится в ответе к задаче 3.7.
III. Сочетания из n элементов по k
1. Мы выбираем из n элементов неупорядоченные k различных элементов. Каждый способ это сделать называется сочетанием из n элементов по k . Различные сочетания отличаются друг от друга составом, но не порядком элементов. Число сочетаний из n элементов по k (нетрудно заметить, что это в точности число подмножеств из k элементов в множестве из n элементов) обозначается C n k . Формула для его нахождения приведена в задаче 4.2.
2. Допустим, что у нас есть n различных типов элементов. Тогда комбинация из k элементов, при условии, что элементы одного типа могут встречаться несколько раз и порядок элементов в комбинации не важен, называется сочетанием с повторениями из n элементов по k . Число сочетаний с повторениями обозначается C n k . Формула для его нахождения приведена в задаче 4.6.
Задачи занятия №3
Размещения
а) У туриста есть пять способов подняться на гору. Для каждого из этих способов существует по пять возможностей спуститься вниз. Соответственно, способов подняться на гору, а затем спуститься с нее, существует ровно 5·5 = 25.
б) В отличие от пункта а, теперь для каждого из пяти способов подняться на гору есть лишь по четыре возможности спуститься: по той же дороге, по которой турист поднимался, спускаться уже нельзя. Так что в этом случае есть 5·4 = 20 возможных маршрутов.
a) Выбрать капитана можно четырьмя способами. При каждом из четырех способов выбора капитана есть по три способа выбрать первого помощника из оставшихся пиратов. А при каждом способе выбора капитана и помощника выбрать боцмана можно двумя способами. Поэтому всего возможностей распределить должности будет 4·3·2=24.
b) Решение аналогично решению пункта а. 6·5·4=120.
с) Решение аналогично решению двух предыдущих пунктов. Вычислять произведение чисел 20·19·18·17 проще всего так: 20·19·18·17 = (20·18)·(18-1)·(18+1) = 360·(18²-1) = 360·(324-1) = 360·323 = 116280 (здесь мы пользовались формулой для разности квадратов). Последнее умножение в этой цепочке можно проделать в столбик, а можно продолжить преобразования и привести выражение к такому виду, чтобы все действия можно было выполнить в уме (попробуйте проделать это самостоятельно). Вычислить 18² можно при помощи формулы для квадрата суммы: 18² = (20-2)² = 20²-2·20·2+2² = 400-80+4 = 324.
Пронумеруем лузы числами от 1 до 6. Составим таблицу: в ячейках верхней строки будем по порядку писать номера шаров от 1 до 15, а в k -й ячейке нижней строки — номер лузы, в которую попал k -й шар. Количество способов распределения шаров по лузам совпадает с количеством способов заполнить нижнюю строку такой таблицы.
Посчитаем это количество. Отметим, что в каждой ячейке нижней строки нашей таблицы может стоять любой номер от 1 до 6 (каждый из шаров может попасть в любую лузу). Поэтому число способов ее заполнить равно 6·6·…·6 = 6 15 (произведение состоит из 15 сомножителей).
Точное значение числа 6 15 находить не обязательно, но можно вычислить, что оно равно 470184984576. Попробуйте это сделать, используя умножение не более шести раз. Все действия выполняйте в уме или в столбик: калькулятором пользоваться запрещается!
Сначала выберем черное поле. Как известно, на шахматной доске 8·8=64 клетки, и ровно половина из них черные. Значит, выбрать черное поле можно 32 способами.
В каждой вертикали и в каждой горизонтали есть по четыре белые клетки. Значит, на одной вертикали или на одной горизонтали с любой выбранной черной клеткой лежат 8 белых клеток. Так как всего белых клеток на доске 32, то не лежащих на одной горизонтали или вертикали с нашей черной клеткой среди них будет 32-8 = 24. Тем самым есть 32 способа выбрать черную клетку, и для каждого из этих способов по 24 возможности выбрать белую клетку. Значит, всего возможностей выбрать пару разноцветных клеток, не лежащих на одной горизонтали или вертикали, будет 32·24 = 768.
Перестановки
a) Ясно, что искомые числа состоят из цифр 1, 2, 3, 4, 5, расставленных в разном порядке. Значит, количество таких чисел равно количеству способов упорядочить множество из пяти цифр. На первое место можно поставить любую цифру от 1 до 5. После того как первая цифра выбрана, вторую можно выбрать четырьмя способами. Когда выбраны первая и вторая цифры, третью можно выбрать тремя способами, и так далее. Значит, всего искомых чисел 5·4·3·2·1 = 5! = 120 (сравните с пунктом I «Теоретических сведений»).
b) Здесь, в отличие от пункта а, на первое место можно поставить не любую цифру: число не может начинаться с нуля. Поэтому на первом месте может стоять любая из четырех, а не пяти, цифр. Дальнейшие рассуждения полностью аналогичны предыдущим. Так что всего искомых чисел будет 4·4·3·2·1 = 96.
Задачи занятия №4
Сочетания без повторений
a) Выбрать пять человек из шести — все равно, что выбрать одного, которого в команду не возьмут. А выбрать одного человека из шести, очевидно, можно шестью способами.
b) Аналогично предыдущему, выбрать пять человек из семи — все равно, что выбрать двух. Первого человека можно выбрать 7 способами, а второго после этого — шестью. То есть если важно, кто первый, а кто второй, число способов это сделать равно 7·6 = 42. Но одну и ту же пару человек можно упорядочить двумя способами. Значит, число неупорядоченных пар, выбранных из семи человек, равно 42:2 = 21.
c) Набрать две команды по пять человек из десяти претендентов — все равно что набрать одну команду, а из остальных претендентов составить другую. Посчитаем число способов выбрать пять человек из 10. Если порядок важен, то есть 10·9·8·7·6 способов это сделать. Но существует 5! = 120 способов упорядочить 5 человек (вспомните задачу 3.10 а). Так что каждому способу выбрать 5 человек неупорядоченным образом соответствует 120 способов выбрать их упорядоченным образом. Значит, количество способов набрать команду из пяти человек в 120 раз меньше, чем 10·9·8·7·6. А это, как нетрудно посчитать, есть в точности 252.
4.2. Проверьте формулу
| C n k | = | A n k | = | n! | . |
| k! | ( n — k ) ! k! |
Второе равенство в этой формуле следует из формулы для A n k , приведенной в «Теоретических сведениях». Докажем первое равенство. Заметим, что для каждой неупорядоченной выборки из k элементов существует k! способов ее упорядочить (вспомните утверждение из п. I «Теоретических сведений»). То есть каждой неупорядоченной выборке из k элементов соответствуют k! различных упорядоченных выборок того же объема (то есть с тем же количеством элементов).
Упорядоченные выборки, полученные из разных неупорядоченных выборок, различны (хотя бы потому, что состоят из различных элементов). Каждую упорядоченную выборку можно получить из какой-то неупорядоченной (а именно той, которая состоит из элементов интересующей нас упорядоченной). Тем самым доказано, что упорядоченных выборок из k элементов ровно в k! раз больше, чем неупорядоченных выборок того же объема. Это и доказывает первое равенство в приведенной формуле.
Сначала подсчитаем количество точек пересечения этих прямых. Общность положения означает, что любые две прямые пересекаются ровно в одной точке. То есть на каждой прямой лежит ( n -1) точка пересечения. Всего точек будет n · ( n − 1) / 2 , так как прямых n штук, и каждую точку мы считаем два раза — по одному разу для каждой прямой, на которой она лежит (вспомните, к примеру, задачу №5 Занятия 1).
Теперь заметим, что количество трегольников со сторонами на этих прямых в точности равно числу способов выбрать три точки из n · ( n − 1) / 2 неупорядоченным образом. Действительно, любые три точки пересечения наших прямых служат вершинами треугольника, так как любые две точки соединены прямой (в силу общности положения прямых). Наоборот, любой треугольник со сторонами на наших прямых будет иметь вершины в точках пересечения прямых. Поэтому число таких треугольников равно C 3 n · ( n − 1) / 2 .
a) Чтобы расставить восемь ладей на доске, нужно выбрать восемь полей из 64, на которых ладьи будут стоять. Поскольку ладьи друг от друга не отличаются, порядок выбора этих полей неважен. Значит, искомое число равно С 8 64 .
b) Этот случай отличается от предыдущего тем, что все фигуры различны между собой, и значит, важен порядок выбора полей. Искомое число способов, тем самым, равно A 8 64 .
Сочетания с повторениям
Пусть пирожки разных типов разложены на пяти лотках. Когда мы покупаем пирожки, мы действуем так: сначала берем сколько-то пирожков с картошкой (может быть, ни одного), затем переходим к лотку с пирожками с капустой и берем сколько-то пирожков оттуда, и так далее до тех пор, пока не наберем восемь пирожков.
Последовательность наших действий при этом можно описать так. Запишем в ряд восемь единиц. Отсчитаем от начала столько единиц, сколько пирожков с картошкой мы взяли, и поставим после них вертикальную черту. В частности, если мы не взяли ни одного пирожка с картошкой, поставим черту перед первой единицей, а если мы их взяли сразу восемь, поставим ее после последней единицы. Далее проделаем то же самое по отношению к пирожкам с капустой, с мясом, с рисом и с яблоком. Если в какой-то момент мы наберем восемь пирожков, а до последнего лотка еще не дойдем, оставшиеся вертикальные черточки будем в нужном количестве ставить после последней единицы. Если, наоборот, мы ничего не возьмем с первых нескольких лотков, черточки будем ставить перед первой единицей.
Всего в нашей записи будет 8 единиц и четыре вертикальные черты, то есть 12 символов. Чтобы получить произвольную запись такого вида, нужно выбрать 8 позиций из 12, на которые мы поставим единицы, а на остальные позиции поставить вертикальные черточки. Тем самым количество возможных способов купить восемь пирожков равно C 8 12 = 495 (примените формулу из задачи 4.2).
Применим принцип, использованный в предыдущих задачах. Сначала распределим по лифтам пятиклассников, потом шестиклассников, затем семиклассников и наконец, восьмиклассников.
Присвоим лифтам номера от 1 до 5. Каждый способ распределить по лифтам пятиклассников будем записывать так: сначала пишем в ряд столько единиц, сколько пятитклассников посадим в первый лифт, затем ставим вертикальную черту и пишем еще столько единиц, сколько пятитклассников посадим во второй лифт, и так далее. Число таких записей равно числу способов распределить по лифтам пятиклассников и равно в точности C 4 14 (вспомните предыдущие задачи). Для шестиклассников аналогичным образом получим C 4 15 способов, для семиклассников C 4 12 и наконец, для восьмиклассников C 4 16 способов. Теперь все эти числа надо перемножить.
Замечание. При решении этой задачи мы фактически заново доказывали формулу для C n k . Решите эту задачу другим способом, непосредственно применяя эту формулу.
Разные задачи
При решении задачи 3.11 мы подсчитали, что число кодов, состоящих из не более чем четырех символов азбуки Морзе, равно 30. Среди этих кодов есть только два, которые используют более трех однотипных символов: это, соответсвенно, код из четырех точек и код из четырех тире. Все остальные коды нам подходят. Тем самым у нас уже есть 28 «хороших» кодов. Осталось придумать еще пять кодов, удовлетворяющих нашим требованиям. Например, таких: — — — · ·, · — — — ·, · — · — ·,— · — · —, — — — · · ·. Теперь у нас есть 33 «хороших» кода, и мы можем ими зашифровать весь русский алфавит.
Попробуйте самостоятельно сосчитать количество всех «хороших» кодов. Хватит ли их, чтобы зашифровать сначала русские буквы, а потом латинские? А цифры?
a) Число треугольников с вершинами в этих точках равно числу способов выбрать две точки на одной прямой и одну — на другой. При этом пару точек, лежащих на одной из прямых, нужно выбирать неупорядченным образом: при их перестановке треугольник не изменится. Если одну вершину выбирать на первой прямой, а еще две на второй, то получится 10·C 11 2 = 550 различных треугольников (10 способов выбрать вершину на первой прямой и C 10 2 = 55 способов выбрать две вершины на второй прямой). Аналогично найдем, что если на первой прямой брать две вершины, а на второй — только одну, получится 11·C 10 2 = 495 различных треугольников. Значит, всего треугольников с вершинами в отмеченных точках существует 550+495 = 1045.
b) Для построения четырехугольника надо выбрать по две точки на каждой прямой (иначе получится не четырехугольник, а треугольник или даже отрезок). При этом та точка, которая лежит левее на первой прямой, будет соединяться стороной с точкой, лежащей левее на второй прямой (и то же самое касается точек, которые лежат правее), иначе получится фигура, которую мы четырехугольником не считаем (попробуйте нарисовать такую фигуру). Поэтому пары точек на каждой прямой надо выбирать неупордоченным образом, а затем вершины соединять вышеуказанным способом. Всего есть C 10 2 = 45 способов выбрать пару точек на первой прямой и C 11 2 = 55 способов выбрать пару точек на второй прямой. Количество искомых четырехугольников равно произведению этих чисел, а именно 2475.
Выберем какого-нибудь человека из нашей компании (назовем его А). Тогда в компании либо есть трое, которые с ним знакомы, либо трое, которые с ним незнакомы. Этих троих назовем Б, В, Г.
Пусть сначала Б, В, Г знакомы с А. Если среди них есть двое знакомых друг с другом, то эти двое и А знакомы между собой, и утверждение задачи выполнено. Если же среди них нет знакомых, то они и есть те трое, которые друг с другом не знакомы, и утверждение вновь выполнено. Случай, когда Б, В и Г не знакомы с А, рассматривается точно так же, только слова «знакомы» и «не знакомы» меняются местами.
Источник
