Обобщённое правило произведения

Операции над множествами

Пусть заданы множества A и B.

Объединение множеств A и B – множество А È В ={ x: x Î A или x Î B } (объединение содержит элементы, которые есть или в A, или в B, или в том и другом множестве). (нарисовать с помощью кругов Эйлера). А È В = B È A.

Пересечение множеств A и B – множество А Ç В ={ x: x Î A и x Î B } (пересечение содержит элементы, которые есть одновременно и в A, и в B. (нарисовать). А Ç В = B Ç A.

Дополнение до универсального множества. Если В – универсальное множество, и А Í В, то дополнение ={ x: x Î B и x Ï A }. (нарисовать).

Произведение множеств A и B – множество A x B ={< x, y >: x Î A, y Î B } (множество всех пар, первый элемент которых принадлежит множеству A, второй элемент – множеству B). Мощность произведения A x B равна произведению мощностей A и B (| A x B|=|A|*|B|). Произведение B x A не равно A x B, но их мощности совпадают (B x A ¹ A x B, но | B x A| = |A x B|).

Пример: A ={ a, b, c }, B ={ c, d }, |A|= 3, |B| =2.

А È В ={ a, b, c, d }, А Ç В ={ c }, A x B ={ <a,c>, <a,d>, <b,c>, <b,d>, <c,c>, <c,d> }, B x A ={ <c,a>, <c,b>, <c,c>, <d,a>, <d,b>, <d,c> }, | A x B| =6, | B x A| =6.

Оператор (функция) – правило, определяющее отображение некоторого множества X в некоторое множество Y. Обозначение: F: X ® Y.

Пример: X ={ a, b, c, d }, Y ={▲, ●, ■}. Возможный вариант функции: f (a)=■, f (b)=●, f (c)=■, f(d) =▲.

X Y a ▲ b ● c ■ d

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

Если объект a можно выбрать p способами, а объект b – другими q способами, то выбор “ либо a, либо b ” может быть осуществлен p+q способами. При этом выборы a и b являются взаимно исключающими.

Например, в вазе лежит 3 яблока и 5 груш. Тогда взять из вазы либо одно яблоко, либо одну грушу (взаимоисключающие события) можно 3+5 = 8 способами.

Обобщённое правило суммы

Пусть дано r множеств T_i (i =1,…, r), каждое из которых содержит n_i элементов (T_i - n_i ‑множество), причём множества взаимно не пересекаются: T_i Ç T_j =Æ при i ¹ j. Тогда объединение этих множеств S=T₁ È T₂ È…È T_r есть (n₁+…+n_r)-множество. .

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

Если объект a можно выбрать p способами, и после каждого из таких выборов объект b можно выбрать q способами, то выбор “ a и b ” в указанном порядке может быть осуществлен p·q способами. При этом выборы a и b являются независимыми.

Например, в вазе лежит 3 яблока и 5 груш. Тогда взять из вазы одно яблоко и одну грушу (события происходят совместно) можно 3·5 = 15 способами.

Виды выборок

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

 

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

Обозначим знаком отношение упорядоченности. Тогда запись означает, что a предшествует b, а - a предшествует или совпадает с b.

 

r-перестановка без повторений из n-множества	r-перестановка c повторениями из n-множества	r-сочетание без повторений из n-множества	r-сочетание с повторениями из n-множества

 

Следствие 1.

Так как ,

то .

Следствие 2.

Так как , то .

 

Следствие 3.

Рекуррентная формула для числа беспорядков: .

#

#

Следствие 4.

# По рекуррентной формуле из следствия 3 получаем или . При n =1 получаем . По формуле из следствия 1 получаем . Следовательно, . #

 

Следствие 5.

Ещё одна рекуррентная формула для числа беспорядков: .

# Рассмотрим n элементов x ₁, x₂, …, x_n. Переставим их так, чтобы получить беспорядок. Начнём с x ₁: возьмём x ₁ и подставим его на место i -го элемента (i ¹1). Тогда x_i можно поставить на либо на первое место, либо на какое-то другое, кроме i- го. Если x ₁ стоит на i -м месте, а x_i – на 1-ом, то число таких беспорядков – D_{n -2} (т.е. число беспорядков оставшихся n -2 элементов). Если x ₁ не стоит на первом месте, то такой беспорядок определяется условием:

x ₂ не стоит на 2-м месте,

x ₃ не стоит на 3-м месте,

…

x_{i -1} не стоит на (i -1)-м месте,

x_i не стоит на 1-м месте,

x_{i+ 1} не стоит на (i +1)-м месте,

…

x_n не стоит на n -м месте.

Всего здесь n -1 элемент, то есть число таких беспорядков – D_{n -1}.

Итак, если x ₁ стоит на i -ом месте, то число таких беспорядков D_{n -1}+ D_n-2. Но x ₁ можно поставить на любое из (n -1) мест (кроме 1-го). Для каждой установки x ₁ справедливы приведённые выше рассуждения.

Таким образом, общее число беспорядков – (n -1)(D_{n- 1}+ D_n-2). #

 

Для проверки полученной формулы вычислим количество беспорядков для некоторых значений n по рекуррентной и прямой формулам. По следствию 4, D ₀=1, D ₁=0.

 

Рекуррентная формула	Нерекуррентная формула

 

Для строгого доказательства правильности рекуррентной формулы, проверим ее в общем виде.

.

Из следствия 3 , следовательно, . Тогда

. Подставим этот результат в рекуррентную формулу:

. Получили формулу из следствия 3.

 

 

Обозначим через D_n,r число перестановок, в которых на своих местах остаются r элементов, а остальные (n-r) образуют беспорядок. Ясно, что D_n,n =1 (все элементы на своих местах), и D_n,0=D_n (ни одного элемента нет на своём месте).

Теорема. .

# r элементов, стоящих на своём месте, можно выбрать из n элементов способами. Для каждой такой выборки остальные (n-r) элементов образуют беспорядки, число которых D_n-r. Следовательно, всего таких перестановок .

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

#

 

Пример. Выстраиваем 5 человек в определённом порядке, после чего 3 из них переставляем так, чтобы они не стояли на своих местах. Сколько таких перестановок?

Ответ: если трое не стоят на своих местах, то оставшиеся двое стоят на своих местах, т.е.

.

 

Следствие. .

# Из n элементов можно образовать n! перестановок без повторений.

Среди них будет D_n,0 таких, где ни один элемент не стоит на своём месте;

D_{n ,1} таких, где по одному элементу стоит на своём месте;

D_{n ,2} таких, где по паре элементов стоит на своих местах;

и т.д.;

D_n,n =1 таких, где все элементы стоят на своих местах.

Следовательно, общее число перестановок (n!) равно сумме этих чисел. #

 

1. Теорема о числе перестановок
2. Функция Эйлера. Доказать, что , где n- натуральное число, p-простые делители числа n. Выразить функцию Эйлера через функцию Мебиуса.

Функция Эйлера

Функция Эйлера φ (n), где n – натуральное число, дает количество натуральных чисел, не превышающих n и взаимно простых с n. Иначе говоря, φ (n)= k, где 0< k £ n; (k, n)=1.

Теорема

, где p_i – все простые делители n. ( - произведение по всем простым делителям числа n).

# В теореме Лежандра заменим a_i на p_i, где p_i – простые делители n.

Тогда (так как p_i делят n нацело).

По теореме Лежандра

. #

 

Пример. Определим, сколько чисел, не превышающих 100, взаимно простые с 100. Разложим число 100 на простые сомножители: 100=2·2·5·5=2²5². Таким образом, у числа 100 два простых делителя – 2 и 5. По формуле Эйлера получаем

.

Таким образом, среди первой сотни есть 40 чисел, взаимно простых с 100.

Функция Мебиуса

Функция Мебиуса m (n), где n – натуральное число, принимает следующие значения:

Функция Мебиуса позволяет записать функцию Эйлера в виде суммы:

.

Суммирование идет по всем делителям n (а не только по простым делителям).

 

Пример. Вычислим φ (100), используя функцию Мебиуса.

Все делители 100 – {1, 2, 4, 5, 10, 20, 25, 50, 100}.

m (1) = 1,

m (2) = (-1)¹ = -1 (у двойки один простой делитель – 2)

m (4) = 0 (4 делится на квадрат двойки)

m (5) = (-1)¹ = -1 (у 5 один простой делитель – 5)

m (10) = (-1)² = 1 (у 10 два простых делителя – 2 и 5)

m (20) = 0 (20 делится на квадрат двойки)

m (25) = 0 (25 делится на квадрат пятерки)

m (50) = 0 (50 делится и на 2², и на 5⁵)

m (100) = 0 (100 делится и на 2², и на 5⁵)

Таким образом,

Свойство функции Мебиуса: .

Например, n =100, a Î{1, 2, 4, 5, 10, 20, 25, 50, 100}.

.

 

1. Теорема о числе способов выбора k-элементов, среди которых нет двух соседних, из n элементов, расположенных в ряд. Доказать с помощью получения рекуррентной формулы.
2. Теорема о числе сочетаний с повторениями. Доказать с помощью получения рекуррентной формулы.

 

Шаг 1: Вводим обозначения – обозначим число r-сочетаний с повторениями из n-множества S через f(n,r)

Шаг 2: Начальные условия: f(n,1)=n; f(1,r)=1

Шаг 3: Логические рассуждения

Как правило, из множества S выделяется какой-либо элемент и фиксируется. Чаще всего – первый из ряда.

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

Если содержит, то остальные (r-1) элементов этого r-сочетания (а, значит, r-сочетаний содержащих фиксированный элемент), можно выбрть f(n, r-1) способом.

Если сочетание не содержит, то таких r-сочетаний f(n-1,r).

Т.к. эти случаи взаимно исключают друг друга, то:

f(n,r)= f(n, r-1)+ f(n-1,r)

Шаг 4: Необходимо проверить получившуюся рекуррентную формулу применительно к известному результату.

f(n,0)=1=f(n,1)-f(n-1,1)=n-(n-1)

Шаг 5: Различные построения.

Один из вариантов: последовательно вычислять f(n,2), f(n,3) и т.д. и смотреть есть ли закономерность.

f(n,2)=n(n+1)/2

f(n,3)=n(n+1) (n+2)/6

В общем виде:

f(n,r)=n(n+1)(n+2)….(n+r-1)/r!

Шаг 6: Рекуррентный спуск

Проверка с помощью формулы начальных условий:

f(n,1)=n

f(1,r)=1

 

1. Теорема о числе способов выбора k-элементов, среди которых нет двух соседних, из n элементов, расположенных в круг. Доказать с помощью получения рекуррентной формулы.
2. Биективные отображения. Подстановки
3. Биективные отображения. Подстановки.
4. Производящая функция. Производящая функция (нумератор) и перечисляющая производящая функция для сочетаний без повторений.
5. Производящая функция. Производящая функция (нумератор) и перечисляющая производящая функция для сочетаний с повторениями.
6. Производящая функция. Производящая функция (нумератор) и перечисляющая производящая функция для сочетаний с повторениями и при условии, что в каждом сочетании должен присутствовать хотя бы один элемент каждого вида.
7. Производящая функция. Производящая функция (нумератор) и перечисляющая производящая функция для перестановок с повторениями (неограниченными).
8. Используя производящую функцию доказать…
9. Используя производящую функцию доказать…
10. Числа Стирлинга второго рода. Их комбинаторный смысл. Способы вычисления.
11. Числа Моргана.
12. Числа Каталина.
13. Биномиальные и полиномиальные коэффициенты.

Операции над множествами

Пусть заданы множества A и B.

Объединение множеств A и B – множество А È В ={ x: x Î A или x Î B } (объединение содержит элементы, которые есть или в A, или в B, или в том и другом множестве). (нарисовать с помощью кругов Эйлера). А È В = B È A.

Пересечение множеств A и B – множество А Ç В ={ x: x Î A и x Î B } (пересечение содержит элементы, которые есть одновременно и в A, и в B. (нарисовать). А Ç В = B Ç A.

Дополнение до универсального множества. Если В – универсальное множество, и А Í В, то дополнение ={ x: x Î B и x Ï A }. (нарисовать).

Произведение множеств A и B – множество A x B ={< x, y >: x Î A, y Î B } (множество всех пар, первый элемент которых принадлежит множеству A, второй элемент – множеству B). Мощность произведения A x B равна произведению мощностей A и B (| A x B|=|A|*|B|). Произведение B x A не равно A x B, но их мощности совпадают (B x A ¹ A x B, но | B x A| = |A x B|).

Пример: A ={ a, b, c }, B ={ c, d }, |A|= 3, |B| =2.

А È В ={ a, b, c, d }, А Ç В ={ c }, A x B ={ <a,c>, <a,d>, <b,c>, <b,d>, <c,c>, <c,d> }, B x A ={ <c,a>, <c,b>, <c,c>, <d,a>, <d,b>, <d,c> }, | A x B| =6, | B x A| =6.

Оператор (функция) – правило, определяющее отображение некоторого множества X в некоторое множество Y. Обозначение: F: X ® Y.

Пример: X ={ a, b, c, d }, Y ={▲, ●, ■}. Возможный вариант функции: f (a)=■, f (b)=●, f (c)=■, f(d) =▲.

X Y a ▲ b ● c ■ d

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

Если объект a можно выбрать p способами, а объект b – другими q способами, то выбор “ либо a, либо b ” может быть осуществлен p+q способами. При этом выборы a и b являются взаимно исключающими.

Например, в вазе лежит 3 яблока и 5 груш. Тогда взять из вазы либо одно яблоко, либо одну грушу (взаимоисключающие события) можно 3+5 = 8 способами.

Обобщённое правило суммы

Пусть дано r множеств T_i (i =1,…, r), каждое из которых содержит n_i элементов (T_i - n_i ‑множество), причём множества взаимно не пересекаются: T_i Ç T_j =Æ при i ¹ j. Тогда объединение этих множеств S=T₁ È T₂ È…È T_r есть (n₁+…+n_r)-множество. .

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

Если объект a можно выбрать p способами, и после каждого из таких выборов объект b можно выбрать q способами, то выбор “ a и b ” в указанном порядке может быть осуществлен p·q способами. При этом выборы a и b являются независимыми.

Например, в вазе лежит 3 яблока и 5 груш. Тогда взять из вазы одно яблоко и одну грушу (события происходят совместно) можно 3·5 = 15 способами.

Обобщённое правило произведения

Пусть дано r множеств T_i (i =1,…, r), каждое из которых содержит n_i элементов (T_i - n_i ‑множество), причем неважно, пересекаются ли T_i или нет. Осуществим выбор элементов последовательно из множеств T_i.

Выбирая из Т ₁, получим множество М ₁ – множество всех возможных выборок по одному элементу из Т ₁. (М ₁ – n ₁-множество). М ₁ =Т₁

Выбирая сначала из Т ₁, потом из Т ₂, получаем множество М₂ упорядоченных пар элементов из Т ₁ и Т ₂ (М ₂ – n ₁× n ₂-множество). М ₂= Т ₁x Т ₂= M ₁x Т ₂.

Аналогично М ₃= Т ₁x Т ₂x Т ₃= M ₂x Т ₃ – множество упорядоченных троек (n ₁× n ₂× n ₃-множество); М ₄= Т ₁x Т ₂x Т ₃x Т ₄= M ₃x Т ₄ – n ₁× n ₂× n ₃× n ₄-множество; …; М_r = M_r-1 x Т_r – n ₁× n ₂× … × n_r -множество. То есть произведение r множеств есть n ₁× n ₂× … × n_r -множество.

.

 

 

1. Выборка. Виды выборок. Примеры. Упорядоченные выборки. Теоремы о числе упорядоченных выборок без повторений. Доказательства. Следствия.

Виды выборок

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

 

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

Обозначим знаком отношение упорядоченности. Тогда запись означает, что a предшествует b, а - a предшествует или совпадает с b.

 

r-перестановка без повторений из n-множества	r-перестановка c повторениями из n-множества	r-сочетание без повторений из n-множества	r-сочетание с повторениями из n-множества