Тема 4. Элементы комбинаторики. Схема выбора с возвращением: Размещения, Сочетания, Перестановки с повторением – 4 часа: 2 часа лекции, 2 часа семинарское занятие

Схема выбора с возвращением.

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

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

Если при упорядоченной выборке m элементов из n-элементного множества А выбранные элементы возвращаются обратно и вновь упорядочиваются, то говорят о размещениях с повторениями. В отличие от «традиционных» размещений, размещения с повторениями могут отличаться друг от друга: элементами, порядком элементов, количеством повторений элементов.

Число всех размещений из n элементов по m элементов с повторениями обозначается «А с чертой из n по m» - и вычисляется по формуле:

.

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

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

Число всех сочетаний из n элементов по m с повторениями обозначается символом С с чертой и вычисляется по формуле:

= .

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

=

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

Пусть в упорядоченном множестве с n элементами имеется m различных элементов. Иногда говорят: «пусть множество разбито на несколько, в данном определении – на m - непустых подмножеств». При этом пусть первый элемент повторяется n₁ раз, второй элемент – n₂ раз, …, m-й элемент – n_m раз, причем

n₁ + n₂ + … + n_m = n.

Перестановки из n элементов данного множества называются перестановками с повторениями из n элементов. Число перестановок с повторениями из n, n₁ + n₂ + … + n_m = n элементов обозначается символом Р_n (n₁, n₂, , n) и вычисляется по формуле:

Р_n (n₁, n₂, …, n_m) =

Задачи, рассмотренные на лекции и семинаре. Тема 4.

Схема с возвращением. Перестановки, Сочетания, Размещения

Лекция 4

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

Задача 2–Т4 (для самостоятельного решения). Подсчитайте, сколько трехзначных чисел можно составить из цифр 1, 3, 5.

Задача 3-Т4. Из трех элементов a, b, c составить все размещения по два элемента с повторениями.

Задача 4-Т4 (для самостоятельного решения). Из элементов (цифр) 2, 4, 5 составить все размещения с повторениями по два элемента.

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

а) 2, 5, 7, 8;

б) 0, 1, 9.

Задача 6–Т4. В качестве некоторого пароля можно использовать в любом порядке латинские буквы, цифры и символ подчеркивания. Пароль к регистру нечувствителен. Пользователь составил пароль из 4 знаков. Сколько всевозможных вариантов таких паролей может быть?

Задача 7-Т4. Из трех элементов a, b, c составить все сочетания по два элемента с повторениями.

Задача 8-Т4 (для самостоятельного решения). Из элементов (цифр) 2, 4, 5 составить все сочетания с повторениями по два элемента.

Задача 9–Т4. В продаже имеются пирожные 7 различных видов. Пирожные одного и того же вида считаем неразличимыми. Сколько существует различных способов покупки 12 пирожных?

Задача 10–Т4. Сколько различных слов, каждое из которых состоит из семи букв можно составить из букв слова «КОРОБОК»?

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

Задача 13-Т4 (для самостоятельного решения). У девочки имеется 2 белых бусины, 3 синих и 1 красная. Сколькими способами их можно нанизать на нитку?

Задача 14-Т4. На шести карточках написаны буквы, из которых можно составить слово АНАНАС. Сколько существует различных шестибуквенных слов, которые можно составить при помощи этих шести карточек?

Задача 15-Т4. В почтовом отделении имеются открытки 6 видов. Какова вероятность того, что среди 4 проданных открыток:

а) все открытки одинаковы?

б) различны?