Combinations

Introduction to combinations

Здравствуйте!

На прошлом уроке мы выясняли, сколько есть различных способов

Рассадить 5 человек по 3 креслам.

Так, например, это кресло №1, это кресло №2, это кресло №3.

Мы говорили, что на кресло №1 претендуют 5 человек,

но пока еще на нем никто не сидит.

Затем останется только 4 человека, поэтому мы могли бы

любого из четырех посадить в кресло №2.

А затем осталось бы только 3 человека,

любого из них мы могли бы посадить в кресло №3.

Итого размещений, т.е. способов, с помощью которых

люди могли бы рассесться по разным креслам,

если бы нам был важен порядок

в какие кресла они садятся - было бы 543.

Есть и другой способ посчитать размещения.

543 – то же самое, что и 54321 разделить на что?

Разделить на 2*1.

В свою очередь это - то же,

что и 5 факториал разделить на 2 факториал.

Откуда появилось это 2?

Как это 2 связано с 5 и 3, и какая разница между ними?

Итак, вот это - то же самое, что и 5! разделить на (5-3)!.

А в общем, как мы вычисляем количество размещений,

с помощью которых 5 предметов сами размещаются или

могут быть размещены в 3 местах?

Общая формула… мы рассматривали ее на прошлом уроке.

Вот она, в ней n – кол-во предметов,

которые мы хотим поместить в k мест,

и k должно быть меньше либо равно n.

Хотя, на самом деле, не должно…

но для наших нынешних целей

предположим, что должно,

иначе наша формула потеряет смысл.

И это равно n! разделить на (n-k)!.

Мне всегда кажется, что труднее запомнить эту формулу,

чем просто подумать о местах (позициях).

Тогда я просто говорю: всего есть 5 человек,

и любой из них мог бы быть здесь.

Затем, т.к. 1 человек уже здесь, то для второго

остаются только 4 человека, а для третьего – 3.

И я вычисляю таким способом: беру первые k элементов

от n факториала.

В этом случае я беру первые три элемента от 5!

543.

Вот как я рассуждаю о размещениях.

А теперь давайте назовем этих людей A, B, C, D, E.

Т.е. это 5 человек, которые будут сидеть в креслах.

Считаем, что комбинация ABC

отлична от комбинации ACB, отлична от комбинации ВАС

и от комбинации ВСА.

Потому что помните: если мы так считаем, то, значит, в этом случае

заботимся о том, где именно и какие люди сидят.

И на прошлом уроке мы дважды все посчитали,

потому что имеет значение, сидит ли человек А на сиденье №1,

а человек В на сиденье №2.

А затем, если они меняются местами, то мы это учитываем, так?

Вот где они меняются местами.

Но что, если бы нам это не было важно?

Что, если бы мы не заботились о том, кто на каком сиденье сидит?

Т.е. мы просто хотели бы знать,

сколько есть разных способов рассадить 5 человек?

Итак, по сути, мы хотим посчитать все ситуации,

в которых рассаживаются люди A, B и С как одну ситуацию.

Нас не волнует, кто в какое кресло садится.

Нас волнуют только 3 человека, которые рассаживаются.

Это подмножество рассаживающихся людей.

И потому вопрос уже не в том, сколько есть различных размещений

или какими различными способами люди могут рассаживаться.

Теперь вопрос ставится так: сколько подмножеств из 3 элементов

мы можем составить из 5-элементного множества?

Знаю, что я немного забегаю вперед,

но, по сути, это определение сочетания.

Сочетание – это размещение, в котором вы не заботитесь о порядке.

Итак, как мы вот это нашли?

Когда мы находили размещения, используя эту формулу,

то мы считали… например, мы считали ABC, ACB, BAC,

BCA, и… Давайте посмотрим.

Здесь должны быть еще две комбинации:

CAB и CBA.

С точки зрения размещений все эти 6 комбинаций различны.

С точки зрения сочетаний все они, по сути, одинаковы…

потому что в сочетаниях мы не заботимся о порядке.

Итак, для любых трех разных человек, которые сидят на этих сидениях,

существует 6 перестановок

(которые мы находим, когда занимаемся перестановками).

А если нам нужны сочетания,

то мы просто разделим на количество способов,

с помощью которых мы можем пересаживать 3 человек по 3 сиденьям.

Это, по сути, то, что мы делали здесь.

Итак, сколькими разными способами

вы рассадить трех человек по трем сиденьям?

Ну, это что-то вроде еще одной задачи по перестановке.

На первое сиденье вы могли бы посадить любого из 3 человек,

на второе сиденье – любого из 2, а на третье сиденье

остается только 1 человек.

Это равно факториалу числа 3, и равно это 6.

Это равно 3!, и равно это 6.

Надеюсь, я не сбиваю вас с толку.

Я пытаюсь сейчас до вас донести то, что когда мы делали размещения,

мы считали все возможные порядки, в которых

люди могли бы рассаживаться.

А сейчас я вас спрашиваю: "Сколько есть различных способов,

с помощью которых люди могут рассаживаться?"

Ну, это будет равно факториалу числа мест,

потому что если у нас есть 3 человека на 3 места или, предположим,

4 человека на 4 места.

На 4-е место претендуют 4 человека, на 3-е – 3,

на 2-е – 2, и на последнее сиденье

остается только 1 человек.

Итак, факториал количества мест – это и есть количество перестановок.

Если у нас есть все те же люди, они просто

меняются местами на своих сиденьях. Вот что такое перестановки.

Попробуем найти сочетания (обозначим большой буквой «С»).

Предположим, что у нас 5 человек.

Сколько различных групп из 3 человек могут быть рассажены?

(И мы не хотим повторяться.

Не хотим проводить двойное вычисление, т.е. считать одного и того же человека дважды или трижды.

Формула будет такая же, как и у размещения, но еще в знаменателе количество способов,

с помощью которых, в нашем случае, 3 человека смогут рассесться по 3 сиденьям.
Поэтому у нас в знаменателе будет ещё 3!.

Надеюсь, я понятно объясняю.

Может быть, я приведу еще пару примеров на следующем уроке,

вы только дайте мне знать точно, если считаете, что

совсем непонятно.

Итак, в общем, если мы скажем: «Сколько есть разных способов,

с помощью которых можно выбрать n предметов?»

Или количество сочетаний, с помощью которых n предметов

могут быть собраны в множества r, где r ≤ n.

Это равно количеству размещений, которые вы можете сделать,

раскладывая n предметов по r местам, разделить на r!

Мы разделим на количество способов, с помощью которых r мест

могли бы сами быть переставлены, т.к. не хотим

дополнительно считать их.

А если вернуться к этой формуле, вверху,

то это было k, но теперь мы предполагаем, что это r.

Это то же самое, что…

Итак, размещение было равно n!/(n-r)!

И теперь мы все делим на r!

И это равно… Давайте я запишу.

Это часто пишется как «r из n».

А другой способ записи – вот так «r из n».

Это называется биномиальным (двойным) коэффициентом,

и мы также проведем целую серию уроков на эту тему,

потому что там показывается разложение полинома,

если вы возводите полиномы в степень.

Формула сочетания n!/(r!(n-r)!).

Вы можете это выучить наизусть.

Знаете, это полезно, если вы хотите быстро

решать задачи во время тестов.

Но очень важно помнить о том, откуда это взялось.

n!/(n-r)! – это просто размещение.

А что было факториалом n?

Ну, это были только первые r… Думаю, можно было бы

назвать это первыми r множителями.

Первые r наибольших множителей n факториала.

Вот и все, что это было.

Затем, если мы составляем сочетания, то делим это еще и на r!,

потому что хотим разделить на все различные расположения,

которые люди могли бы занять, рассаживаясь по r сиденьям.

Или, например, мячики могут быть помещены в r чашек.

Итак, в этой ситуации, если мы хотим знать,

сколько различных групп из 3

могут быть выбраны среди 5 человек (или среди 5 букв),

то это будет равно 5!/(3!(5-3)!).

И это 532*1, разделить на…3!=6.

Мы его ненадолго отложим в сторону.

Разделить на… Это 2 факториал, т.е. 2*1.

Итак, заметьте: вот эта часть – это размещение.

И эта часть избавляется от двух наименьших множителей.

Получится 5*3.

Ой, прошу прощения, здесь еще и 4.

543, что является количеством размещений.

А затем мы делим на 6, потому что получаем 6 перестановок

т.е. 6 разных комбинаций одних и тех же элементов.

Может, это вас запутало.

Но тем не менее, мы получили (543)/6.

И чему это равно?

(512)/6, и это также равно 52.

И получилось 10 возможных способов, с помощью которых

мы можем получить 3-х элементные множества из группы, состоящей из 5 предметов.

До встречи на следующем уроке!