Реферат: Изучение основ комбинаторики и теории вероятностей

Рассмотрим задачу: Сколько разных числовых последовательностей, длины 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. Сочетания без повторений

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