Сочетания

Пусть имеется n различных объектов.  Будем выбирать из них m объектов все возможными способами (то есть меняется состав выбранных объектов, но порядок не важен). Получившиеся комбинации называются сочетаниями из n объектов по m, а их число равно

Cmn=n!(n−m)!⋅m!

Пример всех сочетаний из n=3 объектов (различных фигур) по m=2 - на картинке справа. Согласно формуле, их должно быть ровно C23=3!(3−2)!⋅2!=3. Ясно, что сочетаний всегда меньше

чем размещений (так как при размещениях порядок важен, а для сочетаний - нет), причем именно в m! раз, то есть верна формула связи:

Amn=Cmn⋅Pm.

Билет 8.

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

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

В дальнейшем нам понадобятся некоторые свойства числа сочетаний.

1. Свойство симметричности:

2. Рекуррентная формула для числа сочетаний:

ПРИМЕЧАНИЕ

Интуитивно свойство 2 означает следующее. Если в множестве G, из которого составляется сочетание H, зафиксировать какой-либо элемент x, то все возможные сочетания делятся на две категории: сочетания H, которые содержат x, и сочетания H, не содержащие его. Количество сочетаний первого типа равно числу сочетаний из n-1 (так как элемент x фиксирован) по k-1, второго типа – из n-1 по k.категории: сочетания H, которые содержат x, и сочетания H, не

категории: сочетания H, которые содержат x, и сочетания H, не содержащие его. Количество сочетаний первого типа равно числу сочетаний из n-1 (так как элемент x фиксирован) по k-1, второго типа – из n-1 по k.

Билет 9. Бином ньютона и треугольник паскаля

Бином Ньютона — формула разложения произвольной натуральной степени двучлена (а+b)ⁿ в многочлен. Каждый из нас знает наизусть формулы «квадрата суммы» (а+b)² и «куба суммы» (а+b)³, но при увеличении показателя степени с определением коэффициентов при членах многочлена начинаются трудности. Чтобы не совершить ошибку и применяется формула бинома Ньютона:

В более общем виде формула коэффициентов в биноме записывается так:

где k - порядковый номер слагаемого в многочлене.

Напомним, что факториал — произведение натуральных чисел от 1 до n, то есть 1х2хЗх...хn — обозначается n!, например, 4!=1x2x3x4=24.

Запомнить формулу действительно непросто. Но попытаемся её проанализировать. Видно, что в любом многочлене присутствуют aⁿ и bⁿ с коэффициентами 1. Ясно также, что всякий иной член многочлена выглядит как произведение определённых степеней каждого из слагаемых двучлена (a+b),причём сумма степеней всегда равна n. Например, в выражении(a+b)³=a³+3a²b+3ab²+b³ сумма степеней сомножителей во всех членах равна трём (3, 2+1, 1+2, 3). То же самое справедливо и для любой другой степени. Вопрос лишь в том, какие коэффициенты следует ставить при членах.

Видимо, для того чтобы облегчить труд школяров и студентов, великий французский математик и физик Блез Паскаль триста пятьдесят лет назад придумал специальный инструмент для определения этих самых коэффициентов — «треугольник Паскаля».

Строится он следующим образом.В вершине треугольника пишем 1. Единица соответствует выражению (a+b)⁰, поскольку любое число, возведённое в нулевую степень, даёт единицу. Достраивая треугольник, ниже пишем ещё по единице. Это коэффициенты разложения того же двучлена, возведённого в первую степень: (a+b)¹=a+b. Идём дальше. Стороны треугольника образуют единицы, а между ними — сумма двух единичек, находящихся сверху, то есть 2. Это и есть коэффициенты трёхчлена «квадрат суммы»:

a²+2ab+b².

Следующий ряд, как и предыдущий, начинается и заканчивается единицами, а между ними — суммы цифр, находящихся сверху: 1, 3, 3, 1. Мы получили коэффициенты разложения « куба суммы ». Ряд коэффициентов двучлена четвёртой степени составят 1, 4, 6, 4, 1 и так далее.

Для примера с помощью треугольника Паскаля разложим в многочлен сумму двучленов в шестой степени:

(a + b)⁶=a⁶+6a⁵b + 15a⁴b²+20a³b³ + 15a²b⁴+6ab⁵+b⁶.

Всё очень несложно и запоминается на всю жизнь. Кстати, самостоятельно вспомнить и вывести формулу бинома Ньютона, нарисовав на черновике треугольник Паскаля, тоже намного проще.

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