рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Свойства сочетаний.

Свойства сочетаний. - раздел Математика, КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ   Одной Из Наиболее Распространённых Комбинаторных Формул Являе...

 

Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать следующие свойства сочетаний:

, (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: Пусть - отношение порядка на множестве

Определение 7: Дистрибутивная решетка с отличными друг от друга 0 и 1, в которой всякий элемент имеет дополнение, называется булевой алгеброй.
Отметим, что теория решеток и теория булевых алгебр – это самостоятельные разделы алгебры. Определение 8: Линейно упорядоченное множество, удовлетворяющее условию мини

Мощность множества. Сравнение мощностей.
  Пусть даны конечные множества и , число элементов которых равно

Определение 2: Множества, обладающие одинаковой мощностью, называются равномощными (эквивалентными).
Два конечных множества будут равномощными, если в них содержится одинаковое число элементов. Если имеем дело с бесконечными множествами, то вопросы, связанные с мощностями, решаются путём установле

Определение 3: Множество, эквивалентное множеству чисел натурального ряда, называется счетным.
Натуральный ряд чисел – это счётное множество. Все множества, равномощные множеству , имеют такую же мощность. Теорема 4:

Трансфинитная индукция.
  Понятие мощности множества является обобщением понятия количества элементов конечного множества. А число элементов во множестве – это натуральное число. Но над натуральными числами

Определение 3: Если два линейно упорядоченных множества изоморфны, то их называют подобными множествами.
Подобие для линейно упорядоченных множеств - есть бинарное отношение между линейно упорядоченными множествами, являющееся отношением эквивалентности. Фактор-множество по этому отношению эквивалентн

Задачи для самостоятельной работы.
1) Доказать, что два множества равны тогда и только тогда, когда их пересечение и объединение совпадают. 2) Обозначим через множес

Отрицание – обозначается ,читается:«не » или «неверно, что ».
2) Дизъюнкция (логическое сложение), обозначаемое(читается «и

Формулы алгебры логики. Тавтологии.
  В алгебре выводятся формулы, которые остаются верными, какие бы числа не подставляли вместо букв, входящих в эти формулы. Подобным образом в алгебре высказываний конструируются форм

Доказательство.
Необходимость: Пусть формулы и равносильны. Тогда, по определению, для люб

Определение 3: Множество всех значений таких, что предикат при этих значениях принимает значение «истина», называется областью истинности предиката.
Определение 4: Предикат , определённый на множестве , называе

Формулы и тавтологии логики предикатов.
  При введении определения формул логики предикатов будем использовать следующие обозначения (алфавит): 1) – индивид

Формальный язык логики высказываний.
  Таблицы истинности в логике высказываний позволяют ответить на многие вопросы. Например, является ли данная формула тавтологией, противоречием или выполнимой формулой; влечёт ли она

Предикатов. Свойства теорий первого порядка.
  Для записи формул логики предикатов используется следующий алфавит: скобки, запятые, символы исчисления высказываний (отрицание

Задачи для самостоятельной работы.
1.Определить истинность следующих высказываний, если , ,

Определение формулы и суперпозиции.
  Пусть имеется счетное множество переменных , где

Принцип двойственности.
  Пусть – некоторое подмножество множества булевых функций: .

Линейные функции. Монотонные функции.
  Рассмотрим систему функций: , ,

Теорема Поста.
  В предыдущем параграфе были рассмотрены некоторые классы булевых функций. В каждый класс попадают функции, обладающие определённым свойством. Для удобства введём следующие обозначен

Задачи для самостоятельной работы.
1) Сколько имеется различных двоичных наборов длины ? 2) Сколько имеется

Правила комбинаторики.
  Начнем с основных принципов комбинаторики, т.е. с правил. Существует два общих правила комбинаторики: правило сложения и правило умножения. Правило слож

Определение 2: Множество с заданным на нем порядком называется упорядоченным множеством.
Очевидно, что множество, содержащее более одного элемента, можно упорядочить не единственным способом. Например, из двух букв и

Определение 8: Конечные упорядоченные множества называются размещениями.
Теорема 3: Количество всех размещений из элементов по элемен

Определение 10: Конечные неупорядоченные множества называются сочетаниями.
Таким образом, сочетания – это такая выборка элементов, при которой их порядок совершенно не важен. Сочетаний из элементов по

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

Определение 2: Группы, составленные из объектов, которые принадлежат одному из типов элементов, называют сочетаниями с повторениями.
Число всевозможных сочетаний с повторениями обозначают следующим символом: . Сочетания с повторениями, как было показано в примере

Упражнения для самостоятельной работы.
  1. Сколько всегочетырёхзначных натуральныхчисел? Сколько всего четырёхзначных натуральныхчисел, в записи которых нет одинаковых цифр?  

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги