Дискретная математика. Комбинаторика. Ерош И.Л. - 4 стр.

UptoLike

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

Рубрика:

1. ОСНОВНЫЕ ПОНЯТИЯ И ТЕОРЕМЫ

КОМБИНАТОРИКИ

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

Рассмотрим задачу: сколько разных 5-разрядных чисел можно со-

ставить из 10 цифр?

Перенумеруем разряды:

1 2 3 4 5

В первый разряд можно поставить одну из 10 цифр. Независимо от

того, какая цифра поставлена, во второй разряд можно также поставить

одну из 10 цифр и т. д. Всего получается 10

различных чисел.

Для двоичной системы счисления (используются только две цифры:

0 или 1) получаем 2

различных чисел. Для системы с основанием k и

числом разрядов n соответственно получаем:

A = k

(1)

n – число позиций (разрядов); k – число элементов в каждой позиции (цифр).

В общем виде задача ставится следующим образом: имеется k ти-

пов предметов (количество предметов каждого типа неограничено) и n

позиций (ящиков, кучек, разрядов). Требуется определить, сколько раз-

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

повторяться? Ответ дается формулой (1).

П р и м е р. Cколько разных чисел может содержать 10-разрядное

слово в троичной системе счисления? В первый разряд можно поста-

вить один из трех символов (0, 1 или 2), во второй разряд – также один

из трех символов и т. д. Всего получаем 3

чисел.

Упражнения

1. Кодовый замок имеет 5 одинаковых ячеек, каждая ячейка мо-

жет быть установлена в одно из 6 устойчивых положений. Сколько