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

(лек. 2 час + прак. занят 2 час + лаб. 4 час. + самос. 12 час)

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

Типичными задачами комбинаторики являются такие разделы как перестановки, разбиения множеств и чисел, биномиальные коэффициенты, производящие функции и т.д., а также алгоритмы генерирования упомянутых комбинаторных объектов. Классической задачей комбинаторики является задача определения числа способов размещения в каком-то количестве «ящиков» так, чтобы были выполнены некоторые условия. Комбинаторика имеет дело с конечными множествами, поэтому ее и называют иногда теорией конечных множеств.

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

Правило произведения. Пусть имеем декартово произведение двух множеств {a,b,c}{1,2,3,4}. Число элементов, которого равно произведению числа элементов первого множества на число элементов второго множества, в дано случае это будет 34 = 12. В общем случае можно сформулировать правило произведения:

Если требуется выполнить последовательно k независимых операций, и каждая может быть выполнена n_i (i =1,2, ,k) способами, то общее число исходов равно их произведению n = n₁ n₂ ... n_k.

Число элементов декартова произведения (мощность) n сомножителей равно произведению числа элементов (мощности) каждого из этих сомножителей.

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

Если элемент x может быть выбран m способами, а элемент y - n способами, то выбор, либо x, либо y может осуществляться m + n способами.

Перечислительная комбинаторика

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

Пусть A – конечное множество, состоящее из n элементов, т.е. мощность этого множества │A│ = card A = n.

Перестановки

Дано множество A. Пусть A – конечное множество, состоящее из n элементов A = {a₁, a₂, …, a_n}, т.е. мощность этого множества │A│ = card A = n.

Перестановкой элементов множества A называется любой кортеж <a₁, a₂, …, a_n> состоящий из n различных элементов множества A.

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

Число перестановок определим исходя из следующего рассуждения. На первом месте в кортеже можно поставить любой из n элементов, на второе место - любой из n-1 оставшихся и т.д. Для последнего места остается единственный элемент. Общее число кортежей n (n-1) (n-2) …2 1, т.е.

Пример.

Сколько трехзначных чисел можно составить из трех цифр {1,2,3}.

Решение

Кортежи будут соответственно равны:

<1, 2, 3>; <1, 3, 2>; <2, 1, 3>; <2, 3, 1>; <3, 1, 2>; <3, 2, 1>, и их число равно

Подчеркнем еще раз, что приведенная формула справедлива, если множество A состоит из разных элементов.

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

Пусть в множестве A имеются одинаковые (повторяющиеся) элементы. Перестановкой с повторениями состава (n₁, n₂, … ,n_k) из элементов (a₁, a₂, … ,a_k) называется кортеж длиной n = n₁ + n₂ + …+ n_k, в который a₁ входит n₁ раз, a₂ входит n₂ раз и т.д. Число таких перестановок

Пример.

Сколько слов можно получить, переставляя буквы в слове «МАТЕМАТИКА»

Решение

Слово «МАТЕМАТИКА» является кортежем длины 10, имеющим состав (2, 3, 2, 1, 1, 1) т.е. буква «М» входит два раза, буква «А» входит 3 раза, буква «Т» входит два раза, а остальные по одному разу. Число слов при перестановке букв слова «МАТЕМАТИКА» будет равно

Дадим другое определение перестановки. На языке множеств это можно представить следующим образом.

Каждое взаимно однозначное отображение f: X —> Y называется перестановкой множества X.

Если т = п, то каждая взаимно однозначная функция f: X —> Y является взаимно однозначным отображением множества X на множество Y. В таком случае [п]_п = п (п-1) (п-2) . . . 1 обозначаем п! (п факториал).

Теорема. Число перестановок n-элементного множества равно п!.

Доказательство следует из предыдущего рассуждения.

Справочные зависимости.

|т|_п = (т- п+1) |т|_п-1

|т|_п = т!/п!

|т|_п = |т + п-1|_п

Размещения

Кортежи длины k (1≤k≤n), состоящие из различных элементов n-элементного множества A (кортежи отличаются один от другого как самими элементами, так и их порядком), называются размещениями из n элементов множества A по k. Число таких размещений обычно обозначается (букваA от французского слова arrangement - размещение) или |n|^k.

Схема выбора состоит в выборе k элементов из n-элементного множества без возвращения. Для этого необходимо совершить k действий: первое действие можно совершить n способами, второе уже n -1 способами, а k-е действие n – (k – 1) способами. Согласно вышеуказанному правилу произведения получаем конечное число перестановок . Умножим и разделим на, получим:

Отличие размещения от перестановки. Если размещения отличаются друг от друга только порядком, так как в каждом из них встречаются по одному разу все элементы множества A, то такие размещения являются перестановками, т.е. .

Пример. Дано A = {1, 2, 3}. Найти все размещения из трех элементов по два и их число.

Решение. <1, 2>; <1, 3>; <2, 3>; <2, 1>; <3, 1>; <3, 2>. Число размещений, как видно равно 6.

Подчеркнем еще раз, что приведенная формула справедлива, если множество A состоит из разных элементов.

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

Пусть во множестве A имеются одинаковые (повторяющиеся) элементы. Размещениями с повторениями из n элементов по k называются кортежи длиной k, составленные из n-элементного множества A. Число этих кортежей обозначают . Черта указывает на возможность повторения элементов

Пример.

Сколько пятизначных телефонных номеров можно составить из элементов множества {0,1,2,3,4,5,6,7,8,9}.

Решение.

Телефонные номера являются кортежами длиной k = 5, составленные из десятиэлементного множества с возвращением, т.е. для каждого из пяти элементов есть девять способов выбора.

Рассмотрим размещения на языке множеств.

Даны множества X, Y, причем \X\ = n, |Y| = m. Сколько существует функций: X —> Y, удовлетворяющих заданным ограничениям?

Элементы множества X соответствуют объектам, элементы множества Y — ящикам, а каждая функция f:. X —> Y определяет некоторое размещение, указывая для каждого объекта ящик, в котором данный объект находится. Другую традиционную интерпретацию получим, трактуя Y как множество «цветов», а f(х) как «цвет объекта х». Наша задача, таким образом, эквивалентна вопросу, сколькими способами можно покрасить объекты так, чтобы были соблюдены некоторые ограничения.

Заметим, что без потери общности можем всегда считать, что Х = {1, ..., п} и Y = {1, ..., т}. Каждую функцию f можно тогда отождествить с последовательностью < f(1) , ,.., f (п)>.

Наша задача имеет самый простой вид, если не накладывается никаких ограничений на размещения. Имеет место следующая теорема.

Теорема 1.1. Если |X| = n, |Y| = m, то число всех функций f: X —> Y равно тⁿ.

Доказательство.

Считая, что Х = {1, ..., п}, сводим нашу задачу к вопросу о числе всех последовательности < y₁ ..., y_n > с членами из m-элементного множества Y. Каждый член последовательности y_i мы можем выбрать т способами, что дает тⁿ возможностей выбора последовательности < y₁ ..., y_n >.

Легко также найти число размещений, для которых каждый ящик содержит не более одного объекта — также размещения соответствуют взаимно однозначным функциям. Обозначим через |т|_п число всех взаимно однозначных функций из n-элементного множества в m-элементное множество.

Упорядоченное размещение

Разместим п объектов по m ящикам так, чтобы каждый ящик содержал бы последовательность, а не множество, как прежде, помещенных в нем объектов. Два размещения назовем равными, если в каждом ящике содержится одна и та же последовательность объектов. Размещения такого типа называются упорядоченными размещениями п объектов по m ящикам. Обозначим число таких упорядочений через |т|^п .

Теорема 1.4. Число упорядоченных размещений n объектов по т ящикам равно

|т|^п = т (т+1) . . . (т+ n-1)

(полагаем |т|⁰ = 1).

Доказательство. Будем строить упорядоченное размещение, джобавляя по очереди новые объекты. Первый объект мы можем построить т способами, второй – т+1 способами, ибо его можно разместить в одном из m – 1 пустых ящиков или в ящике, содержащим первый объект, перед ним или после него. В общем случае предположим, что уже размещено i – 1 объектов, причем для k = 1, 2, . . . , т в k-м ящике находится r_k объектов. Тогда i-й объект можем добавить в k-й ящик r_k + 1 способами, что дает в сумме

(r_k+1) +. . . + (r_m +1) = (r₁ + . . . + r_m) + m = m + i -1

возможностей. Таким образом, всех упорядоченных размещений будет т (т+1) . . . (т+ n-1).

Пример.

Изобразить упорядоченные размещения двух элементов a,b по трем ящикам.

a	b
a		b
b	a
b		a
ab
ba
	a	b
	b	a
	ab
	ba
		ab
		ba

В этом случае |3|² = 12 = 3 4

Теорема 1.2. Если |X| = n, |Y| = m то числе всех взаимно однозначных функций f: X —> Y равно |т|_п = m (m - 1)…( m - n + 1) (полагаем |т|₀ = 1)

Доказательство. Будем определять на этот раз число инъективных (т. е. имеющих все различные члены) последовательностей < y₁ ..., y_n > с членами из множества Y. Элемент y₁ такого множества мы можем выбрать т способами, элемент y₂ — (m - 1) способами, в общем случае если уже выбраны элементы y₁, ..., y_i-1, то в качестве y_i можем выбрать любой из т–i+1 элементов множества Y\{( y₁, ,.., y_i-1} (принимаем п ≤ т; если п > т, то очевидно, что и |т|_п и искомое число функций равны нулю). (Это дает т (т - 1) ... (т - п + 1) возможностей выбора инъективных последовательностей < y₁ ..., y_n >.)

Пример.

Дано множество Х из 4-х элементов Х = {1, 2, 3, 4}. Записать последовательности из 3 элементов.

Решение.

Число последовательностей длиной 3 с элементами из множества Х будет равно [4]₃ = 4 3 2 = 24.

<1, 2, 3>	<2, 1, 3>	<3, 1, 2>	<4, 1, 2>
<1, 2, 4>	<2, 1, 4>	<3, 1, 4>	<4, 1, 3>
<1, 3, 2>	<2, 3, 1>	<3, 2, 1>	<4, 2, 1>
<1, 3, 4>	<2, 3, 4>	<3, 2, 4>	<4, 2, 3>
<1, 4, 2>	<2, 4, 1>	<3, 4, 1>	<4, 3, 1>
<1, 4, 3>	<2, 4, 3>	<3, 4, 2>	<4, 3, 2>

Замечание. Перестановка является частным случаем размещения при n=k.

Сочетания

Из m-элементного множества A построим упорядоченное множество длины n, элементы которого являются размещениями с одними и теми же элементами, расположенными в разном порядке считаются равными. Такие размещения называются сочетаниями и обозначаются (англ.combination)

Сочетание отличается от размещения тем, что в нем не учитывается порядок. Поэтому каждому сочетанию соответствует k! размещений.

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

A_n^m = m!C_n^m

Число строго монотонно возрастающих функций, или число размещений n неразличимых предметов по m ящикам не более чем по одному в ящик, т.е. число способов выбрать из m ящиков n ящиков с предметами, называется числом сочетаний и обозначается , или, или. Число сочетаний изm по n в раз, т.е.

Теорема.

Доказательство.

1. Число размещений без повторений нужно разделить на число перестановок, поскольку предметы не различимы.

2. Число сочетаний является числом строго монотонно возрастающих функций, потому что строго монотонно возрастающая функция определяется набором своих значений, причем.

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

По определению = 0 приn > m.

Из этой формулы непосредственно вытекает, что ;;

Задание

Доказать, что

1. , где

Доказательство.

2.

Доказательство.

Сочетания с повторениями

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

Пример.

Сколько наборов из 7 товаров можно составить, если имеется всего 4 вида.

Решение

Число наборов равно

Комбинации элементов с повторениями

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

Комбинацией из n элементов по m с повторениями называется m-элементное подмножество множества A, каждый элемент которого принадлежит одному из n типов. Совокупность таких комбинаций называют комбинациями из n элементов по m

Теорема 1.2.8. Количество различных комбинаций из n элементов по m элементов с повторениями равно

Доказательство. «Закодируем» каждую комбинацию следующим образом. Если комбинация включает k₁ элементов первого типа, то записываем подряд k₁ единиц, ставим нуль. После него ставим подряд k₂ единиц, если комбинация включает k₂ элементов другого типа и т.д.

Например, если A ={a, b, c, d}, то комбинациям по два элементас повторениями соответствуют пары {a,a}, {а,b}, {а,с}, {а,d}, {b,b}, {b, с}, {с,d}, {с,с}, {с,d}, {d,d}, а их "кодами" будут соответственно

11000, 10100, 10010, 10001,..., 00011.

Нетрудно убедиться, что между "кодами" и комбинациями существует взаимно однозначное соответствие (убедитесь самостоятельно).

Таким образом, каждой комбинации из п элементов по m соответствует последовательность из т единиц и п-1 нулей (в рассмотренном примере п = 4, т = 2). Следовательно, число всех комбинаций из п элементов по т с повторениями равно числу последовательно­стей, состоящих из т единиц и п - 1 нулей, т. е. . Теорема доказана.

Пример 1.2.7

Сколько целых неотрицательных решений имеет уравнение

x₁ + x₂ + ... + х_n = т? (1.2.4)

Решение. Решения данного уравнения можно интерпретировать так. Если имеем целые неотрицательные числа x₁, х₂, ..., x_п, такие что х₁ + х₂ + ... + x_п = т, то можно составить комбинацию из п элементов по т, взяв х_i элементов первого типа, х₂ элементов второго типа, ..., x_п элемен­тов n-го типа.

Наоборот, имея комбинацию из п по т элементов, получим решение урав­нения (1.2.4) (x₁, х₂ ..., x_n - число элементов первого, второго, и, соответ­ственно, n-го типа), где все х_i неотрицательные (i = 1, 2, ..., n). Таким об­разом, между множеством всех неотрицательных решений уравнения (1.2.4) и множеством всех комбинаций из п элементов по т устанавлива­ется взаимно однозначное соответствие. Следовательно, число целых не­отрицательных решений уравнения (1.2.4) равно

Например, если x₁ + x₂ + x₃ + х₄ = 10, то это уравнение имеет

целых неотрицательных решений.

Бином Ньютона

Из элементарной математики хорошо известны формулы сокращенного ум­ножения:

(а+b)² =а² +2аb+b² и (а+b)^з=а^з+За² b + Заb² + b^З.

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

(x+y)ⁿ = Уx^k y^n-k

Чтобы убедится в истинности этой формулы, достаточно заметить, что коэффициент при x^k y^n-k равен числу способов которыми из n сомножителей (x+y) можно выбрать k сомножителей.

С числами связано функциональное тождество, называемоеформулой бинома Ньютона. Из элементарной математики хорошо известны формулы сокращенного умножения:'

(а + b)² = а²+ 2аb +b², (а + b)³ = а³ + За² b + Заb² + b³.

Эти формулы можно записать так:

(a + b)² = (C⁰₂ a² b⁰ + C¹₂ аb + C⁰₂ а⁰ b²;

(а + b)³ = C⁰₂ a³ b⁰ + C¹₃ а² b¹ + C²₃ а¹ b² + C³₃ а⁰ b³.

Имеет место и общая закономерность: справедливо равенство:

(а + b)ⁿ = C⁰_n аⁿ b⁰ + C¹_n а^n-1 b¹ + C²_n а^n-2 b² + ... + Cⁿ_n а⁰ bⁿ.

Это равенство и называется биномом Ньютона, а коэффициенты C⁰_n, C¹_n, C²_n,..., Cⁿ_n называются биномиальными коэффициентами.

Если положить, а = b = 1, то из формулы бинома Ньютона вытекает следующее важное соотношение: (1 + 1)ⁿ = C⁰_n + C¹_n + C²_n + ... + Cⁿ_n = 2ⁿ - формула суммы биномиальных коэффициентов.

Если положить в биноме Ньютона а =1, b = -1,то

C⁰_n - C¹_n + C²_n - ... +(-1)ⁿ Cⁿ_n = 0 .

Поскольку =, то биномиальные коэффициенты, равноотстоящие от концов в формуле бинома Ньютона, равны.

Все свойства хорошо просматриваются из треугольника Паскаля.

0 1

1 1 1

2 1 2 1

3 1 3 3 1

4 1 4 6 4 1

5 1 5 10 10 5 1

6 1 6 15 20 15 6 1

7 1 7 21 35 35 21 7 1

8 1 8 28 56 70 56 28 8 1

Разбиения. Комбинаторные числа Стирлинга и Белла

Пусть card(M) = n и k — число непустых подмножеств, на которые разбивается множество M. Рассмотрим разбиение множества M = {а₁, а₂, а_n}. Обозначим через S(n,k) - число разбиений множества на k (n>0, 0<k≤n) непустых частей, а через B(n) – число всех разбиений множества M (n>0) на непустые части.

Тогда S(n,k) будем называть число способов разбить множество M мощностью n на k непустых множества.

S(0,0) = 1

S(n,0) = 0n≠1

Числа S(n,k) называются числами Стирлинга.

Числа Стирлинга:

nk	0	1	2	3	4	5	6
0	1	-	-	-	-	-	-
1	0	1	-	-	-	-	-
2	0	1	1	-	-	-	-
3	0	1	3	1	-	-	-
4	0	1	7	6	1	-	-
5	0	1	15	25	10	1	-
6	0	1	31	90	65	15	1
7	0	1	60	301	350	140	21

Найдем явную формулу для чисел S(n,k). Каждое разбиение M = E₁E₂. . .E_k на непустые подмножества можно характеризовать набором чисел (l₁, l₂, . . . .,l_n ), где

l₁ — число подмножеств разбиения мощности 1,

l₂ — число подмножеств разбиения мощности 2,

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ,

l_n - число подмножеств разбиения мощности n.

Эти числа удовлетворяют тождеству

1 l₁ + 2 l₂ + . . . . + n l_n = n.

Теорема 3.

Доказательство.

Процесс построения всех разбиений множества M на k непустых частей, характеризуемых набором чисел (l₁, l₂, . . . ., l_n), l₁ + l₂ + . . . . + l_n = k, можно представить следующим образом.

Возьмем п упорядоченных ячеек и разобьем их на k; подмножеств, характеризуемых данным набором чисел (l₁, l₂, . . . ., l_n). Эти подмножества занумеруем числами 0, 1, ..., k - 1. Разместим в этих ячейках элементы а₁, ..., a_п. Очевидно, что разбиение ячеек на подмножества структуры (l₁, l₂, . . . ., l_n) порождает разбиение элементов а₁, ..., a_п на подмножества такой же структуры. Последнее задается набором (б₁, б₂, ..., б_п), где б_i — номер подмножества разбиения ячеек, которому принадлежит элемент б_i Производя различные размещения элементов а₁, ..., a_п, по ячейкам, получим все разбиения множества M на k непустых частей данной структуры (l₁, l₂, . . . ., l_n). При этом два размещения определяют одно и то же разбиение множества M тогда и только тогда, когда для соответствующих им наборов (б₁, б₂, ..., б_п) и (б₁, б₂, ..., б_п) выполнено условие

Если сравнить соответствующие слагаемые в (15) и (18), то можно увидеть, что они выражают одно и то же число. Отсюда получаем еще одно явное выражение для S(n,r) (n, r>0)

Эта формула не пригодна для практических вычислений S(n,k), так как она предполагает знание всех решений уравнения (14) или (17).

Эффективный способ вычисления чисел Стирлинга 2-го рода и изучение их свойств связано с установлением ряда реккурентных соотношений для S(n,k).

Теорема. S(m,n) = S(m-1,n-1) + n S(m-1,n)

Комбинаторные числа можно изучать двумя способами: теоретико-множественным и алгебраическим.

Числа Стирлинга 2-го рода (Джеймс Стирлинг (1699-1770))

Комбинаторные числа S(n,k) называются числа Стирлинга 2-го рода, а комбинаторные числа B(n) - числами Белла. Эти числа связаны соотношением:

Число разбиений m-элементного множества на n блоков называется числом Стирлинга второго рода и обозначаются S(m,n)

Найдем явную формулу для определения чисел Стирлинга 2-го рода S(n,k).

По определению

S(m,0) = 0 при m > 0

S(m, m) = 1

S(0, 0) = 1

S(m,n) = 0 при n > m

Числа Стирлинга 1-го рода

Число сюръективных функций, то есть число размещений m предметов по n ящикам, таких, что все ящики заняты, называется числом Стирлинга первого рода и обозначаются s(m,n).

Число Белла (Эрик Темпл Белл (1883-1960))

Число всех разбиений m-элементного множества называется числом Белла и обозначается B(m):

Числа Белла:

B(0) = 1

B(1) = 1

B(2) = 2

B(3) = 5

B(4) = 15

B(5) = 52

B(6) = 203

Также существуют число Белла B(n), которое означает число всевозможных вариантов разбиения множества M на непустые подмножества.

)

Утверждение 1. Для определения S (n,k) существует рекуррентная формула S(n,k) = S(n-1,k-1) + k S(n-1,k).

Доказательство.

M: card (M) = n

M = {a₁,a₂,…,a_n}\

M {a_n}

Существует два способа присоединения {a_n} к M:

1) Пусть M было разбито на k-1 непустых подмножества, тогда {a_n} можно было бы присоединить отдельным k-м подмножеством.

2) Множество M {a_n} было разбито на k непустых подмножества, тогда элемент {a_n} можно было бы присоединить к любому из уже существующих подмножеств. Всего k вариантов.

Метод производящий функций

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

Исходным пунктом являются последовательность {a_i} комбинаторных чисел и последовательность функций {φ_i(x)} (i = 0, 1, …).

Рассмотрим ряд

,

который, в случае, когда последовательность {a_i} конечна, т.е. 0 ≤ i ≤ n, будет многочленом.

При определенных ограничениях данный ряд будет сходящимся и тогда он в некоторой области будет задавать функцию F(x):

Эта функция называется производящей функцией.

Пример 1.

(i=0,1, …, n), φ_i(x)-xⁱ

В этом случае имеем

В качестве производящей функции здесь будет бином Ньютона.

С помощью производящей функции установим тождество

Для этого возьмем тождество

Оно эквивалентно тождеству

Сравнивая коэффициенты при xⁿ, получим

Пример 1.

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

Последовательность чисел f_n называется числами Фибоначчи, задается рекуррентными соотношениями f_n = f_n-1+ f_n-2 и f₀ = f₁ = 1

Возьмем φ_n(x) = xⁿ (n = 0,1, 2, …). С этой последовательностью связан ряд

который в силу f_n ≤ 2ⁿ (поскольку f_n ≤ 2f_n-1 ) сходится при │x│ < ½ и определяет производящую функцию F(x)

Так как

и

то

или

(1-x-x²)F(x) =1

Отсюда находим явный вид производящей функции F(x):

Решая уравнение x² + x – 1 = 0 находим его корни

Найдем разложение F(x) на элементарные дроби

Имеем ax₂ + bx₁ – (a + b)x = -1

Это справедливо, если a = - b и .

Далее, воспользовавшись формулой для суммы убывающей геометрической прогрессии (при ) получим

откуда

что дает явное выражение для чисел Фибоначчи.

Контрольные вопросы

1. Что такое комбинаторика и для чего она нужна?

2. Что называется:

— перестановкой п-элементного множества;

— размещением из п элементов по т элементов;

— сочетанием из п элементов по т элементов?

3. В чем отличие размещений от перестановок?

4. В чем отличие сочетаний от размещений?

5. Сколькими способами можно разместить три книги на книжной полке?

6. Запишите формулу для вычисления числа сочетаний элементов, исполь­зуемую в формуле бинома Ньютона.

7. Как найти число перестановок с повторениями?

8. Сколько существует пятизначных чисел, у которых каждая следующая цифра:

—меньше предыдущей,

— больше предыдущей.

9. Сколько прямых можно провести через п точек, если никакие три из них не лежат на одной прямой?

10. Сколько разных слов можно составить перестановкой букв в слове «чачача»?

11. Вычислите: (а + b + с)2; (а + b + с)3.

12. Покажите, что сумма делится на р, где р — простое число.

13. Докажите свойства биномиальных коэффициентов.

14. Какая разница между декартовым квадратом некоторого непустого мно­жества A и множеством всех двухэлементных подмножеств множества A?

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

16. Сколько существует функций из множества A в множество В, если \А\ = т, а |B| = n?

Лекция № 6

В самой математике главные средства достигнуть истины – индукция и аналогия.

Лаплас, Опыт философии теории вероятностей, М., 1908, стр.7.