§ 3. Бином и полином
Запишем формулы бинома.
Для
(1)
Если заменить b на − b, то из формулы (1) следует:
, (2)
где коэффициенты называют биномиальными коэффициентами.
Для всех неотрицательных целых чисел п, k
(3)
Область определения биномиальных коэффициентов можно расширить:
для функция
(4)
является биномиальным коэффициентом.
Для целых оба определения для биномиальных коэффициентов совпадают.
Замечание: читается: С из п по k ; п над k .
Примеры.
□ 1)
2)
3)
4) . ■
Свойства биномиальных коэффициентов
Числа имеют ряд важных свойств:
10 для целых справедливо свойство симметрии
20 теоремы сложения:
из формулы бинома при а = 1, b = 1 следует:
,
это число равно числу всех возможных неупорядоченных подмножеств множества М, состоящего из п элементов (булеан),
при а = 1, b = −1 :
,
из этого равенства следует, что суммы биномиальных коэффициентов, стоящих на четных и нечетных местах, равны между собой и каждая равна ;
;
30 для теоремы сложения имеют вид :
.
Формула полинома является обобщением формулы бинома, т.е.
для любых действительных чисел а1, а2, … , ат не равных нулю и любого натурального числа п имеет место формула:
(5)
при этом суммирование распространяется на все наборы натуральных чисел для которых .
Коэффициенты
,
определенные для всех натуральных п и всех наборов неотрицательных чисел , для которых , называют полиномиальными коэффициентами.
Полиномиальные коэффициенты часто записывают в виде .
При формула (5) принимает вид
(6)
Пример. □
■
- Богданов а.Е. Курс лекций
- Содержание
- § 1. Основные понятия теории множеств
- Основные понятия теории множеств
- Способы задания множеств
- Операции над множествами
- § 2. Соответствия. Функции. Отображения
- § 3. Понятие алгебры. Алгебра множеств кантора
- Диаграмма Эйлера-Венна
- § 4. Бинарные отношения
- Способы задания бинарных отношений
- Свойства бинарных отношений
- § 5. Бинарное отношение эквивалентности
- § 6. Бинарное отношение порядка. Упорядоченные
- § 7. Решетки (структуры). Изоморфизм
- Изоморфизм множеств
- Дедекиндовые решетки
- Дистрибутивные решетки
- § 8. Отношения (обобщение). Алгебраические
- Операции над отношениями
- Алгебраические системы
- Глава ιι. Комбинаторный анализ
- § 1. Основные определения
- Правила суммы и произведения
- § 2. Формулы расчета перестановок и сочетаний
- § 3. Бином и полином
- § 4. Подстановки
- § 5. Метод включений и исключений
- § 6. Метод производящих функций
- § 7. Комбинаторная мера информации. Вероятность искажения информации
- Глава ιіі. Теория графов
- § 1. Первоначальные понятия теории графов
- § 2. Операции над графами. Способы задания графов Операции над графами
- Способы задания графов
- § 3. Маршруты, цепи, циклы и другие характеристики графа
- § 4. Алгебраическая форма представления графа
- Глава іv. Некоторые приложения графов
- § 1. Эйлеровы графы. Алгоритм флери. Гамильтоновы
- Эйлеровы графы
- Алгоритм Флери.
- Метод построения эйлерового обхода двоичного куба
- Гамильтоновы графы. Метод Робертса – Флореса
- Метод перебора Робертса – Флореса
- § 2. Пространство циклов графа
- § 3. Независимое множество вершин графа
- Алгоритм выделения пустых подграфов
- § 4. Вершинное число внешней устойчивости графа
- § 5. Плотность графа
- Алгоритм выделения полных подграфов
- § 6. Раскраска графа
- Оценки хроматического числа
- Алгоритм минимальной раскраски вершин графа
- § 7. Планарность графа
- Глава V. Оптимизационные алгоритмы теории графов
- § 1. Определение кратчайших путей. Алгоритм дейкстры
- § 2. Максимальный поток через сеть. Алгоритм
- Алгоритм Форда – Фалкерсона
- § 3. Построение остова экстремального веса. Алгоритм краскала
- § 4. Метод ветвей и границ: задача коммивояжера. Общая модель задачи поиска
- Дерево поиска частичных решений
- § 5. Применение ориентированных деревьев в задачах теории кодирования и диагностирования
- § 6. Построение оптимального дерева бинарного поиска. Алгоритм гильберта – мура
- Алгоритм Гильберта – Мура построения оптимального дерева бинарного поиска Суть алгоритма
- Алгоритм
- § 7. Сложность задач теории графов. Задача синтеза управляющих систем
- Задача синтеза управляющих систем
- Задача о выполнимости
- Литература
- Электронное пособие курс лекций
- «Дискретная математика».