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

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

Выборкой объема k из множества, содержащего n элементов, называется подмножество отобранных любым способом k элементов.

Упорядоченная выборка - порядок расположения элементов выборки имеет значение.

Неупорядоченная выборка - порядок расположения элементов в выборке безразличен.

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

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

Основные виды комбинаций (выборок) - это перестановки, размещения и сочетания.

Правило суммы. Если из множества А элемент можно выбрать способами, после чего выбор элемента можно осуществить другими способами. Тогда выбор одного из элементов , или , можно произвести +способами.

Пример. У одного студента пять книг, а у второго семь.

Сколько есть способов выбора одной книги? 5+7 =12

Правило произведения. Если из некоторого множества А элемент можно выбрать способами, после этого элемента можно осуществить другими способами. Тогда одновременный выбор элементов , , можно осуществить · способами.

Пример. У одного студента пять книг, а у второго семь. Сколькими способами они могут обменяться книгами?

Решение. По правилу произведения число способов для обмена n = k×m = 5×7 = 35.

1⁰. Перестановки из n элементов

Эти группы состоят из n одних и тех же элементов и отличаются лишь порядком элементов. Их количество находится по формуле

P_n= n! =1×2×3×……×n.

Знак! «факториал» означает произведение целых чисел от 1 до n. Например 1! = 1

2! = 1×2= 2

3! = 1×2×3= 6

4! = 1×2×3×4= 24 и т.д.

Внимание 0! = 1 по определению.

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

Решение. Искомое число равно

Пример. Сколько вариантов перестановок можно составить из букв В, О, Д, А?

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

2⁰. Размещения из n элементов по k без возврата

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

Пример. Сколько трехзначных чисел можно составить из семи различных цифр при отсутствии среди них нуля?

Решение. Искомое количество цифр

Пример. В группе из 20 человек нужно выбрать старосту, профорга и физорга. Сколькими способами это можно сделать, если каждый человек может быть избран только один раз?

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

.

Пример. Сколькими способами можно набрать семизначный номер телефона, если все его цифры различны.

Решение. Первую цифру можно набрать 10 способами, вторую – 9 способами, т.к. одна цифра уже использована,... седьмую – 4. Согласно правилу произведения общее число возможных способов набора номера равно =604800.

3⁰. Размещения из n элементов по k с возвращением

Упорядоченные выборки объема k, взятые из n элементов, которые могут повторяться. Количество таких выборок:

.

Пример. Код состоит из четырех цифр. Сколько имеется способов для кодирования.

Решение. Имеем упорядоченные соединения по четыре цифры из десяти с повтором. Это размещения из десяти по четыре с возвращением

Их количество:

.

4⁰. Сочетания из n элементов по k без возврата

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

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

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

.

5⁰. Сочетания из n элементов по k с возвращением

Это неупорядоченные выборки объема k, взятые из n элементов, которые могут повторяться. Их количество:

.

Пример. Сколькими способами можно выбрать а) по три карты, б) по 32 карты из колоды, содержащей 36 игральных карт?

Решение. а) , б)

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

Решение. Поскольку не существенно в каком порядке отобраны кандидатуры число вариантов равно

Дата добавления: 2014-01-15