Материал для самостоятельного изучения темы Комбинаторика

4

ТЕМА ДЛЯ САМОСТОЯТЕЛЬНОГО ИЗУЧЕНИЯ:

«СОЧЕТАНИЯ, РАЗМЕЩЕНИЯ, ПЕРЕСТАНОВКИ С ПОВТОРЕНИЯМИ»

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

Задачей комбинаторики можно считать задачу размещения объектов по специальным правилам и нахождение числа способов таких размещений.

Перестановки-соединения, которые можно составить из n предметов, меняя всеми возможными способами их порядок; число их

Количество всех перестановок из n элементов обозначают

Число n при этом называется порядком перестановки

Произведение всех натуральных чисел от n до единицы, обозначают символом n! (Читается "эн - факториал"). Используя знак факториала, можно, например, записать:

1! = 1,

2! = 2•1 = 2,

3! = 3 •2 •1 = 6,

4! = 4 •3 •2 •1 = 24,

5! = 5 •4 •3 •2 •1 = 120.

Необходимо знать, что 0!=1

РАЗМЕЩЕНИЯ С ПОВТОРЕНИЯМИ

Размещения - соединения, содержащие по m предметов из числа n данных, различающихся либо порядком предметов, либо самими предметами; число их.

Пример. В группе ТД - 21 обучается 24 студентов. Сколькими способами можно составить график дежурства по техникуму, если группа дежурных состоит из трех студентов?

Решение: число способов равно числу размещений из 24 элементов по 3, т.е. равно А243. По формуле находим

Ответ: 12144 способа

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

Например: числа 445, 544, 454, 445, 554, 545, 455, 555 - размещения из 2 элементов по 3 с повторениями (по трем различным местам размещаются 2 элемента с повторениями каждого из них любое число раз, но не больше трех)

Обозначение: число размещений из «эн» по «эм» с повторениями -

Подсчет числа размещений с повторениями:

Пример 1. Каждый телефонный номер состоит из 7 цифр. Сколько существует телефонных номеров, не содержащих других цифр, кроме 2, 3, 5 и 7?

Решение: основное множество: {2, 3, 5, 7}

соединение - семизначный телефонный номер

2233447  7443322  порядок важен  задана последовательность  это либо размещения, либо перестановки. Так как семизначный номер может включать не все элементы основного множества (например, номер 2223332 не содержит цифр 5, 7), а лишь некоторые из них, то это размещения в семи разных местах семи цифр, выбранных из четырех разных цифр с повторениями каждой из них любое число раз, но не более семи.

- размещения из 4 по 7 с повторениями

Ответ: 16384

Пример 2. Сколькими способами можно разместить 8 пассажиров в три вагона?

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

Ответ: 6561

Пример 3. Сколько различных 10-буквенных слов можно составить, используя только две буквы: а и b?

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

- размещения из двух по 10 с повторениями.

Ответ: 1024

ПЕРЕСТАНОВКИ С ПОВТОРЕНИЯМИ

Определение: перестановки из n элементов, в каждую из которых входят одинаковых предметов одного типа, одинаковых предметов другого типа и т.д. до одинаковых предметов k-го типа, где , называются перестановками из n элементов с повторениями.

Например: числа 4455, 5544, 4545, 5454, 554, 4554, 5445 - перестановки из 4 элементов с повторениями (в каждую перестановку входят две четверки и две пятерки).

Обозначение: число перестановок с повторениями -

Подсчет числа перестановок с повторениями:

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

Решение: порядок важен и в соединении участвуют все элементы без исключения: зеленые лампочки - 2 раза, а красные - 4 раза. Это перестановки из 6 элементов с повторениями.

способов

Ответ: 15

Пример 5. Сколько всех семизначных чисел, у каждого из которых цифра 6 встречается три раза, а цифра 5 - четыре раза?

Решение: порядок важен и в соединении участвуют все элементы без исключения: шестерки - 3 раза, а пятерки - 4 раза. Это перестановки из 7 элементов с повторениями.

чисел

Ответ: 35

Пример 6. Сколькими способами можно переставить буквы в слове «математика», чтобы получались всевозможные различные анаграммы?

Решение: порядок важен и в соединении участвуют все элементы без исключения: буква «м» - 2 раза, буква «а» - 3 раза, буква «2», буквы «е», «и», «к» - по 1 разу. Это перестановки из 10 элементов с повторениями.

способами

Ответ: 151200

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

Решение: порядок важен и в соединении участвуют все элементы без исключения: буква «м» - 2 раза, буква «а» - 3 раза, буква «2», буквы «е», «и», «к» - по 1 разу. Это перестановки из 10 элементов с повторениями.

способами

Ответ: 151200

СОЧЕТАНИЯ С ПОВТОРЕНИЯМИ

Сочетания-соединения, содержащие по m предметов из n, различающиеся друг от друга, по крайней мере, одним предметом; число их

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

Решение: Так как кнопки нажимаются одновременно, то выбор этих кнопок - сочетание. Отсюда возможно

Ответ: 120 вариантов.

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

Например: соединения {a, a}, {a, b}, {a, c}, {b, b}, {b, c}, {c, c} - сочетания из 3 элементов {a, b, с} по два с повторениями (в соединение могут входить два одинаковых элемента).

Обозначение: число сочетаний с повторениями -

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

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

Решение: порядок выбора монет неважен, и примерами соединений могут являться {5,5,5,5}, {2,2,2,2}, {5,2,5,5} и т.д. Это задача о числе сочетаний из двух видов монет по четыре с повторениями.

способов

Ответ: 5

Пример 9. В кондитерской имеется 5 разных сортов пирожных. Сколькими способами можно выбрать набор из 4 пирожных?

Решение: это задача о числе сочетаний из 5 видов пирожных по 4 с повторениями.

способов

Ответ: 70

Пример 10. Сколько будет костей домино, если в их образовании использовать все цифры?

Решение: число костей домино можно рассматривать как число сочетаний из 10 чисел по 2 с повторениями.

костей

Ответ: 55

Выполнить самостоятельно.

1. Задача №1. Сколькими способами 7 книг разных авторов можно расставить на полке в один ряд? (использовать формулу перестановок)

2. Сколькими способами 5 человек могут занять очередь в железнодорожную кассу?

3. Вычислить (6! - 4!) : 5!

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

5. Номера машин состоят из 3 букв русского алфавита (33 буквы) и 4 цифр. Сколько существует различных номеров автомашин?

6. Турист может посетить города Углич, Ростов, Ярославль, Кострому, Сергиев Посад.

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

7. Сколько экзаменационных комиссий, состоящих из 3 членов, можно образовать из 10 преподавателей? (использовать формулу сочетаний)

8.Из класса, в котором учится 23 человек, необходимо послать на школьную конференцию четырех представителей. Сколько вариантов такого выбора?

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

Сколько возможностей составить команду, если в группе 20 студентов?

4