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

Основные формулы комбинаторики

Задачи, в которых речь идет о тех или иных комбинациях объектов, их называют комбинаторными задачами. Область математики, в которой рассматриваются комбинаторные задачи, называют комбинаторикой.

Комбинаторика – область математики, в которой рассматриваются задачи о тех или иных комбинациях объектов.

Правило суммы

Пусть имеется n попарно непересекающихся множеств A₁, A₂,…A_n, содержащих m₁, m₂,…, m_n элементов соответственно. Число способов, которыми можно выбрать один элемент из всех этих множеств, равно

m₁ m₂ … m_n.

Пример. На курсе имеется 3 группы. В первой – 25 человек, во второй – 30, в третьей – 20. Сколькими способами из них можно выбрать одного студента?

Решение. Из первой группы одного человека можно выбрать 25 способами, из второй – 30, из третьей – 20. Чтобы найти ответ, нужно сложить все эти способы:

25 30 20=75.

Ответ: выбрать одного студента из трех групп можно 75 способами.

Правило произведения

Пусть имеется ^.n множеств A₁, A₂,…A_n,содержащих m₁, m_2,,…, m_n элементов соответственно. Число способов, которыми можно выбрать по одному элементу из каждого множества

m₁ ּ m_{2 ּ}…ּ m_n.

Пример. На курсе имеется 3 группы. В первой – 25 человек, во второй – 30, в третьей – 20. Сколькими способами из каждой из них можно выбрать по одному студенту?

Решение. Из первой группы одного человека можно выбрать 25 способами, из второй – 30, из третьей – 20. Чтобы найти ответ, нужно перемножить эти числа:

25ּ30ּ20=15000.

Ответ: для того, чтобы из каждой группы выбрать по одному студенту, существует 15000 способов.

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

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

Факториалом числа n называется последовательное произведение натуральных чисел от единицы до самого числа n:

Примечание: 0!=1.

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

Перестановками из n различных элементов называются размещения из этих n элементов по n. Перестановки - частный случай размещений.

Пример. Сколькими способами можно расставить в шеренгу студентов группы из 25 человек?

Решение. Число способов есть число перестановок из 25 элементов, то есть:

P₂₅ = 25ּ24ּ23ּ…ּ1=25!=1,55ּ10²⁵.

Ответ: расставить в шеренгу студентов группы из 25 человек можно 1,55ּ10²⁵ способами.

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

Различные упорядоченные подмножества по m элементов данного множества, содержащего n элементов, называются размещениями из n по m. Их число равно:

В частности: .

Пример. Из группы, состоящей из 25 человек, надо выбрать шахматную команду из четырех человек на I, II, III и IV доски. Сколькими способами это можно сделать?

Решение. Так как из 25 человек выбираются 4 и порядок важен, то число способов есть число размещений из 25 по 4, то есть:

.

Ответ: выбрать из 25 человек шахматную команду из четырех человек на I, II, III и IV доски можно 303600 способами.

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

Различные неупорядоченные подмножества по m элементов из данного множества, содержащего n элементов, называются сочетаниями из n по m. Их число равно:

В частности, .

Пример. Сколькими способами из группы в 25 человек можно выбрать баскетбольную команду из пяти человек?

Решение. Так как из 25 человек выбираются 5 и порядок не важен, то число способов есть число сочетаний из 25 по 5, то есть:

Ответ: из группы в 25 человек можно выбрать баскетбольную команду 53130 способами.