Изучение основ комбинаторики и теории вероятностей (стр. 3 из 17)

Для двоичной системы счисления (используются только две цифры: 0 или 1) получаем 2⁵ различных числовых последовательностей. Для системы с основанием к и числом разрядов п соответственно получаем:

(1)

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

В общем виде задача ставится следующим образом: имеется kтипов предметов (количество предметов каждого типа неограниченно) и п позиций (ящиков, кучек, разрядов). Требуется определить, сколько разных комбинаций можно составить, если в позициях предметы могут повторяться? Ответ дается формулой (1).

Пример. Сколько разных числовых последовательностей может содержать 10-разрядное слово в троичной системе счисления? В первый разряд можно поставить один из трех символов (0, 1 или 2), во второй разряд - также один из трех символов и т. д. Всего получаем З¹⁰ чисел.

В некоторых случаях имеются ограничения на количество разных предметов, которые можно помещать на позиции. Пусть, например, имеется п позиций и на каждую i-ю позицию можно поставить k_iпредметов. Сколько в этом случае существует разных расстановок предметов по позициям?

Легко обосновывается формула:

(2)

Пример. В эстафете 100+200+400+800 метров на первую позицию тренер может выставить одного из 3 бегунов, на вторую - одного из 5, на третью - одного из 6, на четвертую - единственного бегуна (на каждую позицию выставляются разные бегуны). Сколько вариантов расстановки участников эстафетного забега может составить тренер?

В соответствии с формулой (2) получаем, что число вариантов равно:

.

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

Рассмотрим задачу: Сколько разных числовых последовательностей, длины 5, можно записать с помощью десяти цифр при условии, что в числовых последовательностях не используются одинаковые цифры?

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

1

2

3

4

5

В первый разряд можно поставить одну из 10 цифр (0,1,2,3,4,5,6,7,8,9). Независимо от того, какая цифра помещена в первый разряд, во втором можно поставить только одну из 9 цифр, в третий - одну из 8 цифр и т. д. Всего существует

различных числовых последовательностей, в каждой из которых нет двух одинаковых цифр.

В общем случае, если имеется k позиций и п разных предметов, причем каждый представлен в единственном экземпляре, то количество разных расстановок:

( 3)

В формуле (3) s

означает факториал числа s, т. е. произведение всех чисел от 1 до s. Таким образом, s

=

s.

Пример 1. Из группы в 25 человек требуется выбрать старосту, заместителя старосты и профорга. Сколько вариантов выбора руководящего состава группы? Старосту выбрать можно одним из 25 способов. Поскольку выбранный староста не может быть своим заместителем, то для выбора заместителя старосты остается 24 варианта. Профорга выбирают одним из 23 способов. Всего вариантов:

.

Пример 2. На дискотеку пришло 12 девушек и 15 юношей. Объявлен "белый" танец. Все девушки выбрали для танцев юношей (и никто из них не отказался). Сколько могло образоваться танцующих пар?

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

.

1.3.4. Перестановки без повторений

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

Положим в (3)

, тогда получим

(4)

Пример. К кассе кинотеатра подходит 6 человек. Сколько существует различных вариантов установки их в очередь друг за другом? Расставим 6 человек произвольным образом и начнем их переставлять всеми возможными способами. Число полученных перестановок в соответствии с формулой (4) будет равно 6! = 720.

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

P_n = n!,

где

.

Заметим, что удобно рассматривать 0!, полагая, по определению, 0! = 1.

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

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

Пусть имеется п₁предметов 1-го типа, n₂ предмета 2-го, п_кпредметов

-го типа и при этом п₁+ п₂+...+ п_к = п. Количество разных перестановок предметов

(5)

Для обоснования (5) сначала будем переставлять п предметов в предположении, что они все различны. Число таких перестановок равно п! Затем заметим, что в любой выбранной расстановке перестановка n₁ одинаковых предметов не меняет комбинации, аналогично перестановка n₂ одинаковых предметов также не меняет комбинации и т. д. Поэтому получаем выражение (5).

Пример. Найдем количество перестановок букв слова КОМБИНАТОРИКА. В этом слове 2 буквы «к», 2 буквы «о», 1 буква «м», 1 буква «б», 2 буквы «и», 1 буква «н», 2 буквы «а», 1 буква «т» и 1 буква «р».

Таким образом, число перестановок букв этого слова равно:

Р(2, 2, 1, 1, 2, 1, 2, 1, 1) = 13!/(2! 2! 2! 2!)= 13!/16.

1.3.6. Сочетания без повторений

Если требуется выбрать к предметов из п,и при этом порядок выбираемых предметов безразличен, то имеем

.(6)

Сочетаниями называют комбинации, составленные из n различных элементов по k элементов, которые отличаются хотя бы одним элементом.

Формула (6) может быть получена следующим образом. Выберем по очереди к предметов из п. Число вариантов будет равно

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

Пример 1. Из группы в 25 человек нужно выбрать троих для работы в колхозе. Если выбирать их последовательно, сначала первого, потом второго, потом третьего, то получим

варианта. Но так как нас не интересует порядок выбора, а только состав выбранной бригады, поэтому полученный результат нужно разделить еще на 3!

Пример 2. В середине 60-х годов в России появились две лотереи, которые были названы "Спортлото": лотерея 5/36 и 6/49. Рассмотрим одну из них, например, 6/49. Играющий покупает билет, на котором имеется 49 клеточек. Каждая клеточка соответствует какому-либо виду спорта. Нужно выделить (зачеркнуть) 6 из этих клеточек и отправить организаторам лотереи. После розыгрыша лотереи объявляются шесть выигравших номеров. Награждается угадавший все шесть номеров, пять номеров, четыре номера и даже угадавший три номера. Соответственно, чем меньше угадано номеров (видов спорта), тем меньше выигрыш.

Подсчитаем, сколько существует разных способов заполнения карточек "Спортлото" при условии, что используется лотерея 6/49. Казалось бы, заполняя последовательно номер за номером, получим:

. Но ведь порядок заполнения не имеет значения, тогда получаем:

Эту же задачу можно решить и другим способом. Выпишем все номера подряд и под выбираемыми номерами поставим 1, а под остальными - 0. Тогда различные варианты заполнения карточек будут отличаться перестановками. При этом переставляются 6 предметов одного вида (единицы) и 49 - 6 = 43 предмета другого вида (нули), т. е. опять

Если все участники заполняют карточки по-разному, то в среднем один из примерно 14 миллионов угадает все 6 номеров. А сколько человек в среднем угадают 5 номеров?

Выберем один из угаданных номеров (

) и заменим его на один