Сколькими способами можно расставить тома энциклопедии

Решим более общую задачу. Пусть энциклопедия состоит из $n$ томов. Количество расстановок $n$-томной энциклопедии, удовлетворяющих условию задачи, обозначим $S_$. Рассмотрим варианты расстановки последнего тома энциклопедии. Если мы его поставим на свое место, то остальные $n — 1$ томов можно поставить на первые $n — 1$ мест $S_$ способом. Если же мы поставим $n$-й том на $(n — 1)$-е место, то $n$-е место мы обязаны занять $(n — 1)$-м томом, при этом количество расстановок остальных $(n — 2)$-х томов на первые $n — 2$ места равно $S_$. Таким образом, $S_ = S_ + S_$. Ясно, что $S_ <1>= 1, S_ <2>= 2$ (два тома можно либо поставить правильно, либо поменять местами). Далее, $S_ <3>= S_ <2>+ S_ <1>= 2 + 1 = 3; S_ <4>= 3 + 2 = 5; S_ <5>= 5 + 3 = 8; S_ <6>= 8 + 5 = 13; S_ <7>= 13 + 8 = 21; S_ <8>= 21 + 13 = 34$.

Числовая последовательность ($S_$), полученная в процессе решения задачи, называется последовательностью чисел Фибоначчи. Она задается начальными условиями $S_ <1>= 1; S_ <2>= 2$ и рекуррентным соотношением $S_ = S_ + S_$ для всех $n > 2$, то есть, каждый член этой последовательности, начиная с третьего, равен сумме двух предшествующих.
Ответ: 34 (считал и тот случай, когда все тома стоят на своем месте).

Источник

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

Главная > Документ

6. Примеры более сложных задач на сочетания, размещения и перестановки без повторений.

Пример 17 . Из 10 роз и 8 георгинов нужно составить букет так, чтобы в нем было 2 розы и 3 георгина. Сколькими способами это можно сделать?

Решение. Выберем сначала из 10 роз 2 розы. Это можно осуществить способами. Мы используем сочетания, а не размещения, потому что порядок, в котором выбираются цветы, значения не имеет. Независимо от выбора роз 3 георгина из 8 можно взять способами. Тогда, по правилу произведения, 2 розы и 3 георгина можно выбрать способами.

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

Пример 18 . Собрание из 40 человек избирает председателя, секретаря и трех членов редакционной комиссии. Сколько существует возможностей выбора этих пяти человек?

Решение. Выберем сначала председателя и секретаря. Вариантов выбора этих двух человек из 40 будет . Размещения здесь потому, что этот выбор зависит от порядка, например, «Иванов – председатель, Петров – секретарь» и «Петров – председатель, Иванов – секретарь» – это разные варианты. Затем из оставшихся 38 человек изберем 3 человека в редакционную комиссию. Это делается способами. По правилу произведения всего вариантов:

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

Пример 19 . Сколькими способами можно расставить 8 томов энциклопедии на книжной полке так, чтобы первый и второй тома:

б) не стояли рядом?

Решение. а). Подсчитаем сначала число вариантов расстановки, когда первый и второй тома стоят рядом. Их можно считать за одну книгу. Тогда получается Р 7 = 7! перестановок. Но первый и второй тома можно соединить двумя способами: слева первый, справа второй том и наоборот. За счет этого количество вариантов удваивается и всего их будет 27! = 10080.

б). Указанные тома не стоят рядом во всех остальных случаях, значит, из общего числа перестановок восьми книг надо вычесть число перестановок, когда тома стоят рядом. Итак, 8! – 10080 = 30240.

Ответ: а)10080, б) 30240.

Пример 20 . Даны две параллельные прямые. На одной из них имеется 10 точек, а на другой – 20. Сколько существует треугольников с вершинами в данных точках?

Решение. Заметим, что здесь будет два типа треугольников, расположенных вершинами вверх и вершинами вниз. Для треугольника первого типа вершину выбираем 10 способами, а основание (2 точки из 20) – способами. Всего, по правилу произведения, получается 10 треугольников. Аналогично, треугольников второго типа будет 20 . Наконец, применив правило суммы, получим общее количество треугольников: 10 + 20 = 2800.

Ответ: 2800 треугольников

Пример 21 . В вагоне электрички имеются два противоположных дивана по 5 мест на каждом. Из 10 пассажиров четверо желают сидеть лицом по ходу движения, трое – против хода, а остальным безразлично, как сидеть. Сколькими способами могут разместиться пассажиры с учетом их желаний?

Решение. Желающих сидеть по ходу движения разместим способами, против хода – , остальных троих на три пустых места – Р 3 = 3! способами. По правилу произведения всех пассажиров можно разместить способами.

Ответ: 43200 способами

Пример 22 . На школьном вечере присутствуют 12 девушек и 15 юношей. Сколькими способами можно выбрать из них 4 пары для танца?

Решение. Четырех девушек можно выбрать способами. После этого выбираем способами юношей (здесь уже существенен порядок). Всего = 17 417 400.

Ответ: 17 417 400 способами

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

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

Рассмотрим, например, слово «квант», состоящее из пяти различных букв. Если менять порядок букв, получим 5! =120 перестановок, т.е. 120 новых слов. (Словом будем называть любую комбинацию букв). Если проделать то же со словом «АТАКА», то перестановок будет меньше, потому что, меняя местами первую, третью и пятую буквы, будем получать то же самое слово. И, так как три буквы «А» можно менять местами 3! = 6 способами, то и перестановок в слове «АТАКА» будет в 6 раз меньше.

А теперь рассмотрим общий случай. Пусть дана выборка

,

состоящая из n элементов, причем, элемент а повторяется m 1 раз, элемент b – m 2 раз, и т.д., элемент с – m k раз и m 1 + m 2 +…+ m k = n . Перестановки в такой выборке, где есть одинаковые элементы, называются перестановками с повторениями и число перестановок с повторениями обозначается . Из приведенных выше рассуждений следует формула:

(7.1)

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

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

Ответ: 5040 способами

Пример 24 . У мамы 2 яблока, 3 груши и 4 апельсина. Каждый день в течение девяти дней она выдает сыну по одному фрукту. Сколько может быть вариантов такой выдачи?

Решение. Обозначая фрукты по первым буквам названия, составим несколько вариантов выдачи: ЯЯГГГАААА, ААГГЯГААЯ, ГГГААЯЯАА. Эти выборки имеют один и тот же состав и отличаются только перестановкой элементов, поэтому применяем формулу числа перестановок с повторениями.

Ответ: 1260 вариантов

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

Определение.8.1. Размещениями с повторениями из n по m называются упорядоченные m -элементные выборки, в которых элементы могут повторяться.

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

(8.1)

Пример 25 . Сколько четырехбуквенных «слов» можно составить из букв «М» и «А»? Результат проверить непосредственно.

Решение. Составим несколько таких «слов». МММА, МАМА, МААА …Мы видим, что состав выборки меняется, порядок элементов в выборке существенен. Значит, это – размещения с повторениями из 2 букв «М» и «А» по 4 буквы.

Выпишем непосредственно все эти 16 «слов»:

ММММ, МММА, ММАМ, МАММ, АМММ, ММАА, МАМА, АММА, АМАМ, ААММ, МААМ, АМАА, ААМА, АААМ, МААА, АААА.

Пример 26 . Вдоль дороги стоят 6 светофоров. Сколько может быть различных комбинаций их сигналов, если каждый светофор имеет 3 состояния: «красный», «желтый», «зеленый»?

Решение. Выпишем несколько комбинаций: КККЖЗЗ, ЗЗЗЗЗЗ, КЖЗКЖЗ… Мы видим, что состав выборки меняется и порядок элементов существенен (ведь если, например, в выборке КЖЗКЖЗ поменять местами К и Ж, ситуация на дороге будет другой). Поэтому применяем формулу размещений с повторениями из 3 по 6:

Ответ: 729 комбинаций

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

Определение 9.1. Сочетаниями с повторениями из n по m называются неупорядоченные m -элементные выборки, в которых элементы могут повторяться.

Число сочетаний с повторениями из n по m обозначается . В отличие от обычных сочетаний, где m  n , в сочетаниях с повторениями m и n могут быть любыми. Формулу для вычисления числа сочетаний с повторениями выведем на основе следующего частного примера.

Пример 27 . В почтовом отделении имеются открытки 3 видов. Сколькими способами можно купить набор из 5 открыток?

Ясно, что в купленном наборе открыток они будут повторяться и порядок их в наборе не важен, то есть это будут сочетания с повторениями из 3 по 5. Зашифруем все возможные наборы из 5 открыток следующим образом: открытки каждого вида изобразим в виде единиц, разделенных символами . Так выборка 11111 означает, что мы купили 2 открытки первого вида, одну – второго и 2 открытки третьего вида, а 11111 – все 5 открыток третьего вида. Подсчитаем количество таких выборок. Каждая из них состоит из 7 элементов: пяти единиц и двух трегольников, то есть состав не меняется, а меняется только порядок элементов. Значит, это будут перестановки с повторениями из 7 элементов, где  повторяется два раза, а 1 – пять раз.

В общем случае, если имеется n видов открыток, а купить надо m штук, получим:

(9.1)

Это и есть формула числа сочетаний с повторениями, однако она неудобна для запоминания, поэтому представим эту формулу в другом виде. Для этого вычислим по формуле (4.2):

и сравним с (9.1). Правые части этих равенств равны. Приравнивая левые части, получим формулу, выражающую число сочетаний с повторениями через обычное число сочетаний.

(9.2)

Пример 28 . В хлебном отделе имеются булки белого и черного хлеба. Сколькими способами можно купить 6 булок хлеба?

Решение. Обозначая булки белого и черного хлеба буквами Б и Ч, составим несколько выборок: ББББББ, ББЧЧББ, ЧЧЧЧЧБ, …

Состав меняется от выборки к выборке, значит, это уже не перестановки; порядок элементов несущественен, это – сочетания с повторениями из 2 по 6.

.

Сделаем проверку и выпишем все варианты покупки: ББББББ, БББББЧ, ББББЧЧ, БББЧЧЧ, ББЧЧЧЧ, БЧЧЧЧЧ, ЧЧЧЧЧЧ. Их действительно 7.

Ответ: 7 вариантов

Пример 29 . Сколько существует прямоугольных параллелепипедов, длина ребра которых выражается целым числом от 1 до 9?

Решение. Параллелепипед определяется тремя ребрами, поэтому его можно представить в виде тройки чисел. Выпишем несколько вариантов: (1,1,5); (2,7,9); (4,4,4) … Элементы в выборке могут повторяться, состав меняется, порядок не существенен, например, выборки (2,7,9) и (9,2,7) соответствуют одному и тому же параллепипеду. Применяем формулу сочетаний с повторениями

Ответ: 165 параллелепипедов

10. Схема определения вида комбинации

Приведем в систему полученные формулы всех 6 видов комбинаций с повторениями и без повторений, представив алгоритм определения вида комбинации следующей схемой.

Составить несколько комбинаций (выборок)

Повторяются ли элементы в выборке ?

Меняется ли состав ?

Меняется ли состав ?

Существенен ли порядок?

Существенен ли порядок?

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

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

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

Решим несколько задач с применением данной схемы.

Пример 30 . В магазине игрушек имеются 7 одинаковых Чебурашек и 2 одинаковых Крокодила. Сколькими способами их можно расставить в один ряд на витрине?

Решение. Обозначив игрушки первыми бувами названия, составим несколько комбинаций: КЧЧЧЧЧЧЧК, ЧЧЧКЧКЧЧЧ, ККЧЧЧЧЧЧЧ, … Повторяются ли элементы в выборке? Да. Меняется ли состав? Нет, ведь каждая выборка состоит из семи букв «Ч» и двух букв «К». Следовательно, это перестановки с повторениями.

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

Пример 31 . На окружности расположено 20 точек. Сколько существует вписанных треугольников с вершинами в этих точках?

Решение. Занумеруем точки числами от 1 до 20. Тогда каждый вписанный треугольник будет представлять собой тройку чисел. Выпишем несколько выборок: (1, 5, 19), (15, 2, 9), (14, 13, 7) …. Числа в выборке не могут повторяться, так как все вершины треугольника различны. Состав меняется от выборки к выборке, порядок не существенен, так как (1, 5, 19) и (19, 5, 1) – один и тот же треугольник. По схеме получается, что это сочетания без повторений из 20 по 3.

Ответ: 1140 треугольников

Пример 32 . В некотором сказочном государстве не было двух жителей с одинаковым набором зубов (либо у них разное число зубов, либо зубов нет в разных местах). Оцените наибольшую численность населения этого государства, если максимальное число зубов у человека – 32.

Решение. Закодируем каждого жителя набором из 32 нулей и единиц. Единица соответствует наличию зуба в данном месте, нуль – его отсутствию. Выпишем несколько комбинаций: 11111…11, 1010…11, 00000…00, …Элементы повторяются, состав меняется, порядок существенен. Это – размещения с повторениями из 2 по 32.

. Ответ: 4294967296 жителей

Пример 33 . Имеются в неограниченном количестве палочки длиной 5, 6, 7, 8, 9, 10 сантиметров. Сколько различных треугольников можно из них составить?

Решение. Составим несколько выборок: (5,5,5); (6,7,8); (8,9,9)..

Элементы повторяются, состав меняется, порядок не существенен. Согласно схеме, применяем формулу сочетаний с повторениями из 6 по 3: . Однако, здесь есть небольшой подвох: треугольника со сторонами 5, 5, 10 не существует, так что их будет 55.

Источник