Числа Каталана
2023 ж. 6 Қыр.
32 158 Рет қаралды
В ролике рассматриваются три внешне непохожих комбинаторных задачи, которые приводят к одной и той же реккурентно определяемой последовательности - числам Каталана.
Ключевые слова: комбинаторика, рекурсия.
Мартин Гарднер "Числа Каталана" kvant.mccme.ru/1978/07/chisla_...
Числа Каталана • Числа Каталана
Производящая функция чисел Каталана • Производящая функция ч...
И всё таки она сходится! • И всё-таки она сходится!
Спасибо! Как всегда интересно! 🌺
Посмотрел видео и осознал, насколько я отупел к своим 40 годам. Плачет.
Таш фигня, это от просмотра видосиков.
@@SamarraVadim Ага. Само пройдёт. 🙂
было бы интересно узнать многообразие задач которые приходят к числам каталана еще)
Большое спасибо за ваш труд!=)
Рахмат Вам из Башкирии!
Бик зур рахмат.🙃
Спасибо
Недавно стлокнулся с числами Каталана, сам того не зная. Вторая задача, где порядок умножений, она встречается внутри другой задачи. У нас есть набор чисел. Например 6 цифр из номера автобусного билетика. Нужно между цифрами расставить знаки арифметических действий и скобки, чтобы получилось какое-то наперёд заданное число, например, 100. Всего вариантов расставить 5 знаков действий со скобками между 6 цифр будет как раз C5 * 4^5 = 42 * 1024 = 43008. Написал считалку, которая перебирает все варианты и получает всё множество ответов. Позже добавил ещё пятое действие: объединить две соседних цифры в двузначное число. Результат получился интересный. У некоторых наборов чисел получается плотное покрытие нескольких сотен первых чисел. Например, набор 383862, из него можно получить все числа подряд от 0 до 316 включительно 3*(8/3-(8-6))-2 = 0 3+8/(3-(8+6)/2) = 1 3-(8+3-8)/(6/2) = 2 3+8-3-(8-6/2) = 3 ... 3*8*3+(8+6)*2 = 100 ... (3+8+3*8*6)*2 = 310 3+(8+3)*(8+6)*2 = 311 3*(8-(3-8))*(6+2) = 312 3*83+8*(6+2) = 313 (3+(8+3)*(8+6))*2 = 314 3+8*38+6+2 = 315 (38+3)*8-6*2 = 316
Думаю, вас заинтересует видео про число 10958 от Numberphile
@@timurpryadilin8830Действительно, 10958 не составляется. Даже если добавить степени и логарифмы. А конкатенация у Мэтта нечестная. Циферки соседние собирать в кучку здорово, а выражения - уже как-то не очень честно. Нужно факториал добавить в список операций, с ним 10958 посчитается легко.
10958 с корнем произвольной степени: 1*(23+45*root(6/(7+8), 9)) = 10958 Здесь корень 6/15 степени из 9, это 9^(15/6) = 9^(5/2) = 3^5 = 243 243*45+23 = 10958
Очень интересно, спасибо! 👍 Но у меня просьба. Можете ли вы также подробно и обстоятельно разьяснить в чём суть задачи, которую решал Грэм прежде, чем досчитал до своего фантастически огромного числа G64, попавшего в книгу рекордов Гинеса? Для меня остаётся загадкой как его ЧЕЛОВЕЧЕСКИЙ интеллект (в отличие от инопланетного) смог различать совершенно неразличимые ни для людей, ни для компьютеров по своей огромности числа начиная с g2 ? Как он понимал, что аабсолютно неосознаваемые по своей огромности числа g2, g5, g10, g30, g60 всё ещё недостаточны для решения его задачи, а вот именно g64 уже достаточно ??? 🤔
"Математику лишь затем изучать нужно, что она ум в порядок приводит!" 😅
Ломоносов
@@user-hi5fy6wv5j - пулю получишь - это давно известно. -- - и в Суде - владение боксом это отягчающее обстоятельство, поэтому со времён ссср кто владеет спортом - никого не трогает.
Здорово ! У Бориса Трушина было видео, где он использовал числа Каталана, чтобы строго решить задачу по теории вероятности. В частности, он использовал без доказательства производящую функцию этих чисел. Было бы здорово, если бы вы её вывели на своём канале.
Из рекуррентного соотношения сразу следует, что производящая функция f(t) удовлетворяет квадратному уравнению tf^2=f-1, откуда, учитывая `f(0)=1', получаем: f(t)=(1-sqrt(1-4t))/2t
Молодцы, реально полезный контент ❤
Спасибо большое за ответ Я изучал подобную задачу только вместо умножения я возводил в степень так как там разные результаты например a^(b^c)≠(a^b)^c А я всё немог понять какая же там закономерность ? 😂😂😂
Ну осталось сделать шаг вперёд и рассмотреть числа Гиппарха. :) В вики Числа Шрёдера - Гиппарха Сколько можно записать утверждений, имея n постулатов? Нюанс в том, что кроме сложения/умножения ещё есть операция отрицания. Ну и в интерпретации со скобками, сколько может быть правильных скобочных последовательностей, если у нас n пар скобок и k типов скобок?
Хо-хо! Оказывается числа Каталана имеют отношения к реляционным СУБД! Они описывают варианты построения порядка соединения таблиц в запросе! Мне, как разработчику БД это любопытно!
Автоматически выбираете варианты? Хм... Если да, то может всё в целом где-то пошло не так, что такое нужно?
@@user-hi5fy6wv5j не автоматически, а основываясь на оценке стоимости. Что именно, по-вашему, пошло не так?
@@EvgeniyFadeev, если не автоматически, то вероятно всё идёт так. А что может быть именно пошло не так, как же я сказал бы вам, по-моему, если я проекта во всех деталях не изучил? Странно задавать такие вопросы.
@@user-hi5fy6wv5j ничего не понял... Можете внятно сформулировать свой вопрос?
Цікаво знати, дякую
С0 каталана в первом примере не очевидно, почему оно не 0?
В силу общей формулы мы знаем, что С0*С0 = С1, и ещё мы знаем, что С1=1, поэтому и С0=1. А потом мы придумываем, как это истолковать: состояние, в котором ничего нет, мы можем получить единственным способом:)
@@user-nq2mj6rz9q Было бы лучше, если бы вы не считали себя "мерой всех вещей", а вместо этого попытались понять объяснение. (Но это, наверное, невозможно...)
Объяснение непонятное. Не понятно из чего была выведена итоговая формула(откуда взяли умножения и сложения, из объяснения это неочевидно) и почему С0 = 1, ведь когда у нас нет ни одной пары точек на окружности, то мы не можем провести ни одной хорды
Мне тоже пожалуйста объясните 😅
Мы считаем не хорды, а способы их расставить. Если нет ни одной хорды, такой способ очевидно всего один, вот мы и говорим, что С1=1 (по обе стороны от проведённой хорды нет ни одной хорды), и С0=1 (здесь просто нет ни одной хорды). И это истолкование созласуется с нашей формулой С1=С0*С0. Что касается сложения и умножения, это самый первый урок по комбинаторике, смотрите его здесь: kzhead.info/sun/hZmqcZZle4xoZZs/bejne.html
Не понял я почему С0 = 1. Может кто объяснит. Посему C не равен 0?
Нужно связать точки отрезками так, чтобы не осталось несвязанных точек. Когда точек и вовсе нет, результат достигается всего одним способом(ничего неделание это тоже способ, так как выполняется условие: отсутствие свободных точек). Так С0 = 1.
Для всех, кто задаёт вопрос, почему С0 = 1, а не 0. Дело в том, что С0 - это не число хорд, а число СПОСОБОВ провести такие хорды. И поскольку хорд нет, число способов равно 1.
Почему Со равно 1? Ведь оно обозначает число хорд, проведённых через точки на окружности, когда этих точек ноль. Логично было бы Со=0
С0 - это не число хорд, а число СПОСОБОВ провести такие хорды. И поскольку хорд нет, число способов равно 1.
Вообще Гарднер мой любимый писатель математик... А профессора Сляпенарского даже Гугл поиск не знает...
Окружность с 3 парами точек (т.е. с 6 точками) напоминает структуру бензола и его валентные изомеры (изомер Дьюара - 3 штуки, и изомер Кекуле - 2 штуки).
Одна задачка, тоже вроде интересная и с виду простенькая, привела к числу Грэма. Математикой только интересуюсь, и уважаю, но не увлечён. Однако при попытке осознать это число, понял что "свихнуться" очень просто. Пожалуй их точных наук математика самая великая.
Формулировка С0 не правильная, вы говорите что это количество способов провести хорду, но при нуле точек ни одну хорду провести нельзя. Правильнее сказать что это число состояний окружности. Раз никакие хорды провести нельзя - значит состояние будет единственным.
мне чего-то не очевидно что число способов провести хорду на окружности без точек равняется 1. Можете объяснить?
А зачем считать варианты ходов ладьи, да ещё и не пересекая диагональ? Математика на 90% абсолютно бессмысленна и потому абсолютно скучна. Сами математики что-то такое знают про её применение в живой жизни, но фанатично хранят секрет.
Вместо йога подставить математика :) Я попросил подвыпившего йога (Он бритвы, гвозди ел, как колбасу): - Послушай, друг, откройся мне, ей-богу, С собой в могилу тайну унесу! Был ответ на мой вопрос прост, И поссорились мы с ним в дым. Я бы мог открыть ответ тот, Но йог велел хранить секрет - вот!
Сказал человек на ютубе, где сжатие видео реализовано через бесполезное преобразование Фурье, придуманное для обработки сейсмологических волн при отслеживании подземных ядерных взрывов. Превьюшки на ютубе кодированы дискретным косинусным преобразованием. А телефон шлёт зашифрованный сигнал бесполезным симметричным шифром Rijndael, в основе которого бесполезное умножение Галуа. Соединение устанавливается при помощи асимметричного RSA, в основе которого бесполезная модулярная арифметика, простые числа, функция Эйлера и малая теорема Ферма. Можно ещё час перечислять, где вокруг используется то, что раньше казалось бесполезным, но я уже устал.
@fhtagnfhtagn, Вам нельзя преподавать. Если, не дай бог, Вы этим занимаетесь, Вы вредитель. Вопрос не в том, где используется математика, а в том, как её преподавать тем, кто не в курсе всего того, что Вы устали перечислять. Для Вас и для тех учителей, которые пропустили лекции по психологии - то, в чём мозг не видит смысла, он не поймёт и не запомнит.
Проблема в том, что вы сразу встали в позицию не ученика, но оценщика, "меры всех вещей". А таких людей обычно не пускают в приличное общество. Научитесь спрашивать, и вам многое откроется.
@@fhtagnfhtagnэто алгоритм быстрого преобразования Фурье, изначально оно было для решения задач теплопроводности
Интересно, а зачем это нужно ?!!