Размещения и сочетания

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

Размещения. Сочетания

В шахматном турнире участвуют 9 человек. Каждый из них сыграл с каждым по одной партии. Сколько всего партий было сыграно?

• Решим задачу перебором:
• * * * * * * * * *

1 2 3 4 5 6 7 8 9

Первый с 8 – ю, второй с 7 – ю, третий с 6-ю, четвертый с 5-ю, пятый с 4 - мя, шестой с 3 – мя, седьмой с 2 – мя, восьмой с 1-м.

Всего 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 партий было сыграно.

Ответ: 36 партий.

Сколько различных четырехзначных чисел, в которых цифры не повторяются, можно составить из цифр 0,2,4,6?

• Из цифр 0,2,4,6 можно получить Р 4 перестановок.
• Но из этого числа надо исключить те перестановки, которые начинаются с нуля, т.к. натуральное число не может начинаться с цифры 0.

• Число перестановок с нулем в начале равно трём, т.е. Р 3 .
• Значит, искомое число четырехзначных чисел равно Р 4 -Р 3
• Получаем:
• Р 4 -Р 3 = 4!-3!=24-6=18

Имеется 9 различных книг, четыре из которых - учебники. Сколькими способами можно расставить эти книги на полке так, чтобы все учебники стояли рядом?

• Сначала рассмотрим учебники как одну книгу.
• Тогда на полке надо расставить не 9 , а 6 книг.
• Это можно сделать Р 6 способами.
• В каждой из полученных комбинаций можно выполнить Р 4 перестановок учебников.
• Значит, искомое число способов разложения книг на полке равно произведению
• Р 6 · Р 4 = 6!· 4! = 720 · 24 =
• 17 280.

• 11 футболистов строятся перед началом матча. Первым становится капитан, вторым вратарь, а остальные случайным образом.
• а)Сколько существует способов построения, если капитан и вратарь занимают первые места?
• б) Сколько существует способов построения, если первым стоит капитан, а остальные в произвольном порядке?

• а) К В . . . . . . . . .
• Т.к. капитан и вратарь занимают постоянные первые два места, то всевозможных перестановок будет Р 9 = 9!= 9 · 8 · 7· 6 · 5 · 4 ·3 · 2 · 1= 362 880 (способов).
• б)т.к. только капитан занимает постоянное место, то всевозможных перестановок будет Р 10 = 10! = 3 628 800 (способов)

Задачи

• Сколькими способами можно обозначить вершины куба буквами

• На дверях четырех одинаковых кабинетов надо повесить таблички с фамилиями четырех заместителей директора. Сколькими способами можно это сделать?
• Ответы:

A,B,C,D,E, F,G,K ?

• 8! 4! 4!
• 8!
• 4!
• 4!

• В гостинице семь одноместных номеров, и семеро гостей желают в них разместиться, причем трое заранее зарезервировали конкретные номера.

3 гостя занимают конкретные номера, значит, остается 4 гостя

Задачи

• В 9 классе в среду 5 уроков: алгебра, геометрия, физкультура, русский язык, английский язык.
• Сколько можно составить вариантов расписания на этот день?
• Сколько можно составить вариантов расписания, если алгебра и геометрия стоят вместе?

• Р 5 =5!=120
• Сначала рассмотрим вариант алгебру и геометрию как один предмет
• Получается Р 4 =4!
• Алгебра и геометрия Р 2 =2!
• Итого Р 4 *Р 2 =24*2=48

Размещения

• Размещением из n элементов по k (k≤n) называется любое множество, состоящее из любых k элементов, взятых в определенном порядке из данных n элементов.
• Число размещений из n элементов по k

обозначают (читают: «А из n по k»).

• Два размещения из n элементов по k считаются различными, если они отличаются самими элементами или порядком их расположения.

Сколько трёхзначных чисел (без повторения цифр в записи числа) можно составить из цифр 0,1,2,3,4,5,6?

• Если бы среди цифр не было нуля, то число трёхзначных чисел, которые можно составить из этих цифр, равно числу размещений из 7 элементов по 3.
• ===210

• т.к. среди данных цифр есть цифра 0, с которой не может начинаться трёхзначное число, то из размещений из 7 элементов по 3 надо исключить те размещения, у которых первым элементом является цифра 0.
• Их число равно числу из 6 элементов по 2.
• Итого 210-30=180 чисел

Задачи

Из 30 участников собрания надо выбрать председателя и секретаря. Сколькими способами это можно сделать?

На станции 7 запасных путей. Сколькими способами можно расставить на них 4 поезда?

Сочетания

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

Пусть имеются 5 гвоздик разного цвета. Обозначим их буквами a, b, c, d, e. Требуется составить букет из трёх гвоздик. Выясним, какие букеты могут быть составлены.

• Если в букет входит гвоздика а, то можно составить такие букеты: abc, abd, abe, acd, ace, ade.
• Если в букет не входит гвоздика а, но входит гвоздика b, то можно получить такие букеты: bcd, bce, bde.
• Если в букет не входят ни гвоздика а, ни гвоздика b, то возможен только один вариант составления букета: cde.
• Итак, рассмотрены всевозможные способы составления букетов, в которых по – разному сочетаются три гвоздики из данных пяти

Из 15 членов туристической группы надо выбрать трех дежурных. Сколькими способами можно сделать этот выбор?

• Каждый выбор отличается от другого хотя бы одним дежурным. Значит, здесь речь идет о сочетаниях из 15 элементов по 3.

• Трех дежурных можно выбрать 455 способами .

Из вазы с фруктами, в которой лежит 9 яблок и 6 груш, надо выбрать 3 яблока и 2 груши. Сколькими способами можно сделать этот выбор?

• Выбрать 3 яблока из 9 можно способами ,
• а выбрать две груши из 6 можно способами.

Так как при каждом выборе яблок груши так же выбираются , то сделать выбор фруктов, о котором говорится в задаче, можно

способам

Из двух ваз с фруктами, в которых лежит 9 яблок и 6 груш, надо выбрать 3 яблока и 2 груши. Сколькими способами можно сделать этот выбор?

• В этой задаче выбор фруктов происходит независимо друг от друга
• Значит, яблоки мы выбираем способами
• А груши способами
• Всего

Основные формулы

Задачи для самостоятельного решения:

• Учащимся дали список из 10 книг, которые рекомендуется прочитать во время каникул. Сколькими способами ученик может выбрать из них 6 книг?
• В магазине «Филателия» продается 8 различных наборов марок, посвященных спортивной тематике. Сколькими способами можно выбрать из них три набора?
• Сколько существует семизначных телефонных номеров, в которых все цифры различные и первая отлична от нуля?

Ответы

• 210 способами
• 56 способами.
• 544 320 номеров