Комбинаторика для вычисления события. Бином Ньютона

Для формулирования и решения задач по комбинаторике используют следующие конфигурации: перестановки, размещения, сочетания.

Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое число (номер элемента) от 1 до n, где n - число элементов множества.

Перестановка

Пусть мы имеем некое упорядоченное множество N состоящее из n различных элементов. Перестановкой из n элементов называется такой набор элементов множества, которые отличаются от исходного лишь порядком элементов. Обычно перестановка обозначается как Pn и рассчитывается по формуле:

Pn = n!

Пример:

Найти число перестановок множества, состоящего из трех элементов: A, B, C.

Согласно формуле, количество перестановок будет равно 3! = 6.

Действительно, это наборы (ABC),(ACB),(BAC),(BCA),(CAB),(CBA).

Размещение

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

begin mathsize 12px style A subscript n superscript k equals fraction numerator n factorial over denominator open parentheses n minus k close parentheses factorial end fraction end style

Пример:

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

Согласно формуле, количество размещений будет равно 4!/(4-2)! = 24/2 = 12.

Действительно, это наборы (AB),(BA),(AC),(CA),(AD),(DA),(BC),(CB),(BD),(DB),(CD),(DC).

Сочетание

Пусть мы имеем некое упорядоченное множество N состоящее из n различных элементов. Сочетанием из n элементов по k будет называться подмножество из k не повторяющихся элементов выбранные из множества, состоящего из n элементов. Подмножества, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений. Обычно сочетание обозначается как Сnk и рассчитывается по формуле:

begin mathsize 12px style C subscript n superscript k equals fraction numerator n factorial over denominator k factorial open parentheses n minus k close parentheses factorial end fraction end style

Пример:

Найти число сочетаний множества, состоящего из четырех элементов: ABCD по два.

Согласно формуле, количество сочетаний будет равно 4!/2!(4-2)! = 24/4 = 6.

Действительно, это наборы (AB),(AC),(AD),(BC),(BD),(CD).

Свойства сочетаний:

    1. Сn0 = 1.
    2. Сnk = Сnn - k.
    3. Сnk = Сn - 1k - 1 + Сn - 1k
    4. Сn0 + Сn1 + Сn2 + ... + Сnn - 1 + Сnn = 2n.

Сочетание играет важную роль в математике. В частности, он используется в биноме Ньютона.

Бином Ньютона

Бином Ньютона - это отношение, позволяющая представить выражение (a + b)n (n ∈ Z+) в виде многочлена, а именно:

(a + b)n = an + Сn1an - 1b + Сn2an - 2b2 + ... + Сnkan - kbk + ... + Сnn - 1abn - 1 + bn.

Числа Сn1Сn2, ... , Сnn - 1 называются биномиальными коэффициентами.

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

 

0

1

1

1 1

2

1 2 1

3

1 3 3 1

4

1 4  6  4 1

5

1 5 10 10 5 1

6

1 6 15 20 15 6 1

7

1 7 21 35 35 21 7 1

8

1 8 28 56 70 56 28 8 1

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

 

Пример:

Представить в виде многочлена (a + 1)4.

Согласно таблице, в случае четвертой степени коэффициенты результирующего многочлена будут равны 1, 4, 6, 4, 1.

И, действительно (a + 1)4 = a4 + 4a3 + 6a2 + 4a + 1.

Вопросы к конспектам

На вечеринку пришло 13 пар. Каждый мужчина пожал руку всем, кроме своей собственной жены. Но женщины не пожимали руки друг другу. Найдите, сколько всего было рукопожатий. Чему равна сумма цифр этого числа?   
При двукратном бросании игрального кубика в сумме выпало 6 очков. Найдите вероятность того, что в первый раз выпало меньше 3 очков.
Последнее изменение: Среда, 1 Февраль 2017, 18:32