Схема выбора без возвращения (без повторения).




Элементы комбинаторики

 

Комбинаторика – это раздел математики, в котором изучаются задачи выбора элементов из заданного множества и расположения их в группы по заданным правилам, в частности задачи о подсчете числа комбинаций (выборок), получаемых из элементов заданного конечного множества. В каждой из них требуется подсчитать число возможных вариантов осуществления некоторого действия.

Правило умножения. Если из некоторого конечного множества первый объект (элемент х) можно выбрать способами и после каждого такого выбора второй элемент (y) можно выбрать способами, то оба объекта (x и y) в указанном порядке можно выбрать способами. Это правило верно для любого конечного числа элементов.

Пример 1. Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5, если цифры а) не повторяются? б) цифры могут повторяться?

Решение. а) Имеется 5 различных способов выбора цифры для первого места. После того, как первое место занято, осталось 4 цифры для заполнения второго места. Для заполнения третьего места остается выбор из 3 цифр. Следовательно, согласно правилу умножения число трехзначных чисел равно .

б) Если же цифры могут повторяться, то трехзначных чисел будет .

Правило суммы. Если некоторый объект х можно выбрать способами, а объект у можно выбрать способами, причем способы выбора элементов не совпадают, то любой из указанных объектов (х или у) можно выбрать способами. Это правило верно для любого конечного числа элементов.

Пример 2. В студенческой группе 14 девушек и 6 юношей. Сколькими способами можно выбрать для выполнения различных заданий, двух студентов одного пола?

Решение. По правилу умножения двух девушек можно выбрать способами, а двух юношей - способами. Следует выбрать двух студентов одного пола: двух студенток или двух юношей. Согласно правилу сложения таких способов будет 182 + 30 =212.

Существует две схемы выбора элементов () из исходного множества элементов.

 

Схема выбора без возвращения (без повторения).

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

Определение 1. Размещением из элементов по элементов () называется любое упорядоченное подмножество данного множества, содержащее элементов. Размещения – это выборки, состоящие из элементов, которые отличаются друг от друга либо составом элементов, либо порядков их расположения. Число всех размещений из элементов по элементов определяется как .

n!= [n факториал] =1*2*3*4….*n

5!=1*2*3*4*5=120

3!=1*2*3=6

0!=1

Пример 3. Сколько различных слов, состоящих из трех букв, можно образовать из букв слова БУРАН (допускаются слова, не имеющие смысла в русском языке)?

Решение. Искомое число слов равно числу размещений из 5 букв по 3 буквы, т.е. .

Определение 2. Перестановкой из элементов называется размещение элементов по элементов. Перестановки – это выборки, состоящие из элементов и отличающиеся друг от друга только порядком следования элементов. Число всех перестановок из элементов определяется как .

Пример 4. Сколькими способами можно расставить на полке 5 различных книг?

Решение. Искомое число способов равно числу перестановок из 5 книг, т.е. .

Определение 3. Сочетанием из элементов по элементов () называется любое подмножество, содержащее элементов данного множества. Сочетания – это выборки, состоящие из элементов, которые отличаются друг от друга только составом элементов. Число всех сочетаний из элементов по элементов определяется как .

 

 

Можно показать, что имеют место формулы:

(1) ().

(2) .

(3) ().

Формулой (1) удобно пользоваться при вычислении сочетаний, когда . Так, Формула (2) выражает число всех подмножеств множества из элементов.

Числа являются коэффициентами в разложении бинома Ньютона: .

 

Пример 5. Сколькими способами можно выбрать 3 цветка из вазы в которой стоят 10 красных и 4 розовых гвоздики?

Решение. Так как порядок выбора цветов не имеет значения, то выбрать 3 цветка из вазы, в которой стоят 14 гвоздик равно числу сочетаний из 14 гвоздик по 3 гвоздики, т.е.

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-12-29 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: