Задачи по комбинаторике для 5-8 классов

'т.

расположенное «вверх ногами» и без ствола. Корень дерева изображают знаком *.

Решим еще раз с помощью построения дерева задачу о числе трехбуквенных слов, которые можно составить, используя алфавит племени УАУА.

Чтобы составить слово, надо сначала выбрать его первую букву, а для этого у нас есть два варианта: буква «а» и буква «у». Поэтому из корня — знака > * — проведем два отрезка (две ветви) и на их концах поставим буквы «а» и «у».

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

5. Шифр для сейфа составляется из трех разных цифр.
Запишите все шифры, которые можно составить, используя цифры 1, 2 и 3.

6. Сколько чисел можно получить из числа 546, переставляя его цифры? Запишите
самое большое и самое маленькое из этих чисел в виде суммы разрядных
слагаемых.

7. В четверг в первом классе должно быть три урока: русский язык,
математика и физкультура. Сколько раз личных вариантов расписания можно
составить на этот день?

Указание. Перебирая варианты, введите обозначения: Р — русский язык, М — математика, Ф — физкультура.

8. В магазине продаются полотенца трех видов: в полоску, в клетку и в
горошек. Из скольких вариантов покупки придется выбирать, если нужны
два разных полотенца?

Указание. Введите обозначения: П — полоска, К —клетка, Г — горошек.

Из четырех игр: шашки, лото, конструктор и эрудит — надо выбрать две.
Сколькими способами можно осуществить этот выбор?

Сколькими способами можно составить патруль из двух милиционеров,
если на дежурство вышли четверо: Быстров, Свистунов, -Умнов и Дубов?

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

Сколькими способами можно выбрать два цветка, если есть васильки, маки,
ромашки и тюльпаны? Сколько получится таких пар, если их составлять из двух
разных цветков?

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

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

Школьники из Волгограда собрались на каникулы поехать в Москву, посетив
по дороге Нижний Новгород. Сколькими различными способами могут ребята осущест­
вить свое путешествие, если из Волгограда в Нижний Новгород можно отправиться
на теплоходе или поезде, а из Нижнего Новгорода в Москву — на самолете, теплоходе,
поезде или автобусе? Решите задачу с помощью построения дерева.

В костюмерной имеются желтые и белые кофты, а также синие, красные и
черные юбки. Сколько можно из них составить различных костюмов? Решите
задачу с помощью построения дерева. (Введите обозначения: Б — белые. Ж — желтые
кофты; С — синие, К — красные, Ч — черные юбки.)

Имеются ручки четырех цветов: красные, синие, зеленые, черные — и два вида
записных книжек. Сколько различных наборов из ручки и записной книжки можно
составить из этих предметов?

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

Начертите окружность и отметьте на ней три точки. Обведите получившиеся при
этом дуги карандашами разных цветов. Сколько карандашей вам потребовалось?
Сколько дуг у вас получилось?

Две волейбольные команды «Ласточка» и «Орленок играют матч до трех
побед. С каким счетом может закончиться их поединок, если в волейболе ничьих не
бывает. Составьте таблицу всех возможных вариантов исход поединка.

Хоккейная комбинация. На поле пять игроков. Начал комбинацию игрок № 1,

4 "А

продолжили игроки с другими номерами, а забил гол игрок № 5. Каждый хоккеист
ударил по шайбе только один раз. На рисунке с помощью стрелок изображен один из
возможных вариантов комбинации. Изобразите в тетради все другие возможные
варианты передачи шайбы между игроками данной комбинации.

23. Запишите все трехзначные числа, сумма цифр которых равна 3.

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

Девять школьников, сдавая экзамены по математике, русскому и
английскому языкам, получили отметки «4» и «5». Можно ли утверждать, что по
крайней мере двое из них получили по каждому предмету одинаковые отметки?

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

27. В телеигре участвуют пять человек, из них трое выходят в

финал. Сколько существует различных вариантов тройки

финалистов?

Сколькими способами можно рассадить двух мальчиков и двух девочек за две
нарты так, чтобы за каждой партой справа сидел мальчик, а слева — девочка?

Сколько существует трехзначных чисел, записанных цифрами 1 и 3 так, что сразу
после единицы не стоит тройка?

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

Дано число, записанное римскими цифрами: МСХ. Используя законы записи чисел
римскими цифрами, запишите все возможные числа, которые можно получить
перестановкой цифр этого числа. Запишите эти числа арабскими цифрами.

Туристы отправились в поход на лодках. Они договорились, что в темное время
дня будут передавать друг другу сообщения с помощью трех цветных
фонариков: желтого, красного, синего. Сколько различных сообщений могут
передать туристы, если для каждого сообщения должно использоваться три
фонарика разного цвета? Сколько еще можно передать сообщений, используя
для этого только один фонарик или два разных фонарика?

Логика перебора

Чтобы осуществить перебор, часто приходится вводить условные обозначения. Например, если в задаче речь идет о красных и зеленых шарах, то не обязательно рисовать эти шары или писать полностью их цвета. Можно ограничиться только первыми буквами — К и 3. Такую замену предметов их условными обозначениями называют кодированием.

Задача 1. Туристическая фирма планирует посещение туристами в Италии трех городов: Венеции, Рима и Флоренции. Сколько существует вариантов такого маршрута?

Обозначим города их первыми* буквами: В; Ф и Р. Тогда код каждого маршрута
будет состоять из трех букв, каждая из которых должна быть использована только один
раз, например ВФР или ФРВ. :

Дерево возможных вариантов изображено на рисунке. Путешествие можно начать в любом из трех городов. Если сначала посетить Венецию, то затем можно поехать в Рим или во Флоренцию. Если вторым посетить Рим, то третьей будет Флоренция; если второй будет Флоренция, то третьим будет Рим. Это первые два варианта путешествия. А всего, как мы видим, существует 6 вариантов путешествия.

Поэтому из чисел 68 и 86 надо выбрать 68.

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

. 12, 13, 14,15, 16,17,18,

23, 24, 25, 26, 27, 28,

34,35,36,37,38,

45, 46, 47, 48,

56,57,58,

67, 68,

78.

Число кодов равно:

7+6 +5+ 4 + 3 + 2+1 = 28.

Таким образом, всего было сделано 28 рукопожатий.

Задача 4. Человек, пришедший в гости, забыл код, открывающий дверь подъезда, но помнил, что он составлен из нулей и единиц и содержит четыре цифры. Сколько вариантов кода в худшем случае ему придется перебрать, чтобы открыть дверь?

Выпишем сначала все коды, содержащие одну единицу, затем — две единицы, затем— три единицы. Получим:

0001 0010 0100 1000 —4 варианта

ООН 0101 ОНО 1001 1010 1100 —6 вариантов
0111 1011 1101 1110 —4 варианта

Следовательно, в худшем случае человеку придется сделать 14 попыток.

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

Витя, Толя и Игорь купили вместе интересную книгу и решили читать ее по очереди.
Выпишите все варианты такой, очереди. Сколько есть вариантов, в которых Игорь на
первом месте? Витя не на последнем месте?

Используя цифры 3, 4, 5, причем каждую только один раз составьте всевозможные
трехзначные числа, которые делятся: а) на 2; б) на 5; в) на 3; г) на 6.

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

а) На соревнование по легкой атлетике нужно отправить двух мальчиков из пяти лучших
спортсменов, среди шестиклассников — Антона, Петра, Бориса, Володи, Коли.
Перечислите все варианты выбора участников соревнования. Сколько этих вариантов?

б) Для участия в эстафете 2 х 100 м нужно выбрать двух мальчиков из пяти, обязательно указав, кто побежит первым, а кто — вторым. Перечислите все варианты выбора участников соревнования в этом случае. Сколько этих вариантов?

6. На районной олимпиаде по математике оказалось шесть победителей. Однако на
областную олимпиаду можно отправить только двоих.

а) Сколько есть вариантов выбора двух кандидатов? ,
Указание. Дайте каждому победителю номер — от 1 до 6

б) Сколько есть вариантов, если один из шести ребят признан лучшим, и он
обязательно будет участвовать в областной олимпиаде?

7. К переправе одновременно подошли пять человек. Лодочник сказал, что в его
лодке поместятся только два пассажира,

а) Сколькими способами можно выбрать двоих пассажиров из пяти?

б) Сколько есть способов выбора пассажиров, если у одного из них болит зуб, и его
необходимо срочно отправить на другой берег в больницу?

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

8. Два курьера фирмы должны забрать почту из четырех филиалов, причем каждый
успеет съездить только в два филиала из четырех. Сколькими способами они могут
распределить между собой поездки?

Указание. Достаточно подсчитать число способов, которыми один курьер может выбрать два филиала из четырех.

Каждый из двух друзей может получить за контрольную по математике любую
отметку от 2 до 5. Сколько существует вариантов получения ими отметок?
Выпишите все эти варианты.

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

12. В классе три человека хорошо поют, двое других играют на гитаре, а еще один
умеет показывать фокусы. Сколькими способами можно составить концертную
бригаду из певца, гитариста и фокусника?

Слово, полученное из данного слова перестановкой букв (и не обязательно
имеющее смысл в языке), называют его анаграммой: например, «нос» и «сно» —
анаграммы слова «сон». Выпишите в алфавитном порядке все анаграммы слов а)
«нос» и «dog»; б) «мама» и «дама». Сравните количество анаграмм для слов в
каждой паре. Как бы вы объяснили получившийся результат?

Поэт-модернист написал стихотворение, в котором первая строка — «Хочу пойти
гулять куда-нибудь», а остальные строки все разные и получены из первой
перестановкой слов. Какое наибольшее количество строк может быть в этом
стихотворении?

Указание. В строке 4 разных слова, закодируйте их цифрами. Записав стихотворение в закодированном виде, «переведите» его на русский язык.

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

Человек забыл код, открывающий замок на его чемодане, но вспомнил, что код
состоит из трех разных цифр, каждая из которых не больше 3. Кроме того, в код
точно не входит сочетание 13. Сколько вариантов кода в худшем случае ему
придется перебрать, чтобы открыть свой чемодан?

а) Вальс будет исполнять одна пара. Сколько имеется вариантов выбора этой пары?

б) Кадриль должны станцевать вместе две пары. Сколько есть вариантов выбора
исполнителей этого танца? в) Мазурку будут исполнять одновременно три пары.
Сколько имеется вариантов составления этих трех пар?

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

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

а) Предположим, что первую партию выиграл Андрей, вторую и третью — Егор.
Сколько существует вариантов дальнейшего хода их поединка? Запишите каждый
из них.

б) Сколько существует вариантов развития поединка, при которых Андрей
выиграет со счетом 3 : 2? Запишите каждый из них.

в) Сколько всего существует вариантов хода их поединка?

Задача-исследование.

1) Аня и Галя карандашами пяти цветов — красным, синим, желтым, зеленым и фиолетовым — раскрашивают бумажные вымпелы для малышей. Аня делает двухцветные вымпелы, а Галя — трехцветные. Аня перебором подсчитала, что всего у нее 10 вариантов двухцветной раскраски. Галя подумала и, не перебирая варианты, сказала, что тогда вариантов трехцветной раскраски тоже 10. Запишите в строчку все 10 наборов из двух карандашей. Под каждым запишите дополняющий его до пяти цветов набор из трех карандашей. Может ли при этом какой-либо трехцветный набор повториться? оказаться не учтенным?

Докажите, что Галя права, продолжив рассуждение: когда Аня берет два каких-то карандаша, то Гале остаются некоторые три; если Аня переберет все возможные пары карандашей, то Галя .... Значит, ....

2) Четыре друга собрались на футбольный матч. Но им удалось купить только три билета.
Сколькими способами они могут выбрать тройку счастливцев? Как удобнее перебирать:
тройки тех, кто пойдет, или тех, кто не пойдет?

3) Из шести кандидатов нужно составить команду для участия в гонках на
четырехместных байдарках. Сколько существует вариантов для выбора четверки
участникjb соревнования и сколько — для выбора пары запасных? Ответы на оба
вопроса, проведя только один перебор.

Правило умножения

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

Занумеруем тропы числами от 1 до 4 и построим дерево возможных вариантов.

На первом уровне дерева 4 «узла» (подъем по любой из четырех троп). Из каждого узла выходят 3 ветки (спуск по трем остальным тропам). Всего получилось 4 • 3 = 12 маршрутов.

Подъем 1 •

/|\ | Спуск 234 134 124 123

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

Изобразить дерево возможных вариантов в такой ситуации сложно. Гораздо легче решить эту задачу с помощью рассуждений,

Подниматься к озеру можно по любой из десяти троп, а спускаться по любой из оставшихся девяти троп. Таким образом, всего получим 10*9 = 90 различных маршрутов похода.

Мы получили ответ умножением. Математики сказали бы, что мы использовали известное в комбинаторике правило умножения. Такой способ подсчета возможен, если дерево вариантов «правильное»: из.каждого узла одного уровня выходит одно и то же число веток.

Заметим, что если надо выяснить, является ли дерево «правильным», не обязательно строить его целиком. Достаточно изобразить какой-либо фрагмент. На рисунке изображен фрагмент дерева в том случае, когда к озеру ведут 10 троп. По нему нетрудно увидеть, что в данной ситуации дерево «правильное».

Подъем '12 3-456789 10

Спуск 2345678910... 123456789

Задача 2. На обед в школьной столовой предлагается 2 супа, 3 вторых блюда и 4 разных сока. Сколько различных вариантов обеда из трех блюд можно составить по предложенному меню?

В меню указаны 2 супа. С каждым из них мсжно взять любое из трех вторых блюд. Получаем 2*3 - 6 вариантов выбора супа и второго. К каждому из этих шести вариантов можно взять любой из четырех имеющихся соков. Итого получаем 2*3*4 = 24 варианта обеда из трех блюд.

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

Суп

Второе блюдо

Задача 3. Сколько существует трехзначных чисел, у которых все цифры четные?

Четных цифр всего пять — это 0, 2, 4, 6 и 8. Из этих цифр надо сначала выбрать первую цифру трехзначного числа. Для этого есть только 4 возможности, поскольку цифра 0 первой быть не может. Вторую цифру можно выбрать пятью способами, третью также пятью способами. Следовательно, всего существует 4*5*5 = 100 трехзначных чисел, удовлетворяющих условию задачи.

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

Добавим, например, к задаче 2 такое условие: один из супов молочный, а одно из вторых блюд — рыбное, и после молочного супа есть его не рекомендуется. В таком случае разным супам будет соответствовать уже разное количество вариантов вторых блюд. При новом условии дерево возможных вариантов уже не будет «правильным» и правило умножения применять нельзя.

У Портоса есть сапоги со шпорами и без шпор, четыре разных шляпы и три разных
плаща. Сколько у него вариантов«одеться по-разному?

В кружке 6 учеников. Сколькими способами можно выбрать старосту кружка и его

Четверо ребят должны дежурить в классе четыре дня подряд по одному дню
каждый. Сколькими способами можно составить расписание их дежурств?

Концерт состоит из 5 номеров. Сколько имеется вариантов программы этого
концерта?

В автохозяйстве 1001 автомобиль. Для их регистрации выделены номера
К***ОД50 (вместо * ставится любая цифра от 0 до 9). Хватит ли этих номеров на все
автомобили хозяйства?

Сколько существует шестизначных чисел, у которых:

а) третья цифра — 3;

б) последняя цифра — четная;

в) на нечетных местах стоят нечетные цифры;

г) на нечетных местах стоят четные цифры?

10. Для передачи текста по радио и телеграфу используется азбука Морзе, в которой
каждая буква состоит из точек и тире. Например, буква Е обозначается точкой «.», а буква

Э — набором из пяти знаков «..—..». Достаточно ли наборов от одного до пяти знаков для обозначения всех букв русского алфавита и всех цифр? Почему букву Е решили обозначить одним знаком, а букву Э — пятью?

11. Саша и Даша решали задачу: «В спортивном клубе 5 пловцов имеют лучшие
результаты. Сколькими способами можно составить из них команду из двух человек для
участия в соревнованиях?»

Саша рассуждал так: «Есть 5 способов выбрать первого участника команды, при этом остается 4 способа выбора второго участника. Применим правило умножения 5x4 = 20 Итого — 20 способов

Даша занумеровала всех пловцов и выписала все возможны варианты команды. У нее получилось всего 10 вариантов: 12; 13; 14; 15; 23; 24; 25; 34; 35; 45. Кто из ребят прав?

12. В футбольном чемпионате принимают участие 15 команд. Сколько всего игр
будет сыграно на этом чемпионате, если:

а) каждая команда с остальными участниками играет на «своем» и на «чужом» поле;

б) каждая команда сыграет с каждой только один раз?

В каком случае можно применить правило умножения, а в каком нельзя? Почему?

Решение комбинаторных задач

Вы уже умеете решать комбинаторные задачи методом полного перебора. Однако когда чисел или предметов много, осуществлять полный систематический перебор — это очень долгая и довольно скучная работа.

Гораздо эффективней такие комбинаторные задачи решаются с помощью рассуждений.

■ Пример 1. Сколько существует различных вариантов кода, если код
состоит из трех цифр?

Первой в коде может стоять любая из десяти цифр. При каждом выборе первой цифры на второе место также можно поставить любую из десяти цифр. Значит, если бы код состоял из двух цифр, было бы 10 • 10 = 102 вариантов кода.

Продолжая рассуждение, легко понять, что для каждого набора первых двух цифр кода есть десять возможностей выбрать его третью цифру. Значит, всего будет 10 • 10 • 10 = 103 различных вариантов кода из трех цифр.

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

Как и прежде, первой в коде может стоять любая из десяти цифр. Но вторая цифра кода уже не может совпадать с первой. Поэтому для каждого выбора первой цифры остается только девять возможностей выбрать вторую цифру. Значит, всего будет 10*9 вариантов выбора первых двух цифр кода.

Рассуждая точно так же, замечаем, что для каждого набора первых двух цифр остается восемь вариантов выбора третьей цифры. Значит, всего будет 10*9*8 = 720 различных вариантов такого кода.

■ Пример 2.В турнире участвовало 16 шахматистов, причем каждый с каждым
сыграл по одной партии. Сколько всего было сыграно партий?

В каждой партии встречаются двое шахматистов. Первым из них может оказаться любой из 16 участников турнира, а вторым — любой из 15 оставшихся. Рассуждая, как в предыдущих примерах, можно подумать, что всего было сыграно 16*15=240 партий.

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

Значит, на «самом деле партий было сыграно вдвое меньше, то есть = 120

партий.

На почте продается 40 разных конвертов и 25 разных марок. Сколько есть вариантов
покупки конверта с маркой?

Сколько существует четырехзначных чисел, составленных из нечетных цифр? из четных
цифр'7 из четырех разных цифр?

Сколько существует пятизначных чисел, которые делятся на 2? на 5? на 10?

Сколько существует вариантов выбрать спикера и вице-спикера парламента, если всего
в парламенте 101 депутат?

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

В компьютере каждый символ кодируется последовательностью, состоящей из восьми
цифр — - нулей и единиц. Например, символ «пробел» закодирован так: 00101000. Какое
наибольшее число символов может быть таким образом закодировано в компьютере?

В чемпионате по настольному теннису участвовало 40 спортсменов, и каждый с каждым
сыграл по одной партии. Сколько всего сыграно партий?

На официальном приеме 50 человек обменялись рукопожатиями. Сколько было сделано
рукопожатий?

Сколько диагоналей у выпуклого двадцатиугольника?

10.Игральный кубик подбрасывают пять раз и записывают число выпавших очков. Результатом эксперимента является последовательность из пяти цифр.

а) Сколько при этом может получиться различных результатов эксперимента?

б) Сколько возможно результатов эксперимента, в которых ни разу не встречается
шестерка?

в) Сколько возможно результатов эксперимента, в которых хотя бы раз встречается
шестерка?

11. Сколько существует четырехзначных чисел, в записи которых встречается хотя бы одна

четная цифра? 12.В латинском алфавите 26 букв. Будем считать «словом» любую последовательность.

состоящую не более чем из 5 букв. Сколько всего таких «слов»? 13.Сколько всего делителей у числа 2 • З2 • 53?

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

■ Пример. В турнире участвуют четыре человека. Сколькими способами могут быть распределены места между ними?

Первое место может занять любой из 4 участников. При этом второе место может занять любой из трех оставшихся, третье — любой из двух оставшихся, а на четвертом месте остается последний участник. Значит, места между участниками могут быть распределены 4#3#2*1=24 способами.

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

В разобранном примере мы фактически подсчитали число всех перестановок для множества из четырех элементов.

А если множество состоит из 10 элементов? Тогда всего будет

10 • 9 • 8 • 7 • 6 • 5 • 4 • 3 • 2 • 1 = 3 628 880 перестановок.

Уже для 10 элементов получается очень большое число перестановок — произведение первых десяти натуральных чисел. А, например, для 20 элементов получается уже такое большое число перестановок — произведение первых двадцати натуральных чисел, —^которое трудно не только со читать, но даже выписать.

В математике есть специальное обозначение для краткой записи произведения нескольких первых натуральных чисел. Например, произведение 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 обозначают 10! Выражение 10! читается так: «Десять факториал».

Факториал можно сосчитать для любого натурального числа.

Например,

2! = 1-2 = 2, 5! - 1 -2 • 3-4-5-120, 15! = 1.-2 • 3/4 • 5 • 6* 7 • 8*9- 10* 11 • 12 • 13 • 14- 15- 1 307 674 368 000.

При этом договорились считать, что 1! = 1.

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

Рассуждения, использованные в разобранном примере, показывают, что число перестановок для множества из 4 элементов равно 4!, точно так же для множества, например, из 10 элементов число перестановок равно 10!, и вообще:

Число перестановок для множества из п элементов равна п!.

1. В конкурсе участвуют 12 школьников. Сколькими способами могут быть
распределены места между ними?

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

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

Анаграмма, как вы уже знаете, — это «слово», полученное из данного слова
перестановкой его букв (но не обязательно имеющее смысл). Сколько существует
различных анаграмм слова «график»? слова «интеграл»?

Из цифр 1, 2, 3, 4, 5 составляются пятизначные числа, в которых все цифры разные.

а) Сколько всего таких чисел?

б) Сколько из них делятся на 5?

в) Сколько из них не делятся на 5?

6. Верно ли, что:

а) 10! =10 • 9! б) 10! = 2! • 5! в) — = 12?

. 11

Делится ли 100! на 47? на 99? на 101?

Сколькими способами можно расставить на полке 10 книг, из которых 4 книги
одного автора, а остальные — разных авторов, так, чтобы книги одного автора стояли
рядом?

Сколькими нулями оканчивается число 100! ?

Интересно знать, что

иногда условие задачи можно понять по-разному, и тогда при переводе условия на математический язык получаются разные задачи, у которых не совпадают ни решения, ни ответы. И это вовсе не значит, что один из получившихся ответов — правильный, а другой — нет.

Давайте исследуем эту проблему на примере комбинаторных задач на «перестановки по кругу».

Сколько, например, существует вариантов расположения шести гостей за шестиместным столом?

 

 

 

 

Эта задача имеет разные решения и, соответственно, разные ответы — в зависимости от того, что понимать под различным расположением гостей за столом.

Если считать, что нам важно, кто сидит на каком стуле, то это простая задача на перестановки, и всего будет 6! = 720 различных вариантов посадить гостей за стол.

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

Это уже совсем другая задача. Теперь расположения, получаемые одно из другого при повороте гостей вокруг стола, надо считать одинаковыми. Ясно, что для любого расположения гостей таких одинаковых вариантов, получаемых друг из друга поворотом, — шесть. Значит, 6! надо разделить на 6. Так как 6! : 6 = 5!, то получается только 120 различных вариантов.

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

1. Сколько существует вариантов рассадить президентов «Большой восьмерки» за восьмиместным круглым столом переговоров?

2. Сколькими способами десять приятелей могут сесть на десятиместную карусель? 3.Двенадцать девочек водят хоровод. Сколькими различными способами они могут вставать в круг.

4. Сколько ожерелий можно составить из 20 различных бусин?