сколькими разными вариантами можно разместить 3 разных объекта на 5 местах информатика
Элементы комбинаторики: перестановки, сочетания и размещения.
Элементы комбинаторики: перестановки, сочетания и размещения.
Определение: Комбинаторика – это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов .
Слово «комбинаторика» происходит от латинского слова «combinare», что в переводе на русский означает – «сочетать», «соединять». Комбинаторные задачи возникли и в связи с такими играми, как шашки, шахматы, домино, карты, кости и т.д.
Комбинаторные задачи делятся на: задачи на перестановки , задачи на размещение, задачи на сочетание
Определение: Факториал – это произведение всех натуральных чисел от 1 до n.
Пример: 4! = 1 · 2 · 3 · 4 = 24.
Задачи на перестановки
Сколькими способами можно расставить 3 различные книги на книжной полке?
Это задача на перестановки.
Решение: Выбираем одну из 3-х книг и ставим на первое место. Это можно сделать 3-мя способами.
Вторую книгу мы можем выбрать из 2-х оставшихся двумя способами, получаем 3·2 способов.
Третью книгу мы можем выбрать 1 способом.
Получится 3·2·1=6 способов.
Определение: Перестановками из n элементов называются комбинации из n элементов, отличающиеся друг от друга только порядком расположения в них элементов.
Типичная смысловая нагрузка: «Сколькими способами можно переставить n объектов?»
Пример 1. Сколькими способами можно расставить 8 участников финального забега на восьми беговых дорожках?
Решение: P 8 = 8!=1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 = 40320.
Пример 2. Сколькими способами можно составить расписание на один день, если в этот день предусмотрено 6 уроков по 6 разным предметам?
Решение: P 6 = 6!=1 ∙2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 = 720.
Пример 3. Сколькими различными способами можно разместить на скамейке 10 человек?
Решение: P 8 = 8!=1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 ∙ 9 ∙ 10 = 3628800.
Пример 4. Сколько слов можно получить, переставляя буквы в слове Гора?
Решение: P 4 = 4!=1 ∙2 ∙ 3 ∙ 4 = 24.
Пример 5. Сколько различных шестизначных чисел, кратных 5, можно составить из цифр 1, 2, 3, 4, 5, 6 при условии, что цифры в числе не повторяются?
Решение: Чтобы число было кратным 5, цифра 5 должна стоять на последнем месте. Остальные цифры могут стоять на оставшихся пяти местах в любом порядке. Следовательно, искомое количество шестизначных чисел, кратных 5, равно числу перестановок из 5 элементов, т.е.
P 5 = 5!=1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 = 120.
Задачи на размещения
Имеется 5 книг и одна полка, такая что на ней вмещается лишь 3 книги.
Сколькими способами можно расставить на полке 3 книги?
Это задача на размещение.
Решение: Выбираем одну из 5-ти книг и ставим на первое место на полке. Это можно сделать 5-ю способами.
Вторую книгу мы можем выбрать 4-мя способами и поставить рядом с одной из 5-ти возможных первых.
Таких пар может быть 5·4.
Третью книгу мы можем выбрать 3-мя способами.
Получится 5·4·3 разнообразных троек. Значит всего способов разместить 3 книги из 5-ти 5·4·3 = 60.
Определение: Размещением из n элементов по k ( k ≤ n ) называется любое множество, состоящее из k элементов, взятых в определённом порядке из данных n элементов.
Типичная смысловая нагрузка: «Сколькими способами можно выбрать k объектов и в каждой выборке переставить их местами?»
Пример 1. Учащиеся второго класса изучают 9 предметов. Сколькими способами можно составить расписание на один день, чтобы в нём было 4 различных предмета?
Пример 2. Сколько трехзначных чисел можно составить из цифр 2, 4, 6, 7, 9?
Пример 3. В соревнованиях высшей лиги по футболу участвуют 18 команд. Борьба идет за золотые, серебряные и бронзовые медали. Сколькими способами могут быть распределены медали между командами?
Пример 4. Сколькими способами можно опустить 5 писем в 11 почтовых ящиков, если в каждый ящик опускают не более одного письма?
Пример 5. Боря, Дима и Володя сели играть в карты. Сколькими способами им можно сдать по одной карте? (колода содержит 36 карт)
– способами можно раздать 3 карты игрокам.
Пример 6. В пассажирском поезде 9 вагонов. Сколькими способами можно рассадить в поезде 4 человека, при условии, что все они должны ехать в различных вагонах?
– способами можно рассадить в поезде 4 человека.
Задачи на сочетания
Сколькими способами можно расставить 3 тома на книжной полке, если выбирать их из имеющихся в наличии внешне неразличимых 5 книг?
Это задача на сочетания.
Решение: Книги внешне неразличимы. Но они различаются, и существенно! Эти книги разные по содержанию. Возникает ситуация, когда важен состав элементов выборки, но несущественен порядок их расположения.
123 124 125 134 135 145
Определение: Сочетанием из n элементов по k ( k n ) называется любое множество, составленное из k элементов, выбранных из данных n элементов (не имеет значения, в каком порядке указаны элементы).
Типичная смысловая нагрузка: «Сколькими способами можно выбрать k объектов из n ?»
Пример 1. В классе 7 человек успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде?
Пример 2. На тренировках занимаются 12 баскетболистов. Сколько может быть организовано тренером разных стартовых пятерок?
Пример 3. В ящике находится 15 деталей. Сколькими способами можно взять 4 детали?
Пример 4. Сколькими способами из колоды в 36 карт можно выбрать 3 карты?
Пример 5. Для участия в команде тренер отбирает 5 мальчиков из 10. Сколькими способами он может сформировать команду, если 2 определенных мальчика должны войти в команду?
Решение: Т.к. двое мальчиков войдут в команду, то остается отобрать 3 из 8. Для выборки важен только состав (по условию все члены команды не различаются по ролям).
Пример 6. В шахматном турнире принимали участие 15 шахматистов, причем каждый из них сыграл только одну партию с каждым из остальных. Сколько всего партий было сыграно в этом турнире?
Решение: В одной игре участвуют 2 человека, следовательно, нужно вычислить, сколькими способами можно отобрать 2-х человек из 15, причем порядок в таких парах не важен.
Пример 7. Сколько различных дробей можно составить из чисел 3, 5, 7, 11, 13, 17 так, чтобы в каждую дробь входили 2 различных числа? Сколько среди них будет правильных дробей?
Решение: Различных дробей из 6 чисел: 3, 5, 7, 11, 13, 17 можно составить
штук ( способами выбираем два числа из 6, и двумя способами составляем из них дробь, сначала одно число – числитель, другое – знаменатель и наоборот).
Из этих 30 дробей 15 будут правильные.
Пример 8. Боря, Дима и Володя сели играть в карты. Сколькими способами им можно сдать по одной карте? (колода содержит 36 карт)
Правило сложения комбинаций
Знак «плюс» следует понимать и читать как союз ИЛИ.
Задача. Студенческая группа состоит из 23 человек, среди которых 10 юношей и 13 девушек. Сколькими способами можно выбрать 2-х человек одного пола?
Решение: Условие «выбрать 2-х человек одного пола» подразумевает, что необходимо выбрать двух юношей или двух девушек:
– способами можно выбрать 2-х юношей;
– способами можно выбрать 2-х девушек;
Таким образом, двух человек одного пола (без разницы – юношей или девушек) можно выбрать: способами.
Пример 1. В группе 9 человек. Сколько можно образовать разных подгрупп при условии, что в подгруппу входит не менее 2 человек?
Решение: Не менее 2-х человек, т.е. 2+7 или 3+6 или 4+5 человек (5+4, 6+3, 7+2 – те же самые комбинации).
В каждой выборке важен только состав, т.е. члены подгруппы не различаются по ролям, т.е. выборки – сочетания из n различных элементов по m элементов.
Число выборов из 2-х человек:
Число выборов из 3-х человек:
Число выборов из 4-х человек:
Применяем правило сложения: способов.
Правило умножения комбинаций
Знак «умножить» следует понимать и читать как союз И.
Задача. Студенческая группа состоит из 23 человек, среди которых 10 юношей и 13 девушек. Сколькими способами можно составить пару из юноши и девушки?
– способами можно выбрать 1 юношу;
– способами можно выбрать 1 девушку.
Таким образом, 1-го юношу и 1 девушку можно выбрать: способами.
Пример 1. Предприятие может предоставить работу по одной специальности 4 женщинами, по другой – 6 мужчинам, по третьей – 3 работникам независимо от пола. Сколькими способами можно заполнить вакантные места, если имеются 14 претендентов: 6 женщин и 8 мужчин?
Решение: Имеем 14 претендентов и 13 рабочих мест. Сначала выберем работников на первую специальность, то есть 4 женщин из 6:
Далее выберем мужчин на вторую специальность:
Осталось 2 женщины, 2 мужчин и 3 вакантных места, которые, по условию, могут занять любые из четырех оставшихся человек.
Это может быть сделано 2 вариантами:
1 женщина и 2 мужчин (выбираем женщину способами)
1 мужчина и 2 женщины (выбираем мужчину способами).
В итоге получаем 15 · 28 · (2+2)=1680.
Пример 2. Группу из 20 студентов нужно разделить на 3 бригады, причем в первую бригаду должны входить 3 человека, во вторую – 5 и в третью – 12. Сколькими способами это можно сделать.
Решение: Создавая первую бригаду, отбирают 3 человека из 20, создавая вторую – 5 из оставшихся 17, создавая третью – 12 из оставшихся 12. Для выборок важен только состав (роли членов бригады не различаются).
Создавая сложную выборку (из 3-х бригад), воспользуемся правилом умножения:
Пример 3. Сколькими способами может быть сдана выигрышная комбинация из 2-х карт при игре в «очко»?
Для тех, кто не знает: выигрывает комбинация 10 + ТУЗ (11 очков) = 21 очко и будем считать выигрышной комбинацию из 2-х тузов.
способами может быть сдана десятка и туз («каждая десятка с каждым тузом»);
способами может быть сдана пара тузов.
Итого: выигрышные комбинации.
Пример 4. Сколько существует трёхзначных чисел, которые делятся на 5?
В разряде сотен можно записать любую из цифр.
В разряде десятков можно выбрать любую из 10 цифр:
По условию, число должно делиться на 5. Число делится на 5, если оно заканчивается на 5 либо на 0. Таким образом, в младшем разряде нас устраивают 2 цифры.
Итого, существует: трёхзначных чисел, которые делятся на 5.
Перестановки с повторениями
У мамы 2 яблока и 3 груши. Каждый день в течение 5 дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано?
Решение:Имеем набор <я, я, г, г, г>. Всего перестановок пятиэлементного множества 5!, но мы не должны учитывать перестановки, в которых объекты одного типа меняются местами несколько раз, поэтому нужно поделить на возможное число таких перестановок: 2! · 3!.
Пример 1: Сколько различных буквосочетаний можно получить перестанов-кой карточек со следующими буквами: К, О, Л, О, К, О, Л, Ь, Ч, И, К?
Решение: Всего: 11 карточек, среди которых буква:
К – повторяется 3 раза;
О – повторяется 3 раза;
Л – повторяется 2 раза;
Ь – повторяется 1 раз;
Ч – повторяется 1 раз;
И – повторяется 1 раз.
По формуле количества перестановок с повторениями:
Пример 2: Сколько слов можно получить, переставляя буквы в слове Институт?
Решение: В слове «институт» 8 букв, из них две буквы «и», три буквы «т» и по одной букве «н», «с» и «у». Поэтому всего можно получить перестановками букв различных слов.
Пример 3: Алексей занимается спортом, причём 4 дня в неделю – лёгкой атлетикой, 2 дня – силовыми упражнениями и 1 день отдыхает. Сколькими способами он может составить себе расписание занятий на неделю?
Решение: По формуле количества перестановок с повторениями:
способами можно составить расписание занятий на неделю.
Пример 4: Сколько чисел, больших 3000000, можно составить из цифр 3, 2, 2, 1, 1, 1, 0.
Решение: На первом месте обязательно должна стоять тройка. Оставшиеся 6 цифр образуют перестановку с повторениями:.
Сочетания с повторениями
В студенческой столовой продают сосиски в тесте, ватрушки и пончики. Сколькими способами можно приобрести пять пирожков?
Решение ( I способ.) :Обратите внимание на критерий сочетаний с повторениями – по условию на выбор предложено не множество объектов как таковое, а различные виды объектов; при этом предполагается, что в продаже есть не менее пяти хот-догов, 5 ватрушек и 5 пончиков.
Что может быть в выборке?
Варианты: 5 хот-догов, 5 ватрушек, 5 пончиков, 3 хот-дога + 2 ватрушки, 1 хот-дог + 2 ватрушки + 2 пончика и т.д. Всего 21 способ.
Типичная смысловая нагрузка: «Для выбора предложено n множеств, каждое из которых состоит из одинаковых объектов. Сколькими способами можно выбрать m объектов?»
Используя формулу количества сочетаний с повторениями, получаем
способом можно приобрести 5 пирожков.
Пример 1: В кошельке находится достаточно большое количество рублей, 2-х, 5-ти и десятирублёвых монет. Сколькими способами можно извлечь три монеты из кошелька?
Решение: Используя формулу количества сочетаний с повторениями, получаем
способами можно выбрать 3 монеты из кошелька.
Пример 2: В почтовом отделении продаются открытки 10 видов. Сколькими способами можно купить 12 открыток для поздравлений?
Размещения с повторениями
Сколько существует четырёхзначных пин-кодов?
Решение:Для решения задачи достаточно знаний правил комбинаторики:
способами можно выбрать первую цифру пин-кода и способами – вторую цифру пин кода и столькими же способами – третью и столькими же – четвёртую. Таким образом, по правилу умножения комбинаций, четырёхзначный пин-код можно составить: способами.
Типичная смысловая нагрузка: «Дано множество, состоящее из n объектов, при этом любой объект можно выбирать неоднократно. Сколькими способами можно выбрать m объектов, если важен порядок их расположения в выборке?
В частности, возможен случай, когда из n имеющихся объектов m раз будет выбран какой-то один объект».
Пример 1: Согласно государственному стандарту, автомобильный номерной знак состоит из 3 цифр и 3 букв. При этом недопустим номер с тремя нулями, а буквы выбираются из набора А, В, Е, К, М, Н, О, Р, С, Т, У, Х (используются только те буквы кириллицы, написание которых совпадает с латинскими буквами).
Сколько различных номерных знаков можно составить для региона?
– способами можно составить цифровую комбинацию автомобильного номера, при этом одну из них (000) следует исключить
– способами можно составить буквенную комбинацию автомобильного номера.
По правилу умножения комбинаций, всего можно составить
Пример 2: Человек, пришедший в гости, забыл код, открывающий дверь подъезда, но помнил, что он составлен из нулей и единиц и всего имеет четыре цифры. Сколько вариантов кода в худшем случае ему придётся перебрать, чтобы открыть дверь?
Пример 3: Каких чисел от 1 до 1 000 000 больше: тех, в записи которых встречается единица, или тех, в которых она не встречается?
Решение: Подсчитаем количество чисел от 1 до 999999 в записи которых нет единиц. Каждую цифру можно выбрать 9 способами (любая цифра кроме 1), поэтому все 6 цифр можно выбрать 9 6 способами. При этом один вариант (000000) нужно убрать, так как число 0 не рассматривается. Получаем всего 9 6 −1=531440 чисел. Так как всего чисел 1 000 000, то видно, что чисел без единицы среди чисел от 1 до 1 000 000 больше, чем тех, в записи которых единица есть.
Ответ: чисел без единицы больше.
(разработка + презентация) на тему «Комбинаторика для школьников любого возраста»
Решение комбинаторных задач. Размещения
Размещения. Формула для числа размещений
1) Размещения с повторениями
Пусть множество Х состоит из n элементов.
Число всех размещений с повторениями из n элементов по k зависит от n и от k (а не от природы множества Х ). Это число обозначается 
. Формула для его нахождения выводится с помощью правила произведения:
(1)
Пример. Сколько трёхзначных чисел может быть составлено из нечётных цифр?
Решение. Х = <1, 3, 5, 7, 9>, 
.
.
Заметим, что эту задачу можно было решить и с помощью правила произведения, которое работало бы и в том случае, если в условии поменять нечётные цифры на чётные. А вот понятие размещений и формула (1) в этом случае не сработали бы!
2) Размещения без повторений
Пусть множество Х состоит из n элементов.
Так как повторения в кортеже не допускаются, то теперь k должно быть не больше n .
Для выбора элемента 
имеется n возможностей. После выбора элемента , элемент 
можно выбрать 
-м способом и так далее. Тогда
(2)
Пример. Сколько трёхзначных чисел может быть составлено из нечётных цифр так, чтобы цифры в каждом числе не повторялись?
Решение. Х = <1, 3, 5, 7, 9>, .
.
Это задача о выборе двух элементов из трех с учетом порядка выбора. Перечислим эти варианты:
Если учащимся известна формула для числа размещений, то количество вариантов равно: А 
вариантов.
2.Ф. Сколькими способами могут быть заняты первое, второе и третье места (по одному человеку на место) на соревнованиях, в которых участвуют: 1) 5 человек; 2) 6 человек?
Это задача о выборе трех элементов из 5 или 6 с учетом порядка выбора.
1)По правилу произведения 5 • 4 • 3 = 60 способов.
2)По правилу произведения 
= 120 способов. Если учащиеся знают формулу для числа размещений, то получаем соответственно:
A
A 
Ответ: 1) 60 способов; 2) 120 способов.
М-задачи из уч. пособия А.Г.Мордковича
Т- под ред. С.А.Теляковского
3. Т. Сколькими способами может разместиться семья из трех человек в четырехместном купе, если других пассажиров в купе нет?
Пронумеруем места в купе (с № 1 по № 4) и будем «выдавать» каждому из трех членов семьи номер места. Из 4 элементов (номеров мест) будут делаться выборки по 3 элемента, при этом важен не только состав выборки, но и порядок расположения в ней элементов (кто именно и на каком месте поедет). Число способов равно числу размещений из 4 по 3:
4. Т. Из 30 участников собрания надо выбрать председателя и секретаря. Сколькими способами это можно сделать?
Из 30 элементов выбираем 2, причем порядок выбора имеет значение. Количество способов выбора равно A 
= 30 • 29 = 870 способов.
Ответ: 870 способов.
5. Т. Сколькими способами могут занять первое, второе и третье места 8 участниц финального забега на дистанции 100 м?
Выбор из 8 по 3 с учетом порядка: A 
= 336 способов.
Ответ: 336 способов.
6. Т. На станции 7 запасных путей. Сколькими способами можно расставить на них 4 поезда?
Выбираем из 7 запасных путей 4 пути для размещения на них поездов; порядок выбора имеет значение: A
= 
840 способов.
Ответ: 840 способов.
7. Т. Сколькими способами можно изготовить трехцветный флаг с горизонтальными полосами, если имеется материал 7 различных цветов?
A
= 210 способов.
Ответ: 210 способов.
8. Т. На соревнования по легкой атлетике приехала команда из 12 спортсменок. Сколькими способами тренер может определить, кто из них побежит в эстафете 4×100 м на первом, втором, третьем и четвертом этапах?
Выбор из 12 по 4 с учетом порядка: A
= 11 880 способов.
Ответ: 11880 способов.
9. М. Сколькими способами могут быть распределены первая, вторая и третья премии между 15 участниками конкурса?
Выбираем 3 призеров из 15 участников конкурса с учетом порядка (кому какая премия):
A
= 2 730 способов.
10. Т. Сколькими способами 6 студентов, сдающих эк. замен, могут занять места в аудитории, в которой стоит 20 одноместных столов?
Выбираем 6 столов для студентов из 20 имеющихся: порядок выбора учитывается (кто сидит у окна, кто около преподавателя и т. п.):
А
= 27 907 200 способов.
Ответ: 27 907 200 способов.
11. Т. На странице альбома 6 свободных мест для фотографий. Сколькими способами можно вложить в свободные места: а) 2 фотографии; б) 4 фотографии; в) 6 фотографий?
а) Выбираем 2 места для фотографий из 6 свободных мест в альбоме: А
= 30 способов.
б) Выбираем 4 места для фотографий из А
= 360 способов.
в) Выбираем 6 мест из 6 (делаем всевозможные перестановки из 6 фотографий):
А
= 6! = 720 способов.
Ответ: а) 30 способов; б) 360 способов; в) 720 способов.
12. М. На плоскости отметили 5 точек. Их надо обозначить латинскими буквами. Сколькими способами это можно сделать (в латинском алфавите 26 букв)?
Выбираем 5 букв для обозначения точек из 26 букв в алфавите; порядок выбора имеет значение (какую точку какой буквой обозначим): А
= 7 893 600 способов.
Ответ: 7 893 600 способов.
13. Т. Сколько четырехзначных чисел, в которых нет одинаковых цифр, можно составить из цифр: а) 1, 3, 5, 7, 9; б) 0, 2, 4,
а) Выбираем 4 цифры из 5 данных; порядок выбора имеет значение: А
= 120 чисел.
б) Выбираем 4 цифры из 5, но на первое место нельзя выбирать ноль.
Используем метод исключения лишних элементов: если на первое место выбран ноль, то после этого выбираем еще на 3 места цифры из 4 оставшихся, получаем А 
= 24 «нулевых» комбинаций, которые недопустимы.
Количество четырехзначных чисел, которые можно составить из данных 5 чисел, равно:
Ответ: а) 120 чисел; б) 96 чисел.
14. Т. Из трехзначных чисел, записанных с помощью цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 (без повторения цифр), сколько таких, в которых:
а) не встречаются цифры 6 и 7;
б) цифра 8 является последней?
а) Выбираем 3 цифры из 7 (без 6 и без 7) с учетом порядка выбора; число вариантов: А 
=
= 210 чисел.
б) Фиксируем цифру 8 на последнем месте; на остальные два места перед ней можно выбрать любые 2 цифры из 8 оставшихся ( с учетом порядка выбора). Количество вариантов: А 
= 56 чисел.
Ответ: а) 210 чисел; б) 56 чисел.
15. М. Сколько существует семизначных телефонных номеров, в которых все цифры различные и первая цифра отлична от нуля?
Выбираем из 10 цифр семь, причем первый выбор делается из 9 цифр (без нуля). Используя метод исключения лишних вариантов, получаем: А
А 
544 320 номеров.
Ответ: 544 320 телефонных номеров.
16. Т. Сколько различных трехзначных чисел (без повторения цифр) можно составить из цифр 1, 2, 3, 4, 5, таких, которые являются: а) четными; б) кратными 5?
Выбираем 3 цифры из 5 данных, причем:
а) последней цифрой должна быть 2 или 4; количество вариантов А 
(фиксирована 2) + А (фиксирована 4) = 
= 24 числа;
б) последней цифрой должна быть 5; количество вариантов равно А (фиксирована 5) = 
= 12 чисел.
Ответ: а) 24 числа; б) 12 чисел.
17. Т. Номер машины в некотором городе состоит из двух различных букв, взятых из набора М, Н, К, Т, С, и трех различных цифр. Сколько машин можно обеспечить такими номерами?
Каждый вариант выбора букв может сочетаться с каждым вариантом выбора цифр, поэтому по правилу произведения общее число способов равно: А
720 = 14 400 способов.
Ответ: 14 400 способов.
18.Т. Сколько команд участвовало в финале первенства, если известно, что каждая команда сыграла с каждой из остальных по одной игре на своем поле и по одной игре на поле соперника, причем всего было сыграно 30 игр?
Поскольку каждая пара команд сыграла между собой по две игры (на своем и на чужом поле), то выбор пары осуществляется с учетом порядка, т. е. составляются всевозможные размещения из n по 2. По условию задачи А 
n 
= 
, n = 6.
19. Т. Из группы туристов требуется выбрать дежурного и его помощника. Если туристов было бы на одного больше, то возможностей выбора было бы в 1,25 раза больше. Сколько туристов в группе?
а) все они хотят ехать в разных вагонах;
Вагоны поезда пронумерованы; осуществляется выбор 4 из 9 вагонов для размещения пассажиров; порядок выбора имеет значение (каждому пассажиру сообщаем номер вагона).
Ответ: а) 3 024 способа; б) 504 способа.
21. Ф. Высказать гипотезу о числе всевозможных разбиений п элементов на 3 группы.
Поступим следующим образом. Сопоставим каждому из п элементов свою ячейку, в которую будем записывать номер группы, в которую будет помещен этот элемент. Получим линейку из п ячеек, в каждой из которых может быть записана либо 1, либо 2, либо 3: