Свойства сочетаний. - раздел Математика, КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
Одной Из Наиболее Распространённых Комбинаторных Формул Являе...
Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать следующие свойства сочетаний:
, (1)
. (2)
Доказательство. Используем формулу числа сочетаний.
1) .
2) .
Первое из доказанных свойств несет в себе своеобразную симметричность формулы для числа сочетаний. Например, , . Это свойство упрощает вычисления.
Второе тождество иногда называют тождеством Паскаля. Оно позволяет разбивать на классы и .
Числа возникают в самых разных задачах комбинаторики и теории вероятностей. Например, из тождества Паскаля следует, что для всех натуральных чисел и , причем , справедливо равенство:
. (3)
Эта формула может быть доказана индукцией по числу слагаемых в левой части.
Рассмотрим некоторые прикладные аспекты последней формулы.
1) При формула (3) превращается в известную формулу суммы первых членов арифметической прогрессии:
.
Таким образом, можно вычислять сумму слагаемых натурального ряда от 1 до .
2) Для из формулы (3) имеем:
,
или окончательно:
.
Последняя формула дает возможность находить сумму квадратов чисел натурального ряда от 1 до .
3) Для получаем:
,
или после преобразований:
.
Таким образом, можно получить формулы для сумм более высоких степеней натуральных чисел.
Сочетания можно встретить и в школьном курсе математики. Например, в качестве коэффициентов бинома Ньютона выступают именно сочетания.
Бином – это сумма двух слагаемых, например, .
Формула бинома Ньютона в общем виде и её доказательство приводятся в следующей теореме.
Теорема 1: Для любых чисел и , и любого натурального числа справедливо следующее равенство:
. (4)
Доказательство. Применим индукцию по числу .
При : .
Пусть формула верна, для случая, когда степень бинома равна . В этом случае следующее равенство будем считать выполненным:
.
Покажем, что формула выполняется для - й степени:
.
Используя предыдущее равенство и раскрывая скобки, получим требуемое выражение.
В доказательстве можно также использовать свойство: .
Формула (4) носит имя и математика Исаака Ньютона, хотя она была известна задолго до него, например, в Европе ее знал французский математик Блез Паскаль. Заслуга Ньютона состоит в том, что он нашел обобщение этой формулы на случай нецелых показателей. Тем не менее, приведенное выше разложение называют биномом Ньютона, а коэффициенты называются биномиальными коэффициентами.
Следствие: Рассмотрим некоторые частные случаи формулы бинома Ньютона:
1) если , то .
2) если , то .
3) Сумма показателей степени при и в любом слагаемом разложения равна .
4) Биномиальные коэффициенты, равноудаленные от концов разложения, равны между собой, так как .
5) Биномиальные коэффициенты сначала возрастают, потом убывают.
Числовые значения биномиальных коэффициентов вычисляются по формуле числа сочетаний: . Готовые значения этих коэффициентов располагаются в строках треугольника Паскаля.
1 n = 0
1 1 n = 1
1 2 1 n = 2
1 3 3 1 n = 3
1 4 6 4 1 n = 4
1 5 10 10 5 1 n = 5
. . . . . . . . . . . . . . . . . . . . . . . . .
Треугольник Паскаля строится следующим образом. Боковые стороны состоят из единиц. Числа, находящиеся внутри, являются суммой вышестоящих чисел. Каждая строка треугольника соответствует некоторой степени для суммы и содержит соответствующие биномиальные коэффициенты. Таким образом, для того, чтобы раскрыть степень суммы , нужно из треугольника Паскаля взять строку, соответствующую данному показателю степени . Эта строка будет содержать нужные коэффициенты , к которым приписываются соответствующие буквенные выражения. Можно заметить, что строки треугольника Паскаля симметричны, поэтому достаточно взять только половину биномиальных коэффициентов и, если нужно, средний элемент.
ВОСТОЧНОУКРАИНСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ... имени ВЛАДИМИРА ДАЛЯ... Фесенко Т Н...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Свойства сочетаний.
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Представление бинарных отношений графами.
Понятие графа используется в математике для наглядного представления бинарных отношений, заданных на конечных множествах.
Граф представляет собой конечный набор точек плоскости (
И порядка. Фактор-множество.
В данном параграфе будут рассмотрены некоторые виды бинарных отношений. Рассмотрим непустое множество и зададим на нём бинар
Булевы алгебры.
Определение 1: Пусть - отношение порядка на множестве
Трансфинитная индукция.
Понятие мощности множества является обобщением понятия количества элементов конечного множества. А число элементов во множестве – это натуральное число. Но над натуральными числами
Задачи для самостоятельной работы.
1) Доказать, что два множества равны тогда и только тогда, когда их пересечение и объединение совпадают.
2) Обозначим через множес
Формулы алгебры логики. Тавтологии.
В алгебре выводятся формулы, которые остаются верными, какие бы числа не подставляли вместо букв, входящих в эти формулы. Подобным образом в алгебре высказываний конструируются форм
Доказательство.
Необходимость: Пусть формулы и равносильны. Тогда, по определению, для люб
Формальный язык логики высказываний.
Таблицы истинности в логике высказываний позволяют ответить на многие вопросы. Например, является ли данная формула тавтологией, противоречием или выполнимой формулой; влечёт ли она
Теорема Поста.
В предыдущем параграфе были рассмотрены некоторые классы булевых функций. В каждый класс попадают функции, обладающие определённым свойством. Для удобства введём следующие обозначен
Правила комбинаторики.
Начнем с основных принципов комбинаторики, т.е. с правил.
Существует два общих правила комбинаторики: правило сложения и правило умножения.
Правило слож
Комбинаторика с повторениями.
Одна из особенностей комбинаторных задач заключается в том, что в ней исключительно большую роль играет точность формулировки. Обычно в задаче по комбинаторике необходимо определить
Упражнения для самостоятельной работы.
1. Сколько всегочетырёхзначных натуральныхчисел? Сколько всего четырёхзначных натуральныхчисел, в записи которых нет одинаковых цифр?
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов