Комбинаторика. Комбинаторные объекты

❤tt♣✿✴✴♠❛t❤❝②❜✳❝s✳♠s✉✳s✉

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

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

Упорядоченная (n, k)– выборка без повторений называется (n, k)– размещением (перестановкой) или размещением из n элементов по k.
Упорядоченная (n, k)– выборка с повторениями называется (n, k)– размещением с повторениями.
(n, n)– размещение без повторений называется перестановкой из n элементов.
Неупорядоченная (n, k)–выборка без повторений называется (n, k) -сочетанием или сочетанием из n элементов по k, другими словами, это k–элементное подмножество множества А.
Неупорядоченная (n, k)– выборка с повторениями называется (n, k)– сочетанием с повторениями.

Например, рассмотрим множество A ={a1,a2,a3}. Составим выбор из трех элементов по два (3,2):
Размещения - Повторения не разрешены, порядок существенен (a1, a2), (a2, a1), (a2, a3), (a3, a2), (a1, a3), (a3, a1).
Размещения с повторениями - Повторения разрешены, порядок существенен (a1,a1), (a1,a2), (a2,a1), (a2,a2), (a1,a3), (a3,a1), (a2,a3), (a3,a2), (a3,a3).
Сочетания - Повторения не разрешены, порядок несущественен (a1, a2), (a1, a3), (a2, a3).
Сочетания с повторениями - Повторения разрешены, порядок несущественен из (a1, a1), (a1, a2), (a1, a3), (a2, a2), (a2, a3), (a3, a3).
Перестановки из трех элементов − это следующие упорядоченные без повторений (3,3)-выборки: (a1,a2,a3), (a1,a3,a2), (a2,a1,a3), (a2,a3,a1), (a3,a1,a2), (a3,a2,a1).

Очень многие комбинаторные задачи решаются с помощью определения мощности множеств: равенства, суммы и произведения.
Правило равенства. Если между конечными множествами A и B есть взаимно однозначное соответствие, то
.
Правило суммы. Если A и B – конечные множества и , , то . .
Правило произведения. Для любых конечных множеств A и B имеет место равенство :

Правило суммы:
n(A∪B)=n(A)+n(B), n-мощность множеств
n(A) - число элементов во множестве
Пример: На одной полке книжного шкафа стоит 45 различных книг, а на другой – 55 различных книг (и не таких, как на первой полке), сколькими способами можно выбрать одну книгу из стоящих на этих полках? Решение:
n(A)=45(книги первой полки)
n(B)=55(книги второй полки)
n(AυB)=n(A)+n(B)=45+55=100

Правило суммы
Если элемент х может быть выбран k способами, а элемент у может быть выбран n другими способами,
тогда выбор элемента х либо у может быть осуществлен
( k+n ) способами.
Правило произведения
Пусть набор (х, у) образуется в результате последовательного выбора элементов х и у , причем элемент х может быть выбран k способами, и при каждом выборе элемента х элемент у может быть выбран n способами,
тогда выбор всех упорядоченных пар (х, у) может быть осуществлен n⋅ k способами.

Правило суммы – частный случай формулы включений и исключений. Если рассматривать А и B как множества исходов, то | A| = n1, |B|=n2; а поскольку события А и B не связаны с друг другом, то можно считать, что соответствующие множества не пересекаются .
Тогда, по формуле включений и исключений
т.е. множество содержит n1+n2 элементов.
Это означает, что имеется возможность n1+n2 исходов события А или B.
Правило произведения. Пусть А1 множество n1 исходов первого события, А2 – множество n2 исходов второго события и т.д. Тогда любую последовательность k событий можно рассматривать как элемент декартова произведения , чья мощность равна
= n1 *n2 *…*nk

Задача 4. Сколько существует двузначных четных чисел с разными цифрами?

Задача 4. Сколько существует двузначных четных чисел с разными цифрами?
Решение. Пусть α = α1α2 − двузначное четное число, у которого все цифры различны. Тогда α2∈ {0,2,4,6,8} ,а
α1∈{1, 2, 3, 4, 5, 6, 7, 8, 9} \ {α2}.
Если α1 − нечетная цифра, т.е. α1∈{1, 3, 5, 7, 9}, получаем, что первая цифра α1 может быть выбрана 5 способами.
При каждом выборе первой цифры α1, вторая цифра α2 может быть выбрана 5 способами.
По правилу произведения получим, что существуют 5 ⋅ 5 = 25 двузначных четных чисел, у которых первая цифра нечетная.
Если α1 − четная цифра, тогда α1∈{2, 4, 6, 8},
а α2∈{0, 2, 4, 6, 8} \ {α1}, т.е. элемент α2 может быть выбран 4 способами.
По правилу произведения, число α может быть выбрано
4 ⋅ 4 = 16 способами.

Задача 5. Сколько существует четырехзначных чисел, делящихся на 5, у которых все цифры различны?

А –первая буква французского слова arrangement, что означает размещение, приведение в порядок

Задача 5. Сколько различных четырехбуквенных «слов» можно составить, используя буквы а,f,c,o,n,e, если под «словом» понимать любую последовательность неповторяющихся букв.
Решение. Имеем дело с подсчетом числа размещений без повторений. Следовательно,

P – первая буква французского слова
permutation что означает перестановка

Размещение с повторениями из n элементов множества M по k - это всякая конечная последовательность, состоящая из k членов данного множества M,
все k элементов которой не обязательно различны.
Два размещения с повторениями считаются различными, если хотя бы на одном месте они имеют различные элементы множества M.
Возьмем буквы Б, А, Р. Какие размещения из этих букв, взятых по две, можно получить?
Сколько таких наборов получиться, если буквы могут повторяться?
Получатся наборы: ББ, БА, БР, АА, АБ, АР, РР, РБ, РА.

Сколькими способами из колоды в 36 карт можно вытащить 5 карт так, чтобы среди них были три карты червовой масти и две крестовой масти?
Решение. Всего в колоде имеем по 9 карт каждой из 4 мастей. Три карты червовой масти можем вытащить
способами, а две карты крестовой масти можно
вытащить способами.
По правилу произведения получаем, что существует
* способов вытащить из колоды 5 карт определенным образом.

Сочетание с повторением
С
m
n
=
С
n
n
+m-1
В магазине есть 5 белых роз, 6 чайных, 4 жёлтых, 2 бордовых. Сколькими способами можно составить букет из этих роз?
С
9
17
=
С
17+9-1
17
=
25!
17!*8!
=
25*24*23*22*21*20*19*18
8*7*6*5*4*3*2
360525

Основные свойства сочетаний
ФОРМУЛА СИММЕТРИИ
ФОРМУЛА СЛОЖЕНИЯ
ЧИСЛО ВСЕХ ПОДМНОЖЕСТВ
N-ЭЛЕМЕНТНОГО МНОЖЕСТВА

Перестановки с повторениями
Число различных перестановок, которые можно построить из n элементов, среди которых находятся
n1 - элементов первого типа,
n2 - элементов второго типа,…,
nk - элементов k-го типа равно

Число элементов в каждой перестановке равно
Поэтому если бы все элементы были различны,
то число перестановок равнялось бы . Но из-за того, что
некоторые элементы совпадают, получится меньшее число перестановок. Возьмем перестановку
В которой сначала выписаны все элементы первого типа, потом все элементы второго типа,…,наконец, все элементы k-го типа. Элементы первого типа можно переставлять с друг другом способами. Но так как все эти элементы одинаковы, то такие перестановки ничего не меняют. Точно также ничего не меняют перестановок второго типа и т.д.

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

ПРИМЕР:
Сколько различных слов можно построить перестановкой букв в слове «лаваш»?
Слово «лаваш» включает по одному экземпляру букв «л», «в», «ш» и два экземпляра буквы «а», а общее количество букв – 5.
По формуле находим:

Задача. У врача 3 таблетки одного лекарства,
2 таблетки – другого и 4 таблетки – третьего.
Сколькими способами он может распределить прием имеющихся таблеток по одной в день?
Решение. Порядок приёма таблеток важен.
Есть повторяющиеся таблетки.
Общее число таблеток 3 + 2 + 4 = 9 равно числу дней приема лекарств.
Решение задачи сводится к нахождению числа всех перестановок с повторениями из 9 элементов:

Задача. Сколько различных слов можно получить перестановкой букв слова ОГОРОД так, чтобы три буквы "о" не стояли бы рядом?
Решение. Общее количество различных слов, полученных перестановкой букв слова огород, равно
Если в каком-то слове все три буквы "о" стоят рядом, то тройную "о" можно считать единым символом, и количество слов, в которых три буквы "о" стоят рядом, равно Р(4) = 4! =24.
В итоге получаем: 120 - 24 = 96.

Найти количество перестановок букв в слове КОЛОБОК .
В слове есть 3 буквы О и 2 буквы К, меняя их , не получим новых слов. Так как , ,
То можем получить всего
разных слов из слова КОЛОБОК