Сколько существует перестановок букв слова фигура

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

В перестановках с повторениями, как и в «обычных» перестановках, участвует сразу всё множество объектов, но есть одно но: в данном множестве один или бОльшее количество элементов (объектов) повторяются. Встречайте очередной стандарт:

Задача 10
Сколько различных слов (не обязательно осмысленных) можно получить перестановкой карточек со следующими буквами: К, О, Л, О, К, О, Л, Ь, Ч, И, К?

Решение: поскольку среди букв есть одинаковые, то формула не годится, так как учитывает «холостые» перестановки (например, двух карточек с буквами «к», при этом форма самих карточек и размеры букв не имеют значения). Поэтому здесь имеют место перестановки с повторениями, и осталось выполнить бесхитростные подсчёты – всего у нас 11 карточек, среди которых буква:

К – повторяется 3 раза;
О – повторяется 3 раза;
Л – повторяется 2 раза;
Ь – повторяется 1 раз;
Ч – повторяется 1 раз;
И – повторяется 1 раз.

Контроль: 3 + 3 + 2 + 1 + 1 + 1 = 11, что и требовалось проверить.

По формуле количества перестановок с повторениями:
различных слов (буквосочетаний) можно получить. Больше полумиллиона

На практике вполне допустимо не записывать общую формулу и, кроме того, опускать единичные факториалы, то есть в компактном виде решение оформляется так:

Но предварительные комментарии о повторяющихся буквах обязательны!

Ответ: 554400

Другой типовой пример для самостоятельного решения:

Задача 11
Сколькими способами можно расставить белые фигуры (2 коня, 2 слона, 2 ладьи, 1 ферзь, 1 король) на первой линии (8 клеток) шахматной доски?

Коротенькое решение в конце книги.

Полную и свежую версию этой книги в pdf-формате ,
а также курсы по другим темам можно найти после Оглавления.

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

С наилучшими пожеланиями, Александр Емелин

© mathprofi.ru — mathter.pro, 2010-2024, сделано в Блокноте.

Сколько существует перестановок букв слова фигура

Дополнительные задания давались на обоих занятиях по комбинаторике. Не смотря на название и кажущуюся однообразность, пункты этих задач содержат в себе некоторый новый материал. 11. Сколько наборов букв можно получить перестановкой из следующих слов:

а) КОТ;	г) МАМА;
б) ДЕД;	д) АУУУ;
в) БРАТ;	е) УКУШУ.

а) 6	г) 6
б) 3	д) 4
в) 24	е) 20

Решение. а) Все буквы разные, поэтому будет 3! = 6 вариантов их перестановки.
б) Букву Е можно поставить на одно из 3 мест, на остальных будут буквы Д, так что вариант перестановки полностью задаётся положением буквы Е, которых 3 штуки.
в) Все буквы разные, значит, 4! = 24 вариантов.
г) Будем рассуждать так же, как и когда поняли, почему надо использовать факториал для подсчёта числа перестановок. Первую букву М можно поставить на одно из 4 мест. Для каждого из этих 4 вариантов вторую букву М можно поставить на одно из оставшихся 3 мест. Для каждого из 3 · 4 = 12 этих вариантов положение букв А будет задано однозначно. Однако, поскольку буквы М на самом деле ничем не отличаются друг от друга, то каждый вариант расстановки оказался посчитан 2 раза: например, когда первая М на 1м месте, вторая М на 2м, то это не должно отличаться от варианта, когда первая М на 2м месте, а вторая — на 1м. Значит, посчитанное число нужно разделить на 2. Всего вариантов будет 12 : 2 = 6.
д) Вся расстановка полностью определяется положением буквы А, поэтому всего вариантов столько же, на сколько мест её можно поставить, то есть 4.
е) Вариант определяется положением букв К и Ш. Есть 5 способов разместить букву К, для каждого из которых букву Ш можно поставить на одно из 4 мест, оставшихся свободными, то есть всего вариантов 5 · 4 = 20.

12. Сколько наборов букв можно получить перестановкой из следующих слов (в этой задаче факториалы от больших чисел можно оставить в ответе не посчитанными):

а) ЛЕС;	д) СЕСТРА;	и) ЗЕЛЕНОШЕЕЕ;
б) МАРТ;	е) ПАПА;	к) БИССЕКТРИСА;
в) ВЕСНА;	ж) ФАКТОРИАЛ;	л) МИКАНОТИКРОБА;
г) АПРЕЛЬ;	з) ПАРАБОЛА;	м) КОМБИНАТОРИКА.

а) 6;	д) 360;	и) 10! : 5! = 30240;
б) 24;	е) 6;	к) 11!: 2! : 3! = 11! : 12;
в) 120;	ж) 9! : 2;	л) 13! : 2 : 2 : 2 : 2 = 13! : 16;
г) 720;	з) 8! : 3! = 6720;	м) 13! : 2 : 2 : 2 : 2 = 13! : 16.

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

В следующих полезно сначала предположить, что все буквы разные. После этого заметим, что при перестановке одинаковых букв местами между собой получаются внешне одинаковые варианты, которые должны быть посчитаны за один и тот же. Например, количество способов переставить две буквы местами равно 2! = 2, так что если в слове было 2 одинаковых буквы, то каждый внешне различимый вариант оказался посчитан нами 2 раза как 2 варианта, отличающиеся перестановкой этих букв местами (когда мы считали все буквы отличающимися друг от друга).

Если было 3 одинаковых буквы (как в пункте з) ), то при фиксированных остальных буквах одинаковые буквы можно переставить местами 3! способами, а внешне все эти перестановки будут выглядеть одинаково и потому должны быть посчитаны за один и тот же вариант. В таком случае каждый вариант оказался посчитан 3! раз, то есть всего вариантов будет 6! : 3! = 6! : 6 = 5! = 120.

Аналогично, в пункте и) всего будет
\(\frac = \frac = 6 · 7 · . · 10 = 30240\) вариантов.

В пункте к) в слове БИССЕКТРИСА есть две группы повторяющихся букв. Поступим так же, как и прежде: сначала считаем, что все буквы разные, затем учтём, что есть несколько одинаковых букв одной группы, например, С, а затем и другой, И. В итоге получим 11! : 3! : 2! вариантов. То есть, за каждую группу одинаковых букв мы делим факториал от длины слова на факториал длины этой группы.

13. Сколько наборов букв можно получить перестановкой из следующих слов:

а) ААУ;	д) ААААУУ;	и) АУ. У (\(k\) букв У);
б) АУУ;	е) ААУУУУ;	к) ААУ. У (\(k\) букв У);
в) АААУУ;	ж) АААУУУУУ;	л) А. АУ. У (\(k\) букв А, \(n-k\) букв У);
г) ААУУУ;	з) АААААУУУ;	м) А. АУ. У (\(k\) букв У, \(n-k\) букв А).

а) 3;	д) 15;	и) \(k + 1\);
б) 3;	е) 15;	к) \((k+2)(k+1)/2\);
в) 10;	ж) 56;	л) \(n! : k! : (n-k)!\);
г) 10;	з) 56;	м) \(n! : k! : (n-k)!\).

Указание. в) Первая буква У может стоять на одном из 5 мест. Для каждого из этих вариантов будет 4 возможных места для второй буквы У. Расстановка обоих букв У однозначно задаёт вариант, так как всё остальное будет заполнено буквами А. При этом, так как буквы У неотличимы, то есть 2! способов поменять их местами, получая один и тот же набор, то есть каждый набор оказался посчитан 2! = 2 раза. Поэтому всего вариантов будет 5 · 4 : 2 = 5 · 2 = 10.
и) Буква А может стоять на одном из \(k + 1\) мест, а остальные обязательно будут заполнены буквами У, так что данная расстановка определяется только положением буквы А.
к) Всего мест \(k + 2\), при этом расстановка определяется только положением букв А. Сначала считаем, что две буквы А отличаются друг от друга, а затем учтём, что варианты, отличающиеся только перестановкой букв А между собой, внешне неотличимы и потому должны быть посчитаны за один.

14. Сколькими способами можно:
а) из 5 ребят выбрать двоих;
б) из 6 ребят выбрать четверых;
в) из 7 ребят выбрать троих;
г) из \(n\) ребят выбрать \(k\)?

Решение. a) Так же, как и с буквами: выбрать первого можно 5 способами, второго — 4 способов, и при этом каждый вариант оказался посчитан 2! раз, так как порядок выбирания на самом деле неважен. Итого 5 · 4 : 2 = 5 · 2 = 10 способов.
б) 15 (выбрать 4 из 6 — то же, что выбрать двоих для невыбирания, а таких способов 6 · 5 : 2!)
в) 7·6·5:3! = 7·6·5:6 = 7·5 = 35
г) \(\frac\)

Последний пункт позволяет объединить следующие два способа решения задач.

При последовательном выборе есть \(n\) способов выбрать первого, при выбранном первом выбрать второго можно \(n-1\) способами, дальше третьего — \(n-2\) способами, . \(k\)-того — \(n-(k-1) = n-k+1\) способами. При этом каждый реальный вариант выбора был посчитан \(k!\) раз, так как порядок выбирания не важен, а одну и ту же группу людей можно выбирать в разном порядке именно \(k!\) способами (\(k\) способов кого-то из выбранных выбрать первым, \(k-1\) — вторым, \(k-2\) — третьим и так далее). Итого получаем
\((n \cdot (n-1) \cdot (n-2) \cdot . \cdot (n-k+1)) : k! = \frac : k! = \frac : k! = \frac\)
(Умножили и разделили на одно и то же число \((n-k) \cdot (n-k-1) \cdot . \cdot 1\), чтобы произведение представить в более красивом виде — как частное двух факториалов.)

С другой стороны, выбор можно отобразить наглядно как написание конкретной последовательности из символов двух видов, например, Д и Н, где каждое место соответствует своему человеку, Д означает, что его выбрали, а Н — что нет. Количество комбинаций из \(k\) букв Д и \(n-k\) букв Н (потому что если всего \(n\) человек, и из них выбираем \(k\), то не выбранными останутся \(n-k\)) длины \(n\) было посчитано раньше и равно
\(n! : k! : (n-k)! = \frac\)

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

• ЗАДАЧИ
• 5 класс
• Плюс-минус один
• Обратный ход
• Посчитай-ка
• Скобки и знаки
• Рыцари и лжецы
• Движение
• Движение (доп. задачи)
• Факториал
• Комбинаторика (доп. задачи)
• Математическая абака
• Комбинаторика
• Козы
• Переливания
• Предновогодний Оливье
• Математическая карусель
• Всюду идут дороги
• Разные задачи
• Разрезалки
• Круги Эйлера
• Принцесса или тигр
• Магические фигуры
• Двумя способами
• Конструкции
• ЗАДАЧИ
• ауд. П3 (рук. Л. А. Попов)

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter!

Сколько существует перестановок букв слова фигура

Допустим, мы выбираем все 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 ) !

Докажите это утверждение самостоятельно по аналогии с предыдущим. Его доказательство в частном случае фактически проводится при решении задачи 3.2.
Следствие. 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

Размещения

3.1. На вершину горы ведут пять тропинок. a) Сколько у туриста есть способов подняться на гору и потом спуститься с нее? b) А если турист не хочет спускаться по той же дороге, по которой он поднимался?

а) У туриста есть пять способов подняться на гору. Для каждого из этих способов существует по пять возможностей спуститься вниз. Соответственно, способов подняться на гору, а затем спуститься с нее, существует ровно 5·5 = 25.

б) В отличие от пункта а, теперь для каждого из пяти способов подняться на гору есть лишь по четыре возможности спуститься: по той же дороге, по которой турист поднимался, спускаться уже нельзя. Так что в этом случае есть 5·4 = 20 возможных маршрутов.

3.2. Пираты подняли бунт и захватили корабль. Теперь им нужно выбрать из своих рядов капитана, его первого помощника и боцмана. Сколькими способами они могут это сделать, если пиратов: а) 4 b) 6 c) 20 и им ещё нужно выбрать кока?

Ответ. a) 24; b) 120; c) 116280.

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.

3.3. Сколькими способами 15 пронумерованных бильярдных шаров могут распределиться по шести лузам?
Ответ. 6 15 = 470184984576.

Пронумеруем лузы числами от 1 до 6. Составим таблицу: в ячейках верхней строки будем по порядку писать номера шаров от 1 до 15, а в k -й ячейке нижней строки — номер лузы, в которую попал k -й шар. Количество способов распределения шаров по лузам совпадает с количеством способов заполнить нижнюю строку такой таблицы.

Посчитаем это количество. Отметим, что в каждой ячейке нижней строки нашей таблицы может стоять любой номер от 1 до 6 (каждый из шаров может попасть в любую лузу). Поэтому число способов ее заполнить равно 6·6·…·6 = 6 15 (произведение состоит из 15 сомножителей).

Точное значение числа 6 15 находить не обязательно, но можно вычислить, что оно равно 470184984576. Попробуйте это сделать, используя умножение не более шести раз. Все действия выполняйте в уме или в столбик: калькулятором пользоваться запрещается!

3.4. В комнате студенческого общежития живут трое студентов. У них есть 4 чашки, 5 блюдец и 6 чайных ложек (все чашки, блюдца и ложки отличаются друг от друга). Сколькими способами они могут накрыть стол для чаепития (то есть дать каждому студенту чашку, блюдце и ложку)?

Ответ. (4·3·2)·(5·4·3)·(6·5·4) = 172800.

Решение. Сначала отдельно посчитаем количество способов раздать студентам чашки, количество способов раздать им блюдца и количество способов раздать им чайные ложки. Например, количество способов раздать блюдца равно числу размещений без повторений четырех элементов из пяти A 5 4 (см. «Теоретические сведения»). А оно равно 5·4·3 = 60 (подумайте почему; вспомните решение задачи 3.2). Аналогично вычисляются и два других числа способов: они будут равны, соответсвенно, 24 и 120. А теперь все полученные числа надо перемножить: 24·60·120 = 172800. Ведь раздача чашек, раздача блюдец и раздача ложек производятся независимо друг от друга. Постарайтесь произвести вычисления без калькулятора, выполняя умножение в столбик не более одного раза (а все остальное проделывая в уме).

3.5. Сколькими способами можно выбрать на шахматной доске белое и черное поля, не лежащие на одной горизонтали или вертикали?

Ответ. 768 способами.

Сначала выберем черное поле. Как известно, на шахматной доске 8·8=64 клетки, и ровно половина из них черные. Значит, выбрать черное поле можно 32 способами.

В каждой вертикали и в каждой горизонтали есть по четыре белые клетки. Значит, на одной вертикали или на одной горизонтали с любой выбранной черной клеткой лежат 8 белых клеток. Так как всего белых клеток на доске 32, то не лежащих на одной горизонтали или вертикали с нашей черной клеткой среди них будет 32-8 = 24. Тем самым есть 32 способа выбрать черную клетку, и для каждого из этих способов по 24 возможности выбрать белую клетку. Значит, всего возможностей выбрать пару разноцветных клеток, не лежащих на одной горизонтали или вертикали, будет 32·24 = 768.

3.6. Четверо студентов сдавали экзамен. a) Сколькими способами им могли быть выставлены оценки, если известно, что все студенты экзамен сдали (то есть получили 3, 4 или 5)? b) А если студентов было 10?

Ответ. a) 3 4 = 81; b) 3 10 = 59049.

Решение. Решение этой задачи аналогично решению задачи 3.3. Число способов выставить студентам оценки равно числу способов поставить напротив каждой фамилии в ведомости оценку 3, 4 или 5. В пункте b) попробуйте проделать вычисления, пользуясь умножением лишь четыре раза и выполнив в столбик лишь одно из них.

3.7. Выведите формулу для нахождения A n k .
Ответ. A n k = n k .

Решение. Эта формула фактически доказана в частном случае при решении задачи 3.3. Если в условии той задачи взять k шаров и n луз и решать ее так же, как мы это делали в частном случае, как раз и получится результат, приведенный в ответе.

3.8. Сколько слов (не обязательно осмысленных: «ьщерук» тоже считается словом), состоящих из а) трех b) пяти c) семи букв, можно составить из тридцати трех букв русского алфавита так, чтобы любые две стоящие рядом буквы были различны?

Ответ. a) 33·32·32 = 33792; b) 33·32 4 = 34603008; c) 33·32 6 = 35433480192.

Решение. Первую букву слова можно выбрать 33 способами. Когда первая буква выбрана, вторая должна быть отлична от нее. Значит, вторую букву можно выбрать лишь 32 способами. По той же причине третью и каждую из последующих букв (если надо) можно выбрать 32 способами. Так что для слова из трех букв имеем 33·32·32 = 33792 возможности, для слова из пяти букв их будет 33·32 4 = 34603008, а для слова из семи букв получим 33·32 6 = 35433480192 (точные значения находить не обязательно).

3.9. Сколько можно составить из тридцати трех букв русского алфавита шестибуквенных слов, содержащих хотя бы одну букву «а»?

Ответ. 33 6 — 32 6 = 217726145.

Решение. Сначала сосчитаем все возможные шестибуквенные слова (разумеется, неосмысленные тоже будет считать). Таких слов бывает 33 6 (сравните с задачей №7). Теперь сосчитаем те слова, в которых вообще нет буквы «а». В них на каждом месте может стоять любая из 32 букв (все буквы, кроме буквы «а»). Значит, таких слов всего 32 6 . Остальные слова содержат хоть одну букву«а», и их количество равно 33 6 — 32 6 = 217726145. Вычисления можно сразу проводить в столбик, а можно сначала упростить выражение с помощью формул сокращенного умножения.

Перестановки

3.10. Сколько пятизначных чисел содержат все цифры а) 1, 2, 3, 4, 5? b) 0, 2, 4, 6, 8?
Ответ. а) 120; b) 96.

a) Ясно, что искомые числа состоят из цифр 1, 2, 3, 4, 5, расставленных в разном порядке. Значит, количество таких чисел равно количеству способов упорядочить множество из пяти цифр. На первое место можно поставить любую цифру от 1 до 5. После того как первая цифра выбрана, вторую можно выбрать четырьмя способами. Когда выбраны первая и вторая цифры, третью можно выбрать тремя способами, и так далее. Значит, всего искомых чисел 5·4·3·2·1 = 5! = 120 (сравните с пунктом I «Теоретических сведений»).

b) Здесь, в отличие от пункта а, на первое место можно поставить не любую цифру: число не может начинаться с нуля. Поэтому на первом месте может стоять любая из четырех, а не пяти, цифр. Дальнейшие рассуждения полностью аналогичны предыдущим. Так что всего искомых чисел будет 4·4·3·2·1 = 96.

3.11. В азбуке Морзе используются два типа символов: точки (·) и тире (—). Можно ли сопоставить каждой букве русского алфавита такой код, чтобы каждая буква оказалась зашифрована не более чем четырьмя символами азбуки Морзе?

Решение. Посчитаем количество возможных комбинаций из четырех символов азбуки Морзе. На каждом месте в такой комбинации может стоять любой из двух символов. Значит, всего комбинаций из четырех символов будет 2·2·2·2 = 16. Но можно использовать и комбинации меньшего числа символов. Аналогично предыдущему находим, что из трех символов можно составить 2 3 = 8 комбинаций, из двух — 2·2 = 4 комбинации, а из одного символа — две комбинации. Сложив эти числа, получим 16+8+4+2 = 30 3.12. a) Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не били друг друга? b) А n ладей на доске размера n × n ?

Ответ. a) 8! = 51840; b) n! .

Решение. Чтобы ладьи не били друг друга, необходимо, чтобы на каждой вертикали и на каждой горизонтали стояла ровно одна ладья. Будем расставлять ладьи следующим образом: первую ладью ставим на первую горизонталь, вторую ладью — на вторую, и т. д., но так, чтобы они все были на разных вертикалях. То есть надо заполнить таблицу, в верхней строке которой стоят номера ладей (или, что то же самое, горизонталей) по порядку, а в нижней номера вертикалей. Число способов сделать это равно числу способов упорядочить 8 (или n ) чисел. А оно равно 8! = 51840 (или, соответственно, n! ).

3.13. Каких семизначных чисел больше: тех, в записи которых есть единица, или всех остальных?
Ответ. Чисел с единицами больше.

Решение. Проще сначала посчитать количество семизначных чисел, в которых единиц нет. В таком числе на первом месте может стоять любая цифра, кроме 0 и 1, а на всех остальных — любые цифры, кроме 1. Значит, таких чисел всего 8·9 6 . А всего семизначных чисел бывает 9·10 6 (на первом месте может стоять любая цифра, кроме нуля, а на всех остальных — любые цифры). Тем самым семизначных чисел, содеращих единицу, будет 9·10 6 − 8·9 6 . Это число надо сравнить с числом 8·9 6 . Результат сравнения будет таким же, как результат сравнения чисел 9·10 6 и 8·9 6 + 8·9 6 = 16·9 6 (убедитесь в этом сами). А результат сравнения этих чисел, в свою очередь, совпадает с результатом сравнения чисел 10 6 и 16·9 5 . Первое из этих чисел, очевидно, равно 1000000, а второе, как можно подсчитать в столбик, равно 944784. Значит, второе из первоначально сравниваемых чисел также меньше первого. Тем самым семизначных чисел, содержащих единицу, больше, чем всех остальных.

Задачи занятия №4

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

4.1. Сколькими способами можно выбрать баскетбольную команду (5 человек) из а) шести человек? b) семи человек? c) Сколько способов набрать две команды по пять человек из десяти претендентов?

Ответ. a) 6; b) 21; c) 252.

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! раз больше, чем неупорядоченных выборок того же объема. Это и доказывает первое равенство в приведенной формуле.

4.3. На плоскости провели n прямых общего положения (то есть никакие две из них не параллельны и никакие три не проходят через одну точку). Сколько получилось треугольников со сторонами на этих прямых?

Ответ. C 3 n · ( n − 1) / 2 .

Сначала подсчитаем количество точек пересечения этих прямых. Общность положения означает, что любые две прямые пересекаются ровно в одной точке. То есть на каждой прямой лежит ( n -1) точка пересечения. Всего точек будет n · ( n − 1) / 2 , так как прямых n штук, и каждую точку мы считаем два раза — по одному разу для каждой прямой, на которой она лежит (вспомните, к примеру, задачу №5 Занятия 1).

Теперь заметим, что количество трегольников со сторонами на этих прямых в точности равно числу способов выбрать три точки из n · ( n − 1) / 2 неупорядоченным образом. Действительно, любые три точки пересечения наших прямых служат вершинами треугольника, так как любые две точки соединены прямой (в силу общности положения прямых). Наоборот, любой треугольник со сторонами на наших прямых будет иметь вершины в точках пересечения прямых. Поэтому число таких треугольников равно C 3 n · ( n − 1) / 2 .

4.4. Сколькими способами можно поставить на шахматную доску а) 8 ладей? b) 4 чёрных и 4 белых фигуры: коня, слона, ладью и ферзя?

Ответ. a) С 8 64 ; b) A 8 64 .

a) Чтобы расставить восемь ладей на доске, нужно выбрать восемь полей из 64, на которых ладьи будут стоять. Поскольку ладьи друг от друга не отличаются, порядок выбора этих полей неважен. Значит, искомое число равно С 8 64 .

b) Этот случай отличается от предыдущего тем, что все фигуры различны между собой, и значит, важен порядок выбора полей. Искомое число способов, тем самым, равно A 8 64 .

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

4.5. В буфете МГУ продаются пирожки пяти типов: с картошкой, с капустой, с мясом, с рисом и с яблоком. Сколькими способами можно купить восемь пирожков?

Ответ. Это можно сделать 495 способами.

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

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

Всего в нашей записи будет 8 единиц и четыре вертикальные черты, то есть 12 символов. Чтобы получить произвольную запись такого вида, нужно выбрать 8 позиций из 12, на которые мы поставим единицы, а на остальные позиции поставить вертикальные черточки. Тем самым количество возможных способов купить восемь пирожков равно C 8 12 = 495 (примените формулу из задачи 4.2).

4.6. Покажите, что C n k = C k n+k-1 .

Решение. Проведем рассуждения аналогично тому, как мы это делали при решении предыдущей задачи. Представим, что у нас есть n корзин с элементами различных типов, и робот, который должен набрать из этих корзин k каких-нибудь элементов. Для этого он будет брать сколько-то элементов из очередной корзины, а затем двигаться к следующей корзине. Последовательность его действий опишем последовательностью из единиц и вертикальных черточек. Сначала запишем в ряд столько единиц, сколько элементов робот возьмет из первой корзины (возможно, единиц вовсе не будет), а после них поставим черту. Затем припишем после черты столько единиц, сколько элементов будет взято из второй корзины, и после них также поставим черту, и так далее. Всего в нашей записи будет k единиц и ( n -1) вертикальных черточек, то есть ( n + k -1) символ. Чтобы получить произвольную запись такого вида, нужно из ( n + k -1) позиций выбрать k позиций для единиц, а остальные позиции заполнить черточками. Количество способов сделать это равно C k n+k-1 .

4.7. Сколькими способами можно распределить 10 пятиклассников, 11 шестиклассников, 8 семиклассников и 12 восьмиклассников по пяти лифтам (считается, что лифты неограниченной вместимости, а школьники одного класса между собой не различаются)?

Ответ. C 4 14 ·C 4 15 ·C 4 12 ·C 4 16 способов.

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

Присвоим лифтам номера от 1 до 5. Каждый способ распределить по лифтам пятиклассников будем записывать так: сначала пишем в ряд столько единиц, сколько пятитклассников посадим в первый лифт, затем ставим вертикальную черту и пишем еще столько единиц, сколько пятитклассников посадим во второй лифт, и так далее. Число таких записей равно числу способов распределить по лифтам пятиклассников и равно в точности C 4 14 (вспомните предыдущие задачи). Для шестиклассников аналогичным образом получим C 4 15 способов, для семиклассников C 4 12 и наконец, для восьмиклассников C 4 16 способов. Теперь все эти числа надо перемножить.

Замечание. При решении этой задачи мы фактически заново доказывали формулу для C n k . Решите эту задачу другим способом, непосредственно применяя эту формулу.

Разные задачи

4.8. При передаче сообщений по телеграфу используется код Морзе. В этом коде буквы обозначаются набором точек и тире, причём количество используемых знаков может быть разным. Хватит ли трех точек и трех тире для того, чтобы зашифровать все русские буквы?

При решении задачи 3.11 мы подсчитали, что число кодов, состоящих из не более чем четырех символов азбуки Морзе, равно 30. Среди этих кодов есть только два, которые используют более трех однотипных символов: это, соответсвенно, код из четырех точек и код из четырех тире. Все остальные коды нам подходят. Тем самым у нас уже есть 28 «хороших» кодов. Осталось придумать еще пять кодов, удовлетворяющих нашим требованиям. Например, таких: — — — · ·, · — — — ·, · — · — ·,— · — · —, — — — · · ·. Теперь у нас есть 33 «хороших» кода, и мы можем ими зашифровать весь русский алфавит.

Попробуйте самостоятельно сосчитать количество всех «хороших» кодов. Хватит ли их, чтобы зашифровать сначала русские буквы, а потом латинские? А цифры?

4.9. На прямой отмечено 10 точек, а на параллельной ей прямой — 11 точек. Сколько существует а) треугольников, б) четырёхугольников с вершинами в этих точках?

Ответ. a) 1045; b) C 10 2 ·C 11 2 = 2475.

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.

4.10. У Мальвины шестеро друзей, и в течении пяти дней она приглашает к себе в гости каких-то трех из них так, чтобы компания ни разу не повторилась. Сколькими способами она может это сделать?

Ответ. А 20 5 = 1860480.

Решение. Сначала сосчитаем количество всевозможных различных компаний из трех человек. Оно, как нетрудно сообразить, равно С 6 3 = 20 (примените формулу из задачи 4.2 самостоятельно). Теперь из этих возможных компаний нужно (упорядоченным образом) выбрать пять, чтобы последовательно приглашать их в гости. Это можно сделать А 20 5 = 1860480 способами (примените формулу из «Теоретических сведений»).

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

Выберем какого-нибудь человека из нашей компании (назовем его А). Тогда в компании либо есть трое, которые с ним знакомы, либо трое, которые с ним незнакомы. Этих троих назовем Б, В, Г.

Пусть сначала Б, В, Г знакомы с А. Если среди них есть двое знакомых друг с другом, то эти двое и А знакомы между собой, и утверждение задачи выполнено. Если же среди них нет знакомых, то они и есть те трое, которые друг с другом не знакомы, и утверждение вновь выполнено. Случай, когда Б, В и Г не знакомы с А, рассматривается точно так же, только слова «знакомы» и «не знакомы» меняются местами.

Вы видите ошибку? Выделите её и нажмите Ctrl+Enter!

Самостоятельная работа по теме «Комбинаторика»

№1. Сколькими способами можно разместить пять различных книг на полке?

№2. Сколько трехзначных чисел с разными цифрами можно составить из цифр 0, 1, 3, 6, 7, 9?

№3. На встрече выпускников 9 бывших одноклассников обменялись визитками. Сколько было использовано визиток?

№4. Сколько существует перестановок букв слова «фигура», в которых буквы «у», «р», «а» стоят рядом в указанном порядке?

№1. Сколькими способами можно разместить шесть различных книг на полке?

№2. Сколько трехзначных чисел с разными цифрами можно составить из цифр 0, 3, 4, 5, 8?

№3. На конференции 7 ее участников обменялись номерами телефонов. Сколько было произведено обменов телефонными номерами?

№4. Сколько существует перестановок букв слова «вершина», в которых буквы «в», «е», «р» стоят рядом в указанном порядке?

Самостоятельная работа. Комбинаторика.

№1. Сколькими способами 9 участников конкурса могут выступать в порядке очередности в четверти финала конкурса?

№2. Используя цифры 0, 3, 7, 8, составьте все возможные двузначные числа, в которых цифры не повторяются.

№3. В районе N каждые два поселка соединены дорогой. Определите число таких дорог, если в районе 10 поселков.

№4. Сколько существует пятизначных телефонных номеров, начинающихся с цифры 3 , в которых все цифры различные?

№1. Курьер должен развезти пиццу по шести адресам. Сколько маршрутов он может выбрать?

№2. Используя цифры 0, 2, 4, 6, 8 составьте все возможные трехзначные числа, в которых цифры не повторяются?

№3. На плоскости отмечены 9 точек, никакие три из них не лежат на одной прямой. Сколько прямых можно провести через эти точки?

№4. Сколько существует шестизначных телефонных номеров, начинающихся на 36, в которых все цифры разные?