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

Часто в задачах по комбинаторике встречаются множества, в которых какие-либо компоненты повторяются. Например: в задачах на числа – цифры. Для таких задач при размещениях используется формула , а для сочетаний .

Примеры задач

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

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

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

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

Обезьяну посадили за пишущую машинку с 45 клавишами, определить число попыток, необходимых для того, чтобы она наверняка напечатала первую строку романа Л.Н. Толстого «Анна Каренина», если строка содержит 52 знака и повторений не будет?

Решение: порядок букв имеет значение. Буквы могут повторяться. Значит, всего есть  вариантов.

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

, где n-количество всех элементов, n₁,n₂,…,n_r-количество одинаковых элементов.

Примеры задач

Сколькими способами можно переставить буквы слова «ананас»?

Решение: всего букв 6. Из них одинаковы n₁«а»=3, n₂«н»=2, n₃«с»=1. Следовательно, число различных перестановок равно .