Материалы для проведения

кружковых занятий

по математике

в 9 классах

по теме

«Комбинаторика»

Составитель:

учитель математики

МАОУ лицей № 14

Бурмистрова А.В.

I. Комбинаторные задачи.

Комбинаторика (от лат. combinatio - соединение) - раздел математики, занимающийся изучением соединений.

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

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

Задача 1.1. Дано 4 жетона: два синих (С) и два красных (К). Какие последовательности (соединения) можно составить из этих жетонов?

Решение. Возможны такие последовательности:

                1) ССКК,

                2) СКСК,

3) СККС,

4) ККСС,

5) КСКС,

6) КССК.

Задача 1.2. Даны жетоны трех цветов (красный - К, желтый - Ж, синий - С). Построить последовательности, состоящие из двух жетонов с повторением цветов или без повторения.

Решение. Возможны такие последовательности:

с повторением и учетом порядка -

        КК, КЖ, КС, ЖК, ЖЖ, ЖС, СК, СЖ, СС;

без повторения с учетом порядка -

        КЖ, КС, ЖК, ЖС, СК, СЖ;

с повторением и без учета порядка -

        КК, КЖ, КС, ЖЖ, ЖС, СС;

без повторения и без учета порядка -

        КЖ, КС, ЖС.

Задача 1.3. Из цифр 1, 2, 3, 4 составить возможные двузначные числа.

Решение. Возможны такие последовательности:

без повторения цифр -

12, 13, 14, 21, 23, 24, 31, 32, 34, 41, 42, 43;

с повторением цифр -

11, 12, 13, 14, 21,22,  23, 24, 31, 32, 33, 34, 41, 42, 43, 44;

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

Решение. 555, 557, 575, 577, 755, 757, 775, 777.                 (8 штук)

Задача 1.5. В школе проводятся соревнования по хоккею. В качестве призов решили использовать мячи (М), ракетки (Р), клюшки (К) и шайбы (Ш). Сколько различных призов можно составить из этих предметов, если каждый награждаемый получает по два различных предмета?

Решение. МР, МК, МШ, РК, РШ, КШ.

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

Решение. МС, МК, СК.

Задача 1.7. Наташа, Данила, Андрей и Маша - лучшие знатоки литературы в классе. На школьную олимпиаду нужно выставить команду из двух человек. Можно ли составить пять различных команд? Сколько различных команд, составленных из одной девочки и одного мальчика, может выставить данный класс?

Решение.         а) НД, НА, НМ, ДА, ДМ, АМ.

                б) НД, НА, МД, МА.

II. Дерево возможных вариантов.

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

Задача 2.1. Составить двузначные числа из цифр 2, 5 и 9.

Решение.                                                 *    (корень дерева)

первая цифра                 2                        5                        9

вторая цифра         2        5        9        2        5        9        2        5        9

Возможные числа: 22, 25, 29, 52, 55, 59. 92, 95, 99.

Задача 2.2. Школьники из Волгограда во время каникул собирались поехать в Москву, посетив по дороге Нижний Новгород. В справочном бюро они получили следующие сведения: из Волгограда в Нижний Новгород можно отправиться на теплоходе (Т) или на поезде (П), а из Нижнего Новгорода в Москву – на самолете (С), теплоходе, поезде или на автобусе (А). Какими различными способами учащиеся могут осуществить свое путешествие?

Решение.         Волгоград                                        *    (корень дерева)

Нижний Новгород                        Т                                П

Москва                        С        Т        П        А        С        Т        П        А

Варианты путешествия: ТС, ТТ, ТП, ТА, ПС, ПТ, ПП, ПА.

Задача 2.3. В палатке имеется три сорта мороженого: рожок (Р), брикет (Б) и эскимо (Э). Наташа и Данила решили купить по одной порции. Сколько вариантов такой покупки существует?

Решение.                                                         *    (корень дерева)

Выбор Наташи                        Р                        Б                        Э

Выбор Данилы                Р        Б        Э        Р        Б        Э        Р        Б        Э

Варианты покупок: РР, РБ, РЭ, БР, ББ, БЭ, ЭР, ЭБ, ЭЭ (9 вариантов).

Задача 2.4. Данила, Андрей и Наташа собрались потренироваться в бросании мяча в баскетбольную корзину. У них только один мяч, и им надо договориться, кто за кем будет бросать мяч. Сколькими способами они могут занять очередь друг за другом?

Решение.                                                 *    (корень дерева)

Первый                Н                                Д                                А

Второй        Д                А                Н                А                Н                Д

Третий        А                Д                А                Н                Д                Н

Варианты покупок: НДА, НАД, ДНА, ДАН, АНД, АДН (6 вариантов).

Дополнительные вопросы к задаче 2.4:

1) Если Наташа предпочитает бросать второй, то какие варианты для этого подходят?

2) Если Андрей хочет бросать за Данилой, то какие из перечисленных вариантов удобны для него?

Задача 2.5. Наташа сшила кукле 10 разных платьев, а Даша сшила своему мишке трое штанишек и четыре футболки. У кого больше разных нарядов – у куклы или у мишки?

Решение.                                                         *         (корень дерева)

Штанишки                        1                                2                                3

Футболки        1        2        3        4        1        2        3        4        1        2        3        4

У мишки 12 вариантов нарядов, у куклы – 10..

III. Виды соединений.

Простейшими соединениями являются размещения, перестановки и сочетания.

1. Размещения (без повторений).

Прежде, чем дать определение размещения, решим две задачи.

Задача 3.1. Даны три элемента: А, Б, В.

Составим из них соединения из одного элемента – это А, Б, В. Такие соединения называются размещениями из трех элементов по одному, их количество в данном случае равно трем.

Составим теперь из этих элементов такие соединения по 2 элемента, которые отличаются друг от друга либо порядком, либо самими элементами. Получим соединения АБ, АВ, БВ, БА, ВА, ВБ. Такие соединения называются размещениями из трех элементов по два, их количество в данном случае равно шести.

Составим из этих элементов соединения по 3 элемента в каждом, отличающиеся либо порядком элементов, либо самими элементами – это АБВ, АВБ, БАВ, БВА, ВАБ, ВБА. Такие соединения называются размещениями из трех элементов по три, их количество в данном случае равно шести.

Задача 3.2. Даны четыре элемента: А, Б, В, Г. Составим из них различного вида размещения.

По одному элементу:        А, Б, В, Г (это размещения их четырех элементов по одному – 4 варианта)

По два элемента:        АБ, АВ, АГ, БА, БВ, БГ, ВА, ВБ, ВГ, ГА, ГБ, ГВ (это размещения их четырех элементов по два – 12 вариантов).

По три элемента:        АБВ, АБГ, АВБ, АВГ, АГБ, АГВ, БАВ, БАГ, БВА, БВГ, БГА, БГВ, ВАБ, ВАГ, ВБА, ВБГ, ВГА, ВГБ, ГАБ, ГАВ, ГБА, ГБВ, ГВА, ГВБ (это размещения их четырех элементов по три – 24 варианта).

По четыре элемента:        АБВГ, АБГВ, АВБГ, АВГБ, АВБГ, АВГБ, БАВГ, БАГВ, БВАГ, БВГА, БГАВ, БГВА, ВАБГ, ВАГБ, ВБАГ, ВБГА, ВГАБ, ВГБА, ГАБВ, ГАВБ, ГБАВ, ГБВА, ГВАБ, ГВБА (это размещения их четырех элементов по четыре – 24 варианта).

Определение. Размещениями называются соединения, содержащие по  элементов из числа данных  элементов (где ) и различающиеся либо порядком элементов, либо самими элементами. Число размещений из  элементов по  элементов обозначается символом .

Задача 3.3. («Четверо вокруг стола»). Сколькими способами можно разместить четырех человек (А, Б, В, Г) вокруг стола, на котором стоят четыре прибора – золотой (З), серебряный (С), мельхиоровый (М), фарфоровый (Ф)?

Решение. Существует четыре способа занять место за самым почетным золотым прибором, то есть  В каждых из этих четырех случаев имеются по три способа занять место за серебряным прибором. Таким образом, занять два места за золотым и серебряным приборами можно  способами, то есть  В каждом из этих двенадцати случаев есть по два способа занять место за мельхиоровым прибором. Значит, имеются  способа занять место за золотым, серебряным и мельхиоровым приборами, то есть  Наконец, оставшегося человека можно усадить только за оставшийся свободным фарфоровый прибор. Итак, существует  способов занять все четыре места, то есть

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

        Число размещений из  элементов по  элементов находят по формуле

        множителей

Задача 3.4. Сколькими способами можно выбрать три лица на три различные должности из 10 кандидатов?

Решение.

Задача 3.5. В пятом классе изучают 11 предметов. Сколькими способами можно составить расписание занятий на понедельник, если в этот день недели должны быть проведены 5 уроков по разным предметам?

Решение.

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

Решение.

Задача 3.7. Сколько трехзначных чисел можно составить из цифр 2, 4, 6, 7, 9?

Решение.

Задача 3.8. Сколько трехзначных чисел можно составить из цифр 0, 2, 4, 6, 7?

Решение.

Задача 3.9. Сколькими способами можно опустить 5 писем в 11 почтовых ящиков, если в каждый ящик опускают не более одного письма?

Решение.

2. Перестановки (без повторений).

        Рассмотрим размещения АБ, БА, составленные из двух элементов А и Б. И содержащие по два элемента. Они отличаются друг от друга только порядком расположения данных элементов. Такие размещения называются перестановками из двух элементов. Их число обозначают символом . Оно равно , то есть .

        Рассмотрим размещения АБВ, АВБ, БАВ, БВА, ВАБ, ВБА, составленные из трех элементов А, Б и В и содержащие по три элемента. Они отличаются друг от друга только порядком расположения данных элементов. Такие размещения называются перестановками из трех элементов. Их число

.

        Перестановки являются частным случаем размещений. Различные перестановки из одного и того же числа элементов отличаются друг от друга только порядком расположения элементов.

Определение. Размещения из  элементов называются перестановками. Число перестановок из  элементов обозначается символом .

Например,  

Произведение натуральных чисел от 1 до   сокращенно обозначается  (произносится «эн факториал»). По определению считается, что

Итак,

Задача 3.10. Сколькими способами можно составить расписание на один день, если в этот день предусмотрено 6 уроков по 6 предметам?

Решение.

Задача 3.11. Сколькими различными способами можно разместить на скамейке 10 человек?

Решение.

Задача 3.12. Сколько различных шестизначных чисел, кратных 5, можно составить из цифр 1, 2, 3, 4, 5, 6 при условии, что цифры в числе не повторяются?

Решение. Цифра 5 должна стоять на последнем месте, следовательно

Задача 3.13. Сколько чисел можно составить из цифр 1, 2, 3, 4, 5, 6, если число начинается: а) с цифры 4, б) с цифр 4 и 5, в) с цифр 4,5 и 6?

Решение. а) однозначных чисел:         1 штука;

двузначных чисел: 4□                        5 штук;

трехзначных чисел: 4□□                  штук;

четырехзначных чисел: 4□□□         штук;

пятизначных чисел: 4□□□□         штук;

шестизначных чисел: 4□□□□□          штук

Всего чисел:

б) двузначных чисел:                         1 штука;

трехзначных чисел: 45□                  штуки;

четырехзначных чисел: 45□□          штук;

пятизначных чисел: 45□□□                 штуки;

шестизначных чисел: 45□□□□          штуки.

Всего чисел:

в) трехзначных чисел:                         1 штука;

четырехзначных чисел: 456□         штуки;

пятизначных чисел: 456□□                  штук;

шестизначных чисел: 456□□□          штук.

Всего чисел:

Замечание к задаче 3.13: если нужно вести речь только о перестановках, то в условии нужно оговаривать, что число должно быть шестизначным.

3. Сочетания (без повторений).

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

Сочетания являются частным случаем размещений. Сочетания – это размещения, которые отличаются друг от друга по крайней мере одним элементом. Перестановка элементов в одном из сочетаний – это то же самое сочетание.

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

АБВ    АБГ    АВГ    БВГ – все различные сочетания, их количество .

АВБ    АГБ    АГВ    БГВ

БАВ    БАГ    ВАГ    ВБГ

БВА    БГА    ВГА    ВГБ

ВАБ    ГАБ    ГАВ    ГБВ

ВБА    ГБА    ГВА    ГВБ

Таких строк столько, сколько можно составить перестановок из трех элементов, то есть

Итак, , отсюда .

В общем виде .

Задача 3.14. В секции занимаются 12 баскетболистов. Сколько различных стартовых пятерок может организовать тренер?

Решение.

Задача 3.15. Сколько вариантов экзаменационных комиссий, состоящих из 7 членов, можно организовать из 14 преподавателей?

Решение.

Задача 3.16. В чемпионате страны по футболу (высшая лига) участвуют 18 команд, причем каждые команды встречаются между собой дважды. Сколько матчей играется в течение сезона?

Решение. В первом круге проводятсяматча. Всего будет сыграно 306 матчей.

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

Решение. а) ; б)

Задача 3.18. Для полета на Марс необходимо укомплектовать следующий экипаж космического корабля: командир, его первый помощник, второй помощник, два бортинженера (обязанности которых одинаковы) и один врач? Командная тройка может быть отобрана из числа 25 готовящихся к полету летчиков, бортинженеры из числа 20 специалистов, в совершенстве знающих устройство космического корабля, а врач – из числа 8 медиков. Сколькими способами можно укомплектовать команду космического корабля?

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

Задача 3.19. Во взводе 3 сержанта и 30 солдат. Сколькими способами можно выделить одного сержанта и трех солдат для патрулирования?

Решение.

Задача 3.20. Вычислить:            

После выполнения вычислений можно отметить, что справедливы равенства:

Перед тем, как рассматривать свойства числа сочетаний, закодируем сочетания из четырех элементов (А, Б, В, Г) по три следующим образом:

1 означает, что буква взята для данного сочетания, а 0 означает, что буква не взята для данного сочетания. Так слово 1110 соответствует сочетанию АБВ, слово 1101 – сочетанию АБГ, 1011 – АВГ, 0111 – БВГ. Чтобы найти все сочетания из четырех элементов по три, надо найти все слова из четырех букв (цифр), в которых три раза стоит 1 и один раз стоит 0.

Задача 3.21. Из четырех элементов (А, Б, В, Г) составили все сочетания по два и закодировали по тому принципу, который изложен выше.

Имеем:         АБ                АВ                АГ                БВ                БГ                ВГ

        1100                1010                1001                0110                0101                0011

Итак число сочетаний из четырех элементов по два совпадает с числом слов из четырех букв (цифр), в которых два раза стоит 1 и два раза стоит 0.

4. Основное свойство числа сочетаний.

Задача 3.22. Имеются 5 ящиков, пронумерованные числами от 1 до 5. Сколькими способами в этих ящиках могут располагаться 3 одинаковых шара, чтобы каждый ящик содержал не более одного шара?

Решение.

 и так далее…

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

        Е        Е        Е        Н        Н

        Е        Е        Н        Е        Н

        Е        Е        Н        Н        Е

        Е        Н        Е        Е        Н        и так далее…

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

Изменим задачу: если требуется определить количество способов, которыми можно расположить 2 шара в 5 ящиках (не более 1 шара ящике), то это количество тоже равно 10, так как

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

Для одного шара                        Для четырех шаров

Е  Н  Н  Н  Н                        Е  Е  Е  Н  Е

Н  Е  Н  Н  Н                        Е  Е  Н  Е  Е

Н  Н  Е  Н  Н                        Е  Н  Е  Е  Е

Н  Н  Н  Н  Е                        Е  Е  Е  Е  Н

Таким образом, мы видим, что  Это свойство сочетаний упрощает вычисления, например,

IV. Треугольник Паскаля.

Заполним таблицу

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

так как существует единственная ситуация, когда нет ящиков и шаров.

Перепишем эту таблицу в виде равнобедренного треугольника:

                                        1

                                          1                1

                        1                2                1

                          1                3                3                1

        1                4                6                4                1

          1                5                10                10                5                1

1        6                15                20                15                6                1

Сумма чисел каждой строки полученного треугольника равна:

     и так далее.

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

        Этот треугольник называется треугольником Паскаля (по имени знаменитого французского философа, математика, физика, писателя Блеза Паскаля, 1623-1662), в трудах которого он встречается. Это название исторически неточно, так как эту таблицу уже знали арабские математики Исясэддин Каши и Омар Хайями (XIII век), а из европейских ученых с нею был знаком итальянский механик и математик Николо Тарталья (1500-1557).

        Сумма чисел в каждой строке:

 - второе свойство числа сочетаний.

К треугольнику Паскаля можно прийти следующим образом. Пусть имеется клетчатая доска:

        → П

Фишка должна из клетки «Старт» прийти в клетку «Финиш». Перемещаться можно по клеткам вверх или вправо. Сколько существует путей, ведущих от старта к финишу?

Есть ли другие пути? Как их найти? С помощью кодирования первые четыре пути запишутся так: П П П В В, П П В П В, П В П П В, В П П П В и так далее, где П – перемещение вправо, В – перемещение вверх.

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

Сколько существует путей, ведущих из клетки (0;0) в произвольную клетку доски?

(0; 0) → (3П; 2В)                10 путей,

(0; 0) → (3П; 1В)                 пути,

(0; 0) → (3П; 4В)                 путей,

(0; 0) → (0; 0)                1 путь (остаться в этой же точке).

Решение этой задачи приводит к треугольнику Паскаля, записанному на клетчатой доске:

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

Решение. Каждый такой путь состоит из 8 горизонтальных и 4 вертикальных единичных отрезков.

Задача 4.2. Сколькими способами можно заполнить карточки «Спортлото» (зачеркнуть 6 номеров из 45)?

Решение. .

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

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

                        АА

        А                АБ

                        АВ

                        БА

☼        Б                ББ

                        БВ

                        ВА

        В                ВБ

                        ВВ

Итак, .

Если из элементов трех видов (А, Б, В) мы будем составлять размещения с повторениями, содержащие по три элемента в каждом, то число таких размещений будет .

                                        ААА

                        АА                ААБ

        А                АБ                ААВ

                        АВ

                        БА

☼        Б                ББ        (остальные размещения не показаны)

                        БВ

                        ВА

        В                ВБ                ВВА

                        ВВ                ВВБ

                                        ВВВ

Задача 5.1. Из элементов двух видов (А, Б) составить размещения с повторениями по 2 элемента в каждом размещении, по три элемента, по четыре элемента. Найти число таких размещений.

Решение.

                        АА

        А                АБ

☼                                        

        Б                БА

                        ББ

                                        ААБ

                                        ААА

                        АА                АБА

        А                АБ                АББ

☼                                                        

        Б                БА                БАА

                        ББ                БАБ

                                        ББА

                                        БББ

Аналогично

Число размещений с повторениями из  элементов по  элементов вычисляется по формуле

Задача 5.2. Сколько трехзначных чисел можно записать с помощью цифр 1, 2, 3, 4, 5?

Решение.

Задача 5.3. Сколько чисел, меньших , можно записать с помощью цифр 7, 6, 4?

Решение. К таким числам относятся все однозначные, двузначные, трехзначные, четырехзначные, пятизначные  числа, составленные из цифр 7, 6, 4. Их количество

Задача 5.4. Сколько чисел, меньших , можно записать с помощью цифр 3, 5, 8?

Решение. К таким числам относятся все однозначные, двузначные, трехзначные, четырехзначные числа, составленные из цифр 3, 5, 8. Их количество

Задача 5.5. Сколько чисел, меньших , можно записать с помощью цифр 5, 7, 3?

Решение. К таким числам относятся все однозначные, двузначные, трехзначные числа, составленные из цифр 5, 7, 3. Их количество равно

Задача 5.6. Сколько чисел, меньших , можно записать с помощью цифр 1, 2, 4, 6?

Решение. К таким числам относятся все однозначные, двузначные, трехзначные, четырехзначные числа, составленные из цифр 1, 2, 4, 6. Их количество

Задача 5.7. Сколько пятизначных номеров можно записать с помощью девяти цифр 1, 2, 3, 4, 5, 6, 7, 8, 9?

Решение.

Задача 5.8. Сколько существует пятизначных номеров:

а) не содержащих цифру 8, б) не содержащих цифры 0 и 8, в) составленных только из цифр 2,3,5,7?

Решение. а)  Исключим номера, начинающиеся с нуля, их количество равно  Остается

б)

в)

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

Составим перестановки из трех элементов А, Б, В.

Их шесть: АБВ, АВБ, БАВ, БВА, ВАБ, ВБА. В этих перестановках элемент Б заменим элементом А. Получим ААВ, АВА, ААВ, АВА, ВАА, ВАА. В этом наборе некоторые перестановки повторяются. Исключив их повторение, получим ААВ, АВА, ВАА. Это и есть перестановки с повторениям, элемент А в каждую перестановку входит два раза. Число перестановок уменьшилось по сравнению с первоначальным и его можно представить в виде  где 2 показывает число одинаковых элементов. Удобнее это записывать так  Поясним эту запись: в обозначении  число 2 показывает, что один из элементов перестановки повторяется дважды, а число 1 показывает, что один из элементов не повторяется; в записи  число 3=2+1 – это число элементов в перестановке.

        Составим перестановки из четырех элементов А, Б, В, Г. Получим 24 перестановки: АБВГ, АБГВ, АВБГ, АВГБ, АВБГ, АВГБ, БАВГ, БАГВ, БВАГ, БВГА, БГАВ, БГВА, ВАБГ, ВАГБ, ВБАГ, ВБГА, ВГАБ, ВГБА, ГАБВ, ГАВБ, ГБАВ, ГБВА, ГВАБ, ГВБА.

Заменим элементы Б и В на элемент А: АААГ, ААГА, АААГ, ААГА, АААГ, ААГА, АААГ, ААГА, АААГ, ААГА, АГАА, АГАА, АААГ, ААГА, АААГ, ААГА, АГАА, АГАА, ГААА, ГААА, ГААА, ГААА, ГААА, ГААА.

Из этого набора выпишем разные перестановки. Их четыре: АААГ, ААГА, АГАА, ГААА. По сравнению с предыдущим набором их число уменьшилось в 3! раз.

Задача 6.1. Сколько слов получится при перестановке букв в слове: а) «ТОЛПА», б) «ТОПОТ», в) «МАТЕМАТИКА»?

Решение. а)

б) перестановка двух букв Т и двух букв О не изменяют слова. Тогда получим  слов.

в)

Задача 6.2. Для премий на математической олимпиаде выделено 3 экземпляра одной книги, 4 экземпляра другой и 8 экземпляров третьей. Сколькими способами могут быть распределены эти премии между тридцатью участниками олимпиады, если каждому вручается не более одной книги?

Решение.

Задача 6.3. Найдите сумму четырехзначных чисел, получаемых при возможных перестановках цифр: а) 1, 1, 4, 4; б) 0, 0, 4, 4.

Решение. а)  - количество различных чисел. Найдем их сумму:

б)

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

Сначала поясним на примере, какие соединения называются сочетаниями с повторениями. Найдем число сочетаний с повторениями из четырех элементов А, Б, В, Г по три элемента:

ААА,        АБВ,                БББ,                БГГ,

ААБ,        АБГ,                ББВ,                ВВВ,

ААВ,        АВВ,                ББГ,                ВВГ,

ААГ,        АВГ,                БВВ,                ВГГ,

АББ,        АБГ,                БВГ,                ГГГ.

Число сочетаний с повторениями обозначается символом . В данном случае мы получили  тогда как

Формула числа сочетаний из  элементов по  элементов с повторениями имеет вид .

Решив предыдущую задачу с помощью этой формулы, находим

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

Задача 7.1. Сколько наборов из 7 пирожных можно составить, если в продаже имеется 4 сорта пирожных?

Решение.

Задача 7.2. Сколько существует различных треугольников, длины сторон которых принимают значения 8 см, 10 см, 12 см, 14 см? Сколько среди них разносторонних, равнобедренных, равносторонних?

Решение. Количество различных треугольников равно

Из них количество разносторонних треугольников равно

Количество равносторонних треугольников равно , а равнобедренных

Задача 7.3. Сколько существует различных треугольников, длины сторон которых принимают значения 5, 6, 7, 8, 9? Сколько среди них разносторонних, равнобедренных, равносторонних?

Решение. 35; 10; 20; 5.