АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Сочетания

Читайте также:
  1. Вводные слова и словосочетания
  2. Вводные слова и словосочетания в алфавитном порядке
  3. Вводные слова, словосочетания, вставные конструкции. обращения
  4. Влияние на организм неправильного сочетания пищевых веществ
  5. Выбор оптимального сочетания «цена – объем продаж» путем сравнения валового дохода и валовых издержек.
  6. Гласные звуки и звукосочетания
  7. Задание 10 вводные слова, словосочетания, вставные конструкции. обращения
  8. Значение сочетания болезней сердца и сосудов с беременностью
  9. Оценка сочетания различных факторов, повлиявших на негативный исход
  10. Предложные терминологические словосочетания
  11. Синтаксическая связь слов в словосочетаниях
  12. Составьте словосочетания с данными паронимами так, чтобы показать разницу в значениях

Сочетанием элементов множества X называется подмножество конечного множества AÍX. Если |A|=k, |X|=n, то подмножество X называется с очетанием из n по k. Например, сочетания трех цветов семицветной радуги будут описываться подмножествами, состоящими из трех элементов выбранных из множества, состоящего из 7 элементов.

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

Теорема 1. Число сочетаний удовлетворяет соотношениям:

; (при 0 < k < n).

Доказательство. Число пустых подмножеств равно 1. Стало быть, . Подмножества, состоящие из n элементов, совпадают со всем множеством, отсюда . Число сочетаний, не содержащих n -й элемент, равно , а содержащих – . Следовательно, при 0 < k < n,

Следующая таблица 2.1 строится на основе теоремы 1 и называется треугольником Паскаля.

Таблица 2.1

Треугольник Паскаля

 

n k            
             
             
             
             
             
             
             

Теорема 2. Число сочетаний из n по k равно .

Доказательство. По индукции по n. При n=0 и k=0 получаем . Пусть теорема верна для n. С помощью теоремы 1 получаем

.

Откуда формула верна для n +1 и всех k < n +1.

Другой способ доказательства заключается в сопоставлении каждой инъекции ее образ. В этом случае, учитывая, что число инъекций с одинаковым образом равно k!, получаем Þ .

Теорема 3. (Бином Ньютона).

Доказательство. По индукции по n. Пусть формула верна для n. Тогда

Можно предложить также другое доказательство: Рассмотрим произведение n сомножителей (1 +x) (1 +x) × × × (1 +x). Сомножители будем рассматривать как ящики. Произведение равно сумме степеней xk, причем при каждом k слагаемые xk получаются выбором из ящиков k элементов, равных x. Отсюда коэффициент при xk будет равен количеству содержащих k элементов подмножеств множества, состоящего из n элементов.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)