- •Дискретная математика. Теория и практика
- •Оглавление
- •Глава 1. Множества 6
- •Глава 2. Комбинаторика 24
- •Глава 3. Отношения. Отображения 34
- •Глава 4. Алгебраические структуры 55
- •Предисловие
- •Введение
- •Глава 1. Множества
- •1.1. Множества и их элементы. Способы задания множеств
- •1.2. Подмножества
- •1.3. Операции над множествами
- •1.4. Диаграммы Эйлера – Венна
- •1.5. Прямое произведение множеств
- •1.6. Метод математической индукции
- •1.7. Соответствия
- •1.8. Задачи, связанные с определением мощности конечного множества
- •Задачи и упражнения к главе 1
- •Глава 2. Комбинаторика
- •2.1. Правила суммы и произведения
- •2.2. Размещения и сочетания
- •2.3. Примеры решения задач
- •2.4. Бином Ньютона
- •2.5. Свойства биномиальных коэффициентов. Треугольник Паскаля
- •Задачи и упражнения к главе 2
- •Глава 3. Отношения. Отображения
- •3.1. Понятие отношения
- •3.2. Способы задания бинарных отношений
- •Характеристическим свойством.
- •3.3. Операции над бинарными отношениями
- •3.4. Свойства матриц бинарных отношений
- •3.5. Свойства бинарных отношений
- •3.6. Определение свойств бинарного отношения по его матрице
- •3.7. Отношение эквивалентности
- •3.8. Счетные и несчетные множества
- •3.9. Отношение порядка. Диаграммы Хассе
- •3.10. Функции
- •Задачи и упражнения к главе 3
- •Глава 4. Алгебраические структуры
- •4.1. Алгебраические операции и их свойства
- •4.2. Понятие алгебраической структуры
- •4.3. Алгебры с одной бинарной алгебраической операцией
- •4.4. Алгебры с двумя бинарными алгебраическими операциями
- •4.5. Конечные поля
- •4.6. Булевы алгебры
- •4.7. Гомоморфизмы алгебр
- •4.8. Алгебраические системы. Решетки
- •Задачи к главе 4
- •Список литературы
2.4. Бином Ньютона
Исторически название бином Ньютона несправедливо, поскольку формулу знали еще среднеазиатские математики, начиная с Хайяма (Омар Хайям (около 1048 – 1131) – персидский поэт, математик и философ), а в Европе до Ньютона (Исаак Ньютон (1643 – 1727) – английский физик, астроном и математик) еe знал Паскаль (Блез Паскаль (1623 – 1662) – французский математик). Однако заслуга Ньютона заключается в том, что он обобщил эту формулу для нецелого показателя n (см. замечание 2.2).
Для натурального показателя n формула бинома Ньютона имеет вид:
= = . (9)
Доказательство. Для доказательства формулы (9) применим метод математической индукции.
1. База индукции. Пусть n = 1. Тогда = = а + b.
2. Индуктивное предположение. Предположим, что формула (9) верна для n – 1.
3. Индукционный переход. Докажем справедливость формулы (9) для n.
В данном случае получаем
= = = + .
Заменим индекс суммирования k на j так, что k = j – 1, j = k + 1. Так как , то и следующая формула принимает вид: = . Отсюда = + .
Выровняем пределы изменения индексов суммирования в обеих суммах. Для этого введем дополнительно и , тогда = и = .
Отсюда = = =
= = = = = = = . Следовательно, формула (9) верна для любого натурального n.
Замечание 2.2. Для нецелого n при |х| < 1, формула имеет вид
=
2.5. Свойства биномиальных коэффициентов. Треугольник Паскаля
Биномиальное разложение служит основой для многих комбинаторных формул. Например:
1. Пусть a = b = 1. Тогда . Так как – число k-элементных подмножеств n-элементного множества, то сумма в левой части есть число всех подмножеств n-элементного множества. Таким образом, получили еще одно доказательства того, что мощность булеана n-элементного множества равна 2n.
2. Пусть a = –1, b = 1. Тогда . Следовательно, суммы биномиальных коэффициентов, стоящих на четных и на нечетных местах, равны между собой, и каждая равна .
3. .
Действительно, .
4. В ходе доказательства формулы (9) мы получили
. (10)
Тождество (10) позволяет вычислить значения , зная и .
Другими словами, с помощью тождества (10) можно последовательно вычислить при n = 0, затем при n = 1, при n = 2 и так далее. Вычисления удобно записывать в виде треугольной таблицы:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
В (k + 1)-й строке по порядку стоят числа . Поскольку и располагаются в этой таблице строкой выше, чем , и находятся в этой строке слева и справа от него, то для получения надо сложить находящиеся справа и слева от него числа предыдущей строки. Например, значение 10 в шестой строке мы получим, сложив числа 4 и 6 пятой строки.
Эту таблицу называют треугольником Паскаля, по имени французского математика Блеза Паскаля, в трудах которого она встречается. Это название так же, как и бином Ньютона, исторически неточно, поскольку такую таблицу уже знал упомянутый ранее Омар Хайям.