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

Применим выведенную выше формулу для решения задач.

Доказательство.

Доказательство проведем методом математической индукции по числу элементов к при фиксированном значении n.

1. При к=1 каждое размещение с повторениями состоит из одного элемента. Его можно выбрать n способами. Таким образом, =n¹.

2. Предположим, что верно равенство =n^k-1. Размещения с повторениями из n элементов по k можно получить из размещений с повторениями из n элементов по k-1 элементу добавлением любого из n элементов.

По правилу произведения получаем = ∙n=n^k-1 ∙n=n^k

Задача.

Решение.

Из условия задачи следует, что необходимо составить всевозможные комбинации по 4 элемента из данных 10. По формуле размещений с повторением получаем: = 10⁴ = 10 000 вариантов.

Задач.

Сколько в n-ичной системе счисления натуральных чисел, записываемых ровно k знаками?

Решение.

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

Но натуральные числа не могут начинаться с нуля. Поэтому из полученного значения n^k необходимо вычесть количество чисел, запись которых начинается с нуля. Если отбросить от этих чисел первую цифру – ноль, то получим (k–1)-значное число (быть может, начинающиеся с нуля). Таких чисел по формуле для вычисления количества размещений с повторениями существует n^k-1. Значит общее количество k-значных чисел в n-ичной системе счисления равно n^k – n^k-1= n^k(n – 1).

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

Как изменится решение задачи о камере хранения, если известно, что цифры, набираемые на колесиках, различны.

Решение.

Вариантов выбора первой цифры 10 (от 0 до 9). Так как повторения быть не может, то вариантов выбора второй цифры всего 9. Аналогично для выбора третьей цифры остается 8 вариантов, для выбора четвертой – 7. По правилу произведения получаем, что всего комбинаций, в которых все числа различны, 10×9×8×7=5 040.

Данная задача относится к классу задач о размещении без повторений.

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

Количество размещений без повторений обозначают . Общее правило вычисления количества размещений:

=n×(n – 1)×…×(n – k+1)= .

Дата добавления: 2015-01-03