Современное развитие

В начале XX века начала развиваться комбинаторная геометрия: были доказаны теоремы Минковского — Радона, Радона, Хелли, Юнга, Бляшке, а также строго доказанаизопериметрическая теорема. На стыке топологии, анализа и комбинаторики были доказаны теоремы Борсука — Улама и Люстерника — Шнирельмана. Во второй четверти XX века были поставлены проблема Борсука и проблема Нелсона — Эрдёша — Хадвигера. В 1940-х годах оформилась теория Рамсея. Отцом современной комбинаторики считается Пал Эрдёш, который ввёл в комбинаторику вероятностный анализ. Внимание к конечной математике и, в частности, к комбинаторике значительно повысилось со второй половины XX века, когда появились компьютеры. Сейчас это чрезвычайно содержательная и быстроразвивающаяся область математики.

2вопрос Операции над множествами. Суммой или объединением множеств иназывают множествоС, содержащее все те и только те элементы, которые принадлежат либо множеству А, либо множеству .Обозначают:C=A B.Операцию нахождения объединения называют сложением множеств.

Множество , которому принадлежат те и только те элементы, которые являются как элементами множества, так и элементами множества, называют пересечением множеств и.

Обозначают: C=A B.

Разностью множеств иназывают множество, содержащее те и только те элементы, которые принадлежат множествуи не принадлежат множеству.

Обозначают \.

Операцию нахождения разности множеств называют вычитанием множеств. Вычитание множеств не коммутативно и не ассоциативно, то есть, существуют множества ,итакие, что

\ В \ и \ (\С)(\) \С.

Теорема 3. Число элементов в объединении двух произвольных конечных множеств равно сумме чисел элементов в каждом из них, уменьшенной на число элементов в пересечении данных множеств, то есть n (A B) = n (A) + n (B) – n (A B).

 Докажем сначала, что для произвольных множеств A и B выполняется равенство A B=A (B \ A) (*).

Пусть x произвольный элемент множества A (B \ A). Тогда, по определению объединения, xA или x(B \ A). Применяя определение разности множеств, получим x A (xB xA). Отсюда, по дистрибутивности дизъюнкции относительно конъюнкции, имеем ( xA xB ) (xA xA ). Так как последнее выражение в скобках является тождественно истинным, то xAxB. Откуда по определению объединения получаем xA B. Таким образом, A (B \ A)A B.

Аналогично доказывается включение A B A (B \ A) и по теореме 1 равенство (*) доказано.

Теорема 2. Число элементов в объединении двух непересекающихся множеств равно сумме чисел элементов в каждом из них, то есть, если п(A)=a, n (B)=b и A B=, то n (A B)=a+b.

Замечание. Данное утверждение справедливо для любого конечного числа попарно непересекающихся конечных множеств.

n(A)=a(i=), AA=, ij (i,j=) n( A) =a.

Лемма 3. Для любых множеств А и В справедливо равенство:

n (B \ A) = n (B) – n (A B). (3)

 Согласно лемме 1 B=(AB)(B \ A). Следовательно, n(B)=n((A B)(B \ A)). По лемме 2 (A B)(B \ A)=. Следовательно, по теореме 1, имеем n(B)=n(A B)+n(B \ A).

Декартовым произведением множеств А и В называют множество АВ, состоящее из всех тех и только тех упорядоченных пар, в которых первая компонента является элементом множества А, а вторая – элементом множества В.

Операцию нахождения декартова произведения множеств называют умножением множеств.

Отсюда, n(B \ A)=n(B)–n(A B). Лемма 3 доказана.

Теорема 4. Число элементов в декартовом произведении двух произвольных конечных множеств равно произведению чисел элементов в каждом из них, то есть n (AB)=n (A) ∙ n (B).

 Рассмотрим произвольные конечные множества А и В.

Пусть n(A)=k, n(B)=l. Без ограничения общности рассуждений можно считать, что А={х, х, … , х} и В={y,y, … ,y}.

Запишем элементы А В в виде таблицы:

(x; y)	(x; y)	(x; y)	…	(x; y)
(x; y)	(x; y)	(x; y)	…	(x; y)
…	…	…	…	…
(x; y)	(x; y)	(x; y)	…	(x; y).

В этой таблице k строк и l столбцов. Следовательно, в ней содержится k∙ l элементов.

Таким образом, n(AB)=n(A) ∙ n(B). Теорема доказана.

3 вопрос Правило суммы Если объект а можно выбрать m способами, а объект b можно выбрать k способами, отличными от способа выбора объекта a, то выбор «либо a, либо b» можно осуществить m+k способами.

Пример: Так как имеется 20 видов молочного шоколада с орехами «ALPEN GOLD», то существует 20 способов выбрать одну из плиток шоколада. Аналогично существует 14 способов выбора одной плитки шоколада «ВОЗДУШНЫЙ». Так как требуется выбрать шоколад «либо с орехами, либо пористый», то по правилу суммы получаем (20+14=34) тридцать четыре способа выбора одной плитки шоколада.

Правило произведения Если объект а можно выбрать n способами, а объект b можно выбрать m способами, то выбор «и a, и b» можно осуществить n ∙ m способами.

Пример: Так как существует 9 способов выбора книг по художественной литературе и 5 способов выбора блокнотов, то по правилу произведения «выбор книги и блокнота» («и a, и b») можно осуществить (9∙5=45) сорока пятью способами.

Ответ: 45 способов.

4 вопрос Факториал – это функция, определённая на множестве целых неотрицательных чисел , значение которой равно произведению целых неотрицательных чисел от 1 до данного числаn, то есть 1∙2∙3∙ …∙n; Обозначают символом n!.

По определению 0! = 1, 1! = 1.Обозначение n! впервые использовал французский математик Христиан Крамп (1760 – 1826 гг.) в 1808 году.

Перестановки без повторений. Определение. Упорядоченные подмножества длины n, составленные из элементов n-элементного множества, называют перестановками без повторений.

Число всех таких перестановок обозначают символом Р.

Теорема 6. Число различных перестановок из n элементов равно произведению последовательных натуральных чисел от 1 до n включительно, то есть Р=1 ∙2 ∙ 3 ∙ … ∙n=n!

При упорядочении n – элементного множества, какой-то элемент получит номер 1, какой-то номер 2 и так далее, какой-то из элементов получит номер n. Номер 1 может получить любой из элементов множества. Значит, выбор первого элемента можно осуществить n способами. Вторым может быть любой из оставшихся элементов, а значит, его можно выбрать (n – 1) способами. Третий элемент можно выбрать (n – 2) способами и т.д. Наконец, предпоследний можно выбрать двумя способами, а последний элемент только одним способом. По правилу произведения получаем, что общее число всевозможных перестановок из n элементов определяется по формуле: Р=n ∙ (n – 1) ∙ (n – 2) ∙ … ∙ 2 ∙ 1=n!..Теорема 6 доказана.

Задача 1. Сколько слов (не обязательно имеющих смысл) можно получить из букв слова «апельсин»?Р₈=8!=1  2  3  4  5  6  7  8=40320 (перестановок).

5 вопрос Размещения без повторений. Определение. Всякое упорядоченное k – элементное подмножество n – элементного множества (kn) называют размещением из n элементов по k элементов.

Число различных размещений из n элементов по k элементов обозначают символом А.

Теорема 7. Число различных размещений из n элементов по k равно произведению k последовательных натуральных чисел, наибольшим из которых является n, то есть

А=n ∙ (n – 1) ∙ (n – 2) ∙ … ∙ (n – k + 1) или .

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

На второе место элемент можно выбрать (n–1) способами, на третье – (n–2) способами и так далее. На последнее k-ое место можно поставить любой из оставшихся n–(k–1)=n–k+1 элементов.

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

А=n ∙ (n – 1) ∙ (n – 2) ∙ … ∙ (n – k + 1).

Последнюю формулу можно записать иначе. Умножим и разделим правую часть равенства на 1 ∙ 2 ∙ 3 ∙ … ∙ (n – k), тогда

= ==.доказана.

Задача 1. Сколькими способами можно распределить 5 путёвок в различные дома отдыха, если отдохнуть желают двенадцать человек?

Решение. Так как из 12 человек надо выбрать 5, а затем распределить между ними различные путёвки, то искомое число способов определяется по формуле: А = .

А===8 ∙ 9 ∙ 10 ∙ 11 ∙ 12=95 040 (способов).

Ответ: 95 040 способов.

6 вопрос Сочетания без повторений. Определение. Всякое k-элементное подмножество n-элементного множества (kn) называют сочетанием без повторений из n элементов по k.

Число различных сочетаний из n элементов по k обозначают символом C.

Теорема 8. Число сочетаний из n элементов по k элементов определяется по формуле: C=.

 Формула для числа сочетаний легко получается из формул для числа размещений и числа перестановок. Действительно, составив сначала все сочетания из n элементов по k, а затем, переставив всеми возможными способами элементы, входящие в каждое сочетание, получим все размещения из n–элементов по k–элементов. Но из каждого такого сочетания можно составить k! перестановок. То есть справедлива формула:

k! C=A C==.Теорема 8 доказана.

а) ;

б) ;

в) ;

г) .

д) Правило симметрии.

Если 0 k n, то верно равенство: C=C.

 Известно, что C=.

Найдём C===.

Следовательно, C=C.

Утверждение доказано.

е) Для k,n: 0k n, верно равенство:

(n + 1) C=(k + 1) C.

(n + 1) C==;

(k + 1)C==== =.

Следовательно, (n + 1) C=(k + 1) C.

Утверждение доказано.

ж) Правило Паскаля.

k, n: 0 k n верно равенство: C=C + C.

Найдем C:

C===;

Найдем C: C===.

Найдём C + C:

C + C=+==

= ==C.

7 вопрос Перестановки с повторениями

Определение. Перестановкой с повторениями из m элементов состава k₁, k₂,…,k_m называют кортеж длины суммы k₁+k₂+…+k_m, где k₁ – число повторений одного элемента множества, k₂ – число повторений другого элемента множества и т.д., k_m – количество повторений оставшегося элемента множества.

Обозначают: .

Теорема 10. Число различных перестановок с повторениями данного состава (n₁, n, ..., n) вычисляют по формуле

, где n =n₁ +n+...+ n_т.

 Рассмотрим одну перестановку и заменим в ней все одинаковые элементы разными. Тогда число различных перестановок, которые можно составить из рассматриваемой нами перестановки, по правилу произведения равно n₁, n, ..., n. Проделав это для каждой перестановки, получим n! перестановок.

Следовательно, ∙n₁!∙n₂∙…∙n_m! = n!.

Теорема доказана.

Задача. Сколькими способами можно расставить белые фигуры: 2 коня, 2 слона, 2 ладьи, ферзя и короля на первой линии шахматной доски?

Решение. В этой задаче надо найти число кортежей длины 8, имеющих заданный состав (2, 2, 2, 1, 1). Число таких кортежей, то есть перестановок с повторениями, равно 5040.

.

Ответ: 5 040 способами.

8 вопрос Определение. Размещением с повторениями из k элементов по m элементов называют кортеж, составленный из m элементов k-элементного множества. Число всевозможных размещений с повторениями из k элементов по m элементов обозначают .

Теорема 7. Число всевозможных размещений с повторениями из k элементов по m элементов подсчитывают по формуле: .

 Доказательство проведем методом математической индукции по k, где k – число элементов в размещении при фиксированном значении т. Прежде всего заметим, что размещения с повторениями по k элементов могут быть получены из размещений по (k–1) элементу присоединением еще одного элемента. Так как к каждому размещению по (k–1) элементу можно присоединить любой из имеющихся т элементов, то каждое размещение по (k–1) элементу порождает т различных размещений по k элементов, то есть .

1. При k = 1 каждое размещение состоит только из одного элемента, а число элементов равно т, значит, и число размещений равно т. Итак, , что соответствует формуле.

2. Допустим, что для некоторого числа k равенство справедливо.

3. Найдем число размещений с повторениями из т элементов по k + 1. Пользуясь формулой ,

получаем: =т∙m=m.

Таким образом, доказываемая формула справедлива для k=1 и из ее справедливости для некоторого k следует и справедливость для (k+1). Теорема. доказана.

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

Решение. Так как порядок следования цифр в числе существенен, цифры могут повторяться, то это размещения с повторениями из 5 элементов по 3, а их число равно (чисел).

Ответ: 125 чисел.

9 вопрос Определение. Набор из к элементов, составленный из повторяющихся элементов m элементного множества, называют сочетанием с повторениями из m по к.

Сочетание с повторениями из m элементов по к обозначают символом .

Теорема 9. Число всевозможных сочетаний с повторениями из к элементов по m элементов подсчитывают по формуле:

.

 Фактически нам надо выяснить, сколько различных составов могут иметь кортежи длины к из m элементов. Любой состав кортежа длины к из т элементов имеет вид (к₁, к ₂, к₃,... ,к_т), где к₁, к₂, ..., к_m – неотрицательные целые числа, сумма которых равна к. Заменяя каждое из чисел к_j (1<j<к) соответствующим количеством единиц и разделяя нулями единицы, отвечающие различным числам, получаем кортеж из (т –1) нулей и к единиц. При этом каждому составу отвечает одна и только одна запись с помощью нулей и единиц, а каждая такая запись задает один и только один состав. Поэтому число различных составов равно числу перестановок с повторениями из (т –1) нулей и к единиц, то есть

=Р(т–1,к)=.

Теорема доказана.

Задача. В кондитерском магазине продавались четыре сорта пирожных: эклеры, песочные, наполеоны и слоеные. Сколькими способами можно купить 7 пирожных?

Решение. Покупка не зависит от того, в каком порядке укладывают купленные пирожные в коробку. Покупки будут различными, если они отличаются количеством купленных пирожных хотя бы одного сорта. Следовательно, количество различных покупок равно числу сочетаний четырех видов пирожных по семь.

(способов)

Ответ: 120 способов.

10 вопрос Треугольник Паскаля является, пожалуй, одной из наиболее известных и изящных числовых схем во всей математике. Блез Паскаль, французский математик и философ, посвятил ей специальный «Трактат об арифметическом треугольнике». Впрочем, эта треугольная таблица была известна задолго до 1665 года – даты выхода в свет трактата.

В треугольнике Паскаля прослеживаются следующие закономерности.

1. Члены всякой строки треугольника Паскаля сначала возрастают (до середины строки), а затем − убывают.

Например, 1<4<6, 6>4>1 (четвертая строка); 1<5<10, 10>5>1 (пятая строка).

2. Всякая строка треугольника Паскаля симметрична относительно своей середины (то есть члены всякой строки треугольника Паскаля, равноудаленные от ее краев, равны между собой).

Формально это свойство записывается в виде упоминавшегося нами равенства .

3. Сумма членов n-й строки треугольника Паскаля равна 2.

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

4. Всякое непустое множество имеет столько подмножеств с четным числом элементов, сколько и подмножеств с нечетным числом элементов; иными словами, при n≤1

C + C + C + …=C + C + C + …

Данное соотношение получается применением формулы бинома Ньютона к левой части тождества (1 – 1)^п=0.

С помощью утверждения 3 можно конкретизировать:

C + C + C + … = C + C + C + …=2.

5. Крайние члены треугольника Паскаля равны 1. Каждый же из остальных членов равен сумме двух смежных с ним членов, стоящих в предыдущей строке.

Например (см. строку с номером п=4),

4=1 + 3; 6=3 + 3; 4=3 + 1.

В общем случае (при 1≤m≤п) C=C + C.

6. .

Это получается при .

7. .

Получается применением формул и.

Пример. Разложить по формуле бинома Ньютона двучлен

Решение.