Форма входа

Корзина

Ваша корзина пуста

Поиск

Календарь

«  Июль 2018  »
ПнВтСрЧтПтСбВс
      1
2345678
9101112131415
16171819202122
23242526272829
3031

Наш опрос

Оцените мой сайт
Всего ответов: 94

Статистика


Онлайн всего: 1
Гостей: 1
Пользователей: 0




Вторник, 18.12.2018, 14:18
Приветствую Вас Гость | RSS
Фондовый рынок
Главная | Регистрация | Вход
Блог


Главная » 2018 » Июль » 15 » Формулы комбинаторики. Как запомнить и осилить.
05:34
Формулы комбинаторики. Как запомнить и осилить.

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

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

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

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

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

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

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

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

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

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

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^3.

Если бы мы выбирали пять раз из пяти, с возвращением, то была бы предыдущая формула =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^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.

 

a

b

c

d

e

a

aa

ab

ac

ad

ae

b

ba

bb

bc

bd

be

c

ca

cb

cc

cd

ce

d

da

db

dc

dd

de

e

ea

eb

ec

ed

ee

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

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

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

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

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

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

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

5^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 не имело смысла.

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

Просмотров: 382 | Добавил: Воронноров | Рейтинг: 5.0/1
Всего комментариев: 5
1 mvalera7  
забавная абстракция. Можно описать, что то наподобие про "Биномиальноераспределение"
http://k-tree.ru/articles/statistika/raspredelenie_puassona

Очень туго идет понимание. Формулы то не сложные, но бес реального понимания по настоящему случайной выборке, когда следующее событие не зависит от предыдущих событий\нахождений результата  - всё бесполезно.

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

На счёт, «по-настоящему случайной выборки». На практике этого не бывает.А в теории, это просто совокупность равновероятных событий,порядок следования которых мы не знаем.
Поэтому, случайная, означает равновероятная.
Событий n, у каждого вероятность 1/ n, порядок следования неизвестен.
Будет, время попытаюсь нарисовать абстракцию с Пуассоном.
Пока кратко. Это обычная аппроксимация биноминального распределения, которое по форме близко к Гаусовской кривой, если составляющие
бинома равны по величине.
Х=У  (Х+У)^n
Проблема с представлениями бинома в слове «би» =два.Там где два, начинается диалектика и  фрактальность.
С одной стороны число составляющих  бинома растёт, с другой, их величина постоянно падает.
λ  -это усреднённая вероятность на какую-то единицу.
n- число единиц, вероятность которых ищется при заданной   λ .
λ ^ n   - прямоугольник.
e^-λ / k! –нелинейный коэффициент,  сжимающий и растягивающий прямоугольник.
На скорую руку, и летом, мне лучше не придумать.
Кстати, по ссылке, по-моему, есть ошибка.
f(4) = P(k = 4) = λ^k*e^-λ / k! = 5^2 * e-5 / 2! = 0.084 = 8.4%
к=2,  а они что пишут?

3 mvalera7  
Да, ошибка есть. Мне самому пришлось в экселе формулы расчетов рисовать.
Просто у меня в реальных экспериментах постоянно вылезает, от 300-600% от равновестной\средней. Т.е. той самой лямда.
Странно весьма, куча событий при 20-70% и тут два-три по 200-800%.
Очень интересует сколько брать событий по минимуму, чтоб точность была хотя бы 95% от "равновестной"

0
4 Воронноров  
Думаю, что я смогу достаточно подробно описать суть биноминального распределения и как выводится формула Пуассона.
Но вот практическое его применение мне представляется  имеющим мало смысла.
Когда оно используется, то априори предполагается, что наши вероятности наступления и не наступления события просто растягиваются в биноминальный многочлен аналогично кривой Гаусса.
При этом при росте числа испытаний многочлен всё длиннее, а вероятности в данной точке всё меньше.
И в предельном абстрактом варианте это падение вероятностей от числа испытаний в данной точке выражается формулой Пуассона.
Что, кстати, противоречит исходной посылке о том, что  исходные вероятности постоянны.
Мягко говоря, это очень теоретическое предположение имеющее смысл для бесконечно малых и больших.
И, на мой взгляд, реальный смысл может иметь только функция интегрального распределения,- соотношение наступления и не наступления события в точке, а никак не величина в ней.

5 mvalera7  
Ну как сказать, "реальность такова что компьютеры при расчётах почему то весьма далеки от реальности выраженной нам в чувствах человека" - во загнул, мозги ещё не закипают от солнышка.
Да ты прав, как раз интересует то что ты написал.
Попробую описать ситуацию:
Комп ведет поиск решения по сложному алгоритму. В среднем\лямда решение находиться за 1 час на моём компе. Количество попыток не ограниченно, но имеет важнейшее значение - машинное время не бесплатно и ограниченно.
В реальности решение может находиться и за 20% от среднего и за 280%, у меня бывало и 800% - но это редчайший случай.
Нужно узнать, сколько брать переборов (времени) чтоб приблизиться к среднему значению в 1 час хотя бы с точностью 95%. Двадцать часов, сто?
smile
У меня упорно выходит: где то 11-13 часов\средних решений. Но чувствую пахнет жареным, где то черт бродит рядом.

Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]

Copyright MyCorp © 2018