Формулы комбинаторики. Как запомнить и осилить.

Периодически я возвращаюсь к теме математики, так как это очень полезная дисциплина, лежащая в основе человеческого мышления.

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

Вектор развития любой науки идёт от простого к сложному и на этом пути неизбежны потери.

Причём потери в самом главном, в понимании смысла базовых идей.

За деревьями исчезает лес и многим начинает представляться, что чем сложнее, заумнее и «научнее» изложен вопрос, тем это ближе к истине.

На самом деле всё обстоит ровно наоборот. Гениальность в простых понятиях, а все значимые достижения человеческой цивилизации рождаются из комбинации элементарных представлений.

И труднее всего осилить базовые принципы, которыми мучают детей, и которые, в большинстве случаев, сами не понимают.

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

Формулы комбинаторики широко используются в теории вероятностей для определения пространства возможных событий.

И многие со страхом вспоминают эту абракадабру.

n ^n

n ^r

n!

A(r по n), (n) r, n!/( n- r)!, n(n- 1) (n- 2)(n- 3)……… (n- r+1)

С(r по n), (n) r / r!, n!/ r!( n- r)!

Этот базовый, кажущийся элементарным, но очень непростой раздел теории, проходится походя, типа любой глупыш враз себе представит ……и т.д.

Что, на самом деле, совсем не так!

И должен же найтись какой-то добрый человек, который обобщит и упростит эту заумь.

Я долго искал популярных объяснений, ничего не нашёл, и решил сделать сам.

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

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

Наиболее общая формула, описывающая все возможные события:

n ^n.

Как её нарисовать?

Рис.1.

С помощью площади обычного прямоугольника.

А насколько это логично и допустимо? Есть ли математические аналоги?

Ведь степень это многомерное пространство?

Математика, это в первую очередь абстракция, позволяющая создавать удобные для представления модели. Желательно, конечно, чтобы они были внутренне непротиворечивы.

Аналогии, конечно же, существуют. Это обычное логарифмирование степенных функций.

Суть использования логарифма в понижении уровня операции.

Степень становится произведением, а произведение суммой.

Y= n ^n

LOG (Y) = LOG (n ^n) = n * LOG (n)

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

Соответственно, для следующей формулы:

n ^r, где r < n

всё очень просто.

Рис.2.

Формула n ^r, в теории вероятностей, определяет число возможных исходов при количестве выборок из общего объёма, меньших самого объёма.

Например:

Выбираем трёх человек из пяти, постоянно возвращая выбранного обратно.

Число возможных вариантов = 5³.

Если бы мы выбирали пять раз из пяти, с возвращением, то была бы предыдущая формула =5⁵.

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

А без них, последовательная логика при описании предмета, исчезает.

Для россиян комбинаторика начинается с формулы:

n! — представляющей количество перестановок и, одновременно, максимальное число вариантов при выборе без возвращения.

И без первых двух формул, её смысл воспринимается плохо и неполно. Он усечён представлениями о перестановках.

Осмысление и доказательство этой формулы в русскоязычных вариантах требует непростых умственных усилий, в то время как англоязычный вариант Уильяма Феллера, легко выводится из n ^n, и встраивается в общую логику.

Как оно у россиян.

Есть два человека. А и В.

Перестановок — две.

АВ и ВА.

Добавляем третьего –С.

Становится сложнее.

Рис.3.

Результат, = 2 * 3 =6.

Далее по методу индукции. Добавляем четвёртого –D

Результат, = 6 * 4 =24

Добавляем пятого –Е.

Результат, = 24 * 5 =120.

Логика понятна, 1*2*3*4*……… = n!

Но, нарисовать и представить этот вариант, непросто.

А как у Феллера?

Он заходит с другой стороны.

Допустим, есть четыре человека. А,B,C и D.

Выбираем, наугад, первого. Сколько вариантов? Четыре.

Выбранного человека возвращаем обратно и выбираем снова.

Сколько вариантов? Шестнадцать! =4*4.

Любые четыре первых варианта могут пересечься с четырьмя вариантами вторых.

Рис.4.

Если мы выбираем с возвращением в третий и четвёртый раз, то вариантов:

=4*4*4

=4*4*4*4

=4⁴

= n ^n

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

Тогда вариантов:

1. =4*3

2. =4*3*2

2. =4*3*2*1

Получаются, те же = n!

Но представить себе это гораздо проще, и получаемый результат очевиден.

Более того, это очень легко нарисовать, следуя общей логике понижения уровня операций, в виде площади обычного прямоугольного треугольника.

Рис.5.

Первые три формулы успешно нарисованы и переходим к более сложным комбинациям.

Варианты с возвращением больше не рассматриваются. Они сыграли свою роль понятийной базы, и остальные формулы, отталкиваются от :

n!, который (ые) по аналогии с (n ^ n)→(n ^r), начинают усекать.

Выбираем без возвращения трёх человек из пяти.

Если бы было 5 из 5, то =5*4*3*2*1.

А если 3 из 5, то =5*4*3.

Подобная операция в мат. литературе описывается массой различных символов, из-за чего создаётся путаница.

A(r по n), (n) r (Феллер), Р(n по r), n!/( n- r)!, n(n- 1) (n- 2)(n- 3)……… (n- r+1).

A(r по n) –российский вариант.

(n) r — у Феллера, по аналогии с: (n) ^r

Р(n по r) — англоязычный вариант, от слова «permutation». Интересно, что в российских и англоязычных вариантах n и r меняются местами. В российском, r –первая или сверху, n –вторая или снизу. В англоязычном наоборот.

Теперь самое главное. А как это нарисовать?

Рис.6

Очевидно, что это площадь трапеции.

Раз предыдущий вариант, n!, был площадью треугольника, то теперь мы его усекаем.

И сразу же, становится понятна запись:

n!/( n- r)!

n! -треугольник.

( n — r)! -его усечение, когда отваливается площадь «n — r» , и остаётся трапеция. Нагляднее некуда.

И последняя, самая трудная для понимания формула, которая представляет собой биноминальные коэффициенты.

С(r по n), С(n по r), (n) r / r!, n!/ r!( n- r)!, (n(n- 1) (n- 2)(n- 3)……… (n- r+1)) / r!

С(r по n), С(n по r) — англоязычные и русскоязычные варианты сходятся на букве С, от слова «combination», но r и n, по-прежнему перевёрнуты местами.

Сама формула получается из предыдущей, делением её на r!.

С(r по n) = A(r по n) / r!

А что это такое и как нарисовать -r! ?

Раз существует треугольник — n!, означающий перестановки из числа n.

То может существовать и треугольник — r!, означающий перестановки из числа r.

И нарисовать его по аналогии, элементарно.

Рис.7.

Закрашено красным.

Т.о., геометрически — символически, наша формула, это площадь заштрихованной трапеции, поделенная на площадь красного треугольника.

Заодно, сразу же, становится понятной запись:

С(r по n) = С(n- r по n)

n!/ r!( n- r)! = n!/ ( n- r)! r!

Действительно,

Рис.8.

Отношения площадей трапеций к треугольникам, что сверху (заштриховано зелёным и жёлтым), что снизу (заштриховано синим и красным), равны.

5*4*3 / 3! = 5*4 / 2!

Как изобразить r! -стало понятно.

Осталось описать его суть.

Для этого рисуем табличку 9.

Рис.9.

Начинаем с самого общего варианта

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

Всего возможностей 25.

Далее, тоже, но без возвращения. Тогда повторов букв быть не должно. Вычёркиваем диагональ из пяти повторяющихся вариантов. (Закрашено сиреневым.)

Остаётся 20 вариантов. Замечаем, что сочетания букв над диагональю и под ней, отличаются только перестановкой. ab → ba .

Если мы перестаём их различать, то вариантов остаётся 10.

Мы прошли весь путь, от n ^n → до n!/ r!( n- r)!

5⁵, 5*4*3*2*1= 5! , 5*4*3*2*1/ 3*2*1 = 5! / (5!-3!), 5! / 2!*(5!-3!)= 10,

В завершении появляется вопрос, да, хорошо, всё просто, но что нового я сказал?

Я это нарисовал!

А что, раньше не смогли?

Нет.

А почему?

А потому, что мои рисунки математически некорректны и не во всём логичны. Это всего лишь упрощённая абстракция.

n ^n — не равно площади прямоугольника, а в одном месте,(которое наблюдательный читатель заметит) я не понижаю уровень операции.

Но это никак не помешало нам получить наглядное представление о предмете.

И в этом соль математики!

Все открытия, (на которые я не претендую), происходили примерно таким образом.

Есть задача, не решаемая в привычных аксиомах и единицах.

Все проходят мимо, но находится какой-то чудак, который создаёт новое, искусственное, абстрактное пространство, в котором задача решается, и появляется новый раздел математики или понятие.

Самый простой пример — отрицательные числа.

Совсем недавно, человеческий мир не понимал что это такое. Число баранов не бывает минус один, и выражение: y = 4–5 не имело смысла.

Сегодня, особенно на бирже, отрицательным счётом никого не удивишь.