Пользователь
0,0
рейтинг
10 января 2013 в 11:42

Разработка → Числа Каталана из песочницы

Несомненно, самым замечательным математическим фактом является тождество . В нем удивительным образом сошлись, казалось бы, совершенно не связанные константы из разных областей математики. Доказать это тождество не так сложно, но объяснить его, понять глубинный смысл, удается немногим.
В качестве еще одного замечательного факта хотелось бы вспомнить числа Каталана, которые удивительным образом всплывают в самых разных комбинаторных задачах. К сожалению, они выпадают из рассмотрения типовой школьной программы, но уверен, что любой специалист компьютерных наук должен быть знаком с ними.

Само число Каталана выражается формулой C(n) = (2n)!/n!(n+1)!, где восклицательный знак, как обычно, обозначает факториал. Начало последовательности выглядит так: 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796…
Английская Википедия утверждает, что известно, как минимум 66 различных конструкций, которые приводят к появлению чисел Каталана. Вот некоторые из них:

  • Правильные скобочные последовательности – наборы открывающихся и закрывающихся скобок, в которых каждой открывающейся скобке соответствует закрывающаяся. Число возможных последовательностей с фиксированным числом пар скобок выражается числом Каталана. Например, 14 правильных последовательностей из четырех пар скобок:
    (((()))), ((()())), ((())()), ((()))(), (()(())), (()()()), (()())(),
    (())(()), (())()(), ()((())), ()(()()), ()(())(), ()()(()), ()()()()

  • Двоичные деревья – деревья, из каждого узла которых (кроме листьев) выходит ровно две ветки. Количество бинарных деревьев с заданным числом листьев – число Каталана. На рисунке представлены пять деревьев с 4 листьями в каждом.

    Такие деревья уже обсуждались на Хабре

  • Любые деревья. Число неизоморфных деревьев с заданным числом вершин также равно числу Каталана. Такие деревья тоже обсуждались

  • Монотонные пути в квадрате – маршруты из левого нижнего угла квадрата в правый верхний, которые идут по линиям сетки вверх или вправо и не заходят выше диагонали. На рисунке все такие пути для квадрата 3x3.


  • Триангуляции многоугольника. Количество различных триангуляций выпуклого многоугольника диагоналями равно числу Каталана.


  • Разбиение вершин многоугольника на пары. Четное число точек на окружности можно объединить в пары непересекающимися хордами. Число способов таких объединений также равно числу Каталана.


  • Таблица Юнга – прямоугольник, заполненный последовательными числами так, чтобы они возрастали во всех строках и столбцах. Число таблиц Юнга размером 2xn также выражается числом Каталана.



Для каждой из этих конструкций можно либо по индукции, либо реккурентными соотношениями доказать, что число соответствующих объектов выражается числом Каталана. Не буду останавливаться на этих доказательствах – их можно найти в учебниках по дискретной математике. Также есть некоторые замечательные соотношения, которые можно получить, используя некоторые из упомянутых построений. Но это требует написания громоздких формул, чего хотелось бы избежать. Сейчас интереснее другое – неужели совпадение всех этих количеств для совершенно разных вещей случайность?
Конечно же, нет. Связь этих конструкций гораздо глубже. Можно построить взаимнооднозначное соответствие между этими объектами и некоторые из таких соответствий я попробую продемонстрировать. Помимо простого любопытства это имеет и некоторую практическую ценность. Например, задачу о генерации всех бинарных деревьев (решение которой в лоб неочевидно) можно свести к гораздо более простой задаче о генерации скобочных последовательностей.

Соответствие 1

Очень легко построить соответствие между скобочными последовательностями и монотонными путями в квадрате. Читая скобочную последовательность слева направо, будем строить путь, начав из левого нижнего угла, – для каждой открывающейся скобки нарисуем горизонтальный отрезок, для закрывающейся скобки – вертикальный.
Так как в последовательности было равное число открывающихся и закрывающихся скобок, то путь в итоге закончится в правом верхнем углу, а тот факт, что каждая открывающаяся скобка стоит раньше соответствующей ей закрывающейся скобки (ведь последовательность — правильная) гарантирует нам, что путь не перейдет в верхнюю половину квадрата. Очевидно, что это построение обратимо и из каждого монотонного пути можно получить скобочную последовательность.
На приведенном рисунке соответствующие скобки и отрезки отмечены одним цветом. Хорошо заметно, что отрезки, соответствующие одной паре скобок «видят друг друга»:


Соответствие 2

В качестве второй задачи построим соответствие между правильными скобочными последовательностями и таблицами Юнгам 2xn. Тут тоже все просто. Пронумеруем скобки слева направо. Если скобка открывающаяся, то соответствующее ей число пишем в верхнюю строку. Если закрывающаяся, то в – нижнюю. Так как i-ая открывающаяся скобка всегда стоит левее i-ой закрывающейся, то число соответствующее открывающейся скобке будет меньше числа, соответствующего закрывающей. А значит, верхнее число в таблице окажется меньше нижнего в той же колонке, то есть из правильной скобочной последовательности мы получили таблицу Юнга. Это построение также обратимо, а значит получено взаимно-однозначное соответствие.


Соответствие 3

Теперь займемся бинарными деревьями. Очень легко увидеть соответствие между бинарными деревьями и расстановками скобок в выражении с однородными операциями, но это дает несколько другие последовательности. Для привязки бинарных деревьев к правильным скобочным последовательностям надо воспользоваться несколько другим подходом. Воспользуемся стандартным обходом дерева и пронумеруем вершины (корень примем за 0) в порядке обхода. Теперь, если при переходе к числу I мы спустились от родителя к ребенку, то на i-ое место ставим открывающуюся скобку. В противном случае ставим закрывающуюся.

Дерево – бинарное, поэтому у каждого узла есть сосед. А значит, спустившись к ребенку и поставив открывающуюся скобку, мы рано или поздно доберемся до его соседа и поставим закрывающуюся скобку. Это гарантирует правильность получившейся последовательности. Построение легко обратить и взяв за основу скобочную последовательность получить бинарное дерево.
Заметим, что если в скобочной последовательности n пар то соответствующее дерево имеет n+1 лист.

Соответствие 4

Для построения соответствия между триангуляциями многоугольника проще всего использовать бинарное дерево. На этот раз мы занумеруем в нем все листья слева направо (остальные узлы пометим буквами). Для триангуляции возьмем многоугольник, в котором вершин на одну больше, чем листьев в дереве. Одну из сторон этого многоугольника отметим, как стартовую, а остальные занумеруем (для наглядности – против часовой стрелки).
Далее выполняем следующую процедуру – если две вершины дерева соседние, то соответствующие стороны многоугольника «стянем» диагональю, которую пометим той буквой, которой помечен родитель этой пары узлов в дереве. Далее продолжаем процедуру «стягивания» пока от многоугольника не останется единственный стартовый отрезок.

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

Вместо эпилога

Ну и в заключение приведу табличку, в котором изображено соответствие объектов для третьего числа Каталана.
Богданов Андрей @bay73
карма
54,5
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (105)

  • +10
    первая формула вроде бы минус единице равна? :)
    • +5
      Конечно же, пока картинку рисовал минус потерял. :(
    • +2
      Не вроде бы, а совершенно точно.
      • +1
        Поправил
    • +5
      а если эту единицу перенести влево, то справа получится ноль. И тогда формула будет показывать соответствие между пятью константами: e, pi, i, 1, 0
  • +42
    Ага! 42 — одно из чисел Каталана
    • +29
      Ваш комментарий просто обязан набрать ровно 42 плюса (:
      • +1
        Сделано :)
      • +4
        Наблюдал подобное недавно в фейсбуке, где одна компания обещает приз N-тысячному пользователю, поставившему лайк. Прелюбопытно наблюдать этот момент. Все затаившись ждут приближения, лайки набираются медленно. И вот когда остается (n-1)995 то начинается… В доли секунды происходит резкий перескок, после чего волна дислайков…
      • +1
        Сейчас было бы 43, если бы я страничку не перезагрузил.
    • –7
    • +3
      Я чуть было не нарушил равновесие, в последнюю наносекунду отвел указатель мыши и щелочек пришелся по белому полю (:
      • 0
        Я бы исправил, так что закон равновесия в силе!
  • +7
    но объяснить его, понять глубинный смысл, удается немногим

    Может быть тогда объясните нам его смысл? Мне правда стало это более интересно, чем числа Каталана. Как оно хотя бы называется, это тождество?
    • +3
      Обычно его называют Тождеством Эйлера.
    • +1
      Да просто в формулу Эйлера подставьте Пи вместо x, получите так называемое «Тождество Эйлера».
    • +4
      Я недавно пробовал объяснить: written.ru/articles/science/complex_exponent
    • 0
      +1=0: «Это абсолютно парадоксальнo, мы не можем понять это, и мы не знаем, что это значит, но мы доказали это, и поэтому мы знаем, что это должно быть правдой.» — Бенджамин Пирс
      • 0
        Ньютон считал, что мы можем что-то посчитать, даже если не понимаем физического смысла, так во всяком случае в книге «Математика. Утрата определённости» говорится.
  • +8
    Скобочки, они прекрасны! (.)(.)
    • +1
      Lisp же :)
      • +2
        Так вот отож!
  • +36
    А что, это идея.

    1. Выбираешь любую область точных знаний.
    2. Выбираешь какую-нибудь простенькую, но занятную, штуку.
    3. Пишешь на Хабр.
    4. ???
    5. Видимо, таки PROFIT

    Хинт: из книжек Перельмана можно понабрать материала примерно на 100500 таких статей.
    • +5
      А если добавить ещё книжки М.Гарднера… там материал даже современнее.
      • +1
        О, да, у меня были «крестики-нолики» и посложнее: «математический цветник». Зачитаны до дыр :)
    • +13
      Тут такая штука, что в типичном вузе типичный преподаватель никогда и ни за что не расскажет о связи математики с реальностью, если это сложнее интеграла, а если начинаются всякие поля, кольца, ТФКП и т.п., то вообще всё грустно становится. Ну и Хабр же не только программисты и суровые айтишники читают. Кто-то картинки рисует, кто-то сайты верстает.
      • 0
        А преподаватель это знает? Возможно, ему известен десяток-другой применений комплексных чисел. Но объяснить, как они связаны с реальностью? А как они связаны? И как связаны с реальностью конечные поля? Неархимедовы множества? И т.д.
        • +12
          Я имею в виду, что должно быть обозначено зачем существует та или иная теория. Формулы не из воздуха берутся, как правило, они решают конкретные задачи. Если преподаватель не может даже примерно обозначить для чего применяется та или иная теория, то учиться у него сложно, потому что это не только зубрежка, но и бесцельная зубрежка. Вроде учишь что-то, а откуда ноги растут, для чего применяется не знаешь, нет системы в голове. Такое и учить сложнее, и шансы на какое-то понимание малы.

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

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

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

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

          Допустим, я электротехник по образованию (гипотетически, это не про меня) и я разумеется в одном из семестров буду изучать переходные процессы в электрических цепях. Если мне за год до этого на математике по курсу ТФКП скажут, что там во все поля комплексные числа, преобразование Лапласа и прочии Дирихле, то будучи разумным человеком, я озабочусь по мере изучения прикидывать практический смысл той или иной формулы. Если мне объяснят, что можно обойтись без комплексных чисел, без преобразования Лапласа, но покажут, что объемы вычислений вырастают на многие порядки, то я соображу, что лучше подучить чуток матана, чем потом по триста листов бумаги исписывать заместо счета в уме.

          Как-то так. Длинновато…
          • 0
            Интересно, что на вопрос «для чего нужны конечные поля», сейчас можно услышать только один ответ — «криптография». Все остальные области применения, если они и были, давно забыты.
            • +3
              Конечные поля еще применяются в электротехнике, цифровых фильтрах и т.п. Еще там рядом же теорема о вычетах, которая еще большее применение имеет. Но в целом да, это про криптографию, но лишь потому что там очень тесные завязки с теорией чисел.

              Тут нужно понимать, что претензии на отсутствие практической значимости обычно адресуются именно абстрактной алгебре. Но на то она и абстрактная. У абстрактной алгебры «заказчик» вся остальная математика, которая уже поставляет теории более приземленным наукам. У абстрактной алгебры такая специфика, что до реального применения порой проходят десятки лет, она бежит впереди поезда.
              • 0
                Про конечные поля в электротехнике не слышал. С цифровыми фильтрами понять можно, хотя там все лавры пытается забрать БПФ. А «претензии на отсутствие значимости»… мне казалось, что их больше адресуют бесконечномерным пространствам и функциям на них, неизмеримым множествам, теории «очень больших» множеств и прочим играм с наборами аксиом.
                • +8
                  Это сейчас такие претензии. В историческом же формате это вечный вопрос к абстрактной математике. Первое время даже сами математики не понимали абстрактных. Мол, «че за фигню вы тут понапридумывали, абстракции какие-то, зачем вы нужны вообще, дискредитируете только нас»…

                  Те же бесконечные тригонометрические ряды довольно сложно осознать. Фурье весьма так всем мозг порвал в своё время. Ведущие ученые того времени как на дурака на него смотрели, потому что разложить функцию в ряд, мягко говоря, неочевидный ход, когда на дворе 19 век.

                  Бесконечность вообще сложная и хитрая штука, большинство людей просто запоминает некоторые правила работы с ней, и не более того. Те же ряды Фурье. Там же бесконечное число элементов, но как-то пользуются и не особо напрягаются. Почему бесконечное-то? Почему не конечно? Причем ряд Фурье он ведь из гильбертова пространства, а оно допускает бесконечномерность. Вот вам и пример реальной пользы бесконечномерного пространства да еще и из 19 века.

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

                  Например, физики веками работали с 1-2-3-мерными пространствами. Но стало как-то «не хватать», чтобы теорию с реальностью соотнести. Потребовались 10-20-30 размерностей, и внезапно есть бесконечномерные пространства из абстрактной алгебры, которая этот вопрос десятки лет назад решила, и на которые дико смотрели и не понимали зачем это вообще всё.

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

                  Абстрактная алгебра как следует из названия абстрактна. В ней уходят от конкретных деталей.
                  • 0
                    Если вы в конце говорите про теорию струн, то она еще не доказана
                    • +1
                      Она и не обязана быть доказана, чтобы показать, что непонятные вундервафли из абстрактной алгебры могут иметь практический смысл. Без абстрактной алгебры физики бы еще ничего и не начали доказывать, даже не сформулировали бы, что хотят проверить на деле.
                • 0
                  В принципе, БПФ можно считать в поле по конечному модулю :)
                  • +1
                    Можно. Но поможет ли это в обработке сигналов?
          • 0
            Вы поставили мой основной вопрос обучения в ВУЗе. ЭТ не была моей основной спецухой, но меня до сих пор интересует какой физический смысл имеет Z-преобразование и комплексное преобразование при расчете цепей.
            • +5
              У него нет физического смысла. Это абстракция, инструмент. Практический инструмент. Z-преобразование это просто преобразование Лапласа, где ядро Лапласа заменено буквой z. :) Ну и вообще это из операционного исчисления. Нужно оно за тем, что решать системы алгебраических уравнений на порядки проще, чем системы дифференциально-интегральных уравнений. Z-преобразование как раз тот случай, когда вообще можно не понимать, как это работает, но решать реально сложные задачи.

              Правила преобразования на фоне решения без этого преобразования крайне просты, можно сказать, что даже на порядок. В операторном методе расчета переходных процессов в нелинейной цепи в ходе решения получается система дифуравнений высокого порядка. И порядок быстро растет с ростом количества узлов и элементов. В достаточно сложно цепи можно получить систему дифуравнений 5-10-20 порядка. Решение такой системы это по большому счету неподъемная задача для большинства людей (инженеров, которым это нужно рассчитать). Но решить систему алгебраических уравнений 10-20 порядка уже вполне реально, даже не будучи гением.

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

              Что касается комплексных чисел, то в данном случае это так же, всего лишь абстракция и инструмент. Можно решить без комплексных чисел все эти задачи, но с ними решение увеличивается кратно.
              • 0
                Я вспомнил что такое быть студентом.
              • 0
                Огромное спасибо! Как жаль, что не вы были моим преподавателем по физике на 1-2 курсе! Я мог бы быть намного образованнее.
      • 0
        Нам в типичном вузе на типичном втором курсе на типичной дискретке про числа Каталана рассказывали. И про парные скобочки тоже. А ТФКП тоже бывает невероятно занимательно. Почитайте книжку «Простая одержимость», например :-)
        • 0
          За книжку спасибо. А что касается вашего случая, то вам может просто повезло. Ну или физмат поди какой? Если это общеобразовательная программа для вуза, то теории чисел там вообще нет, а комбинаторика очень кратко и поверхностно дается в разделе теорвера сугубо с целью решения задач теорвера. ТФКП у меня к примеру было, а вот про числа Каталана никак. Хотя и два года математики. Ну и мой поинт всё же не в том, что про числа Каталана никто не знает, а в том, что часто никто не расскажет в чем их смысл, чего умеют, кому нужны.
          • 0
            Физический факультет, кафедра физико-технической информатики. Для меня странно звучит фраза «общеобразовательная программа для вуза». В вузе у всех специальность, о каком общем образовании речь? Ну можно говорить об общеобразовательной психологии или физкультуре на технических специальностях. Теория чисел наверняка есть на математических факультетах на соответствующих направлениях.

            Я понимаю, что числа Каталана не у всех были, а если у кого и было, многие успели забыть. Статья, безусловно, полезная, я даже плюсанул её :-)
            • 0
              В высшем образовании есть обязательная часть, обязательным минимум. Даже на технических специальностях математика преподается от 1 до 5 лет. Плюс она еще и разная преподается. Количество лет матана может быть одинаковым, а изучали люди разное.
    • 0
      Да можно даже любую актуальную статью перевести по ИТ или из поиска по нерусским Википедиям, если на русском такого материала нет.
    • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    Поясните пожалуйста еще раз построение скобок из бинарного дерева, я что-то не очень понял ваше объяснение. С другой стороны, просто посмотрев на картинку понятно, что открывающая скобка соответствует левому поддереву, а закрывающая — правому. Поэтому, применив стандартный обход и смотря на то, какое в данный момент поддерево мы взяли, тупо ставим нужную скобку в очередь. И получаем в итоге то, что хотели.
    • –1
      я так понял это совпадение, там скобки зависят от того родитель узел или нет
      • +1
        Скобки зависят от того, левый он сын или правый. Вершины нумеруются в порядке «голова — левое поддерево — правое поддерево». Голове всего дерева никакая скобка не соответствует.
        • 0
          Теперь, если при переходе к числу I мы спустились от родителя к ребенку, то на i-ое место ставим открывающуюся скобку. В противном случае ставим закрывающуюся.


          про нумерацию — Да, согласен, но про открытую и закрытую понял то, что написал. Поправьте, если опять ошибся.
          • 0
            Родителей в этом дереве меньше, чем листьев. Так что баланс не сойдётся, неважно, оставляй голову для какой-нибудь скобки, или нет. А вот количество левых и правых детей одинаково.
    • +1
      Да, вы все верно поняли, а я не очень понятно написал. Открывающуюся скобку ставим, если сооответствующий узел — левый у своего родителя. Собственно это и означает, что мы «спускаемся» к нему при обходе, ведь всегда при обходе из родительского узла мы сначала попадает в левого ребенка.
  • +1
    <sarcasm> Количество пальцев на руке — опять число Каталана! Количество глаз на голове — тоже!
    • +6
      Кутузов, Михаил Илларионович имеет на этот счет особое мнение…
      • 0
        Это киномиф, не носил он повязки, и оба глаза у него работали.
        • 0
          Так я про то и говорю — поскольку как минимум один глаз явно натуральный, а со вторым какая-то информационно-дезинформационная неразбериха то надо предположить что второй глаз комплексный. А поскольку комплексное число не входит во множество Каталана то вот мы и приходим к моему первому утверждению.
  • +8
    Если вдруг кому-либо интересно доказательство:
    1. Для доказательства нам потребуется формула Эйлера (e^ix=cos(x)+i*sin(x) ):
    Получить ее очень просто, достаточно разложить в ряд Тэйлора e^ix
    e^ix = 1 + ix/1! + (ix)^2/2! + (ix)^3/3!… (ix)^n/n! + o(n)
    e^ix = ( 1 — x^2/2! + x^4/4! +… ) + i*( x/1! — x^3/3! + ..)
    Очевидно*, что первая скобка равна cos(x), а вторая скобка sin(x) => e^ix = cos(x) + i * sin(x)
    2. Получим формулу Эйлера, для этого положим x = pi
    e^i*pi = cos(pi)+i*sin(pi)
    e^i*pi = -1 +i*0
    e^i*pi = -1

    P.S: простите, что не LaTex
    __
    i — мнимая единица (sqrt(-1))
    * — см. разложение sin(x) и cos(x) в ряд Тейлора
    • +8
      Доказательство это хорошо. Где бы теперь найти глубинный смысл… Разве что действительно попытаться объяснить, что умножение на e^(i*x) это поворот комплексной плоскости на угол x, а потом сказать, что поворот на pi радиан — это центральная симметрия, т.е. умножение на -1…
      • +2
        Мне больше всего в свое время понравилась статья «Мировые константы и в основных законах физики и физиологии»:

        arbuz.uz/t_e_pi.html
      • +2
        Понимать глубинный смысл комплексный чисел, ещё и на реальных примерах — цель, как минимум, не очень благодарная. К сожалению.
        • +2
          Труднее всего понять, «почему». Причём вопросы идут по возрастающей — почему перемещения и подобия плоскости — линейная функция на C. Почему, если добавить инверсию, получатся дробно-линейные функции, а значит, ничего кроме перемещений, подобий и инверсий мы не получим (нет, доказать это легко — но почему оно сработало?) Почему такая связь между С и гармоническими функциями и конформными отображениями. Почему теорема Лиувилля не работает для плоскости. Почему С алгебраически замкнуто, а R нет, и как это повлияло на существование нашего мира. И как комплексные числа влезли в теорию волновых функций. Почему перемещения плоскости описываются в удобных терминах комплексных чисел, для пространства приходится обращаться к некоммутативным кватернионам, а дальше — вообще жить с матрицами.
      • 0
        Очень даже!
        Ловите плюс.

        Проще не куда!
      • +1
        Хорошее объяснение!
        Только вот мне еще в универе прямо таки хотелось более глубоко понять эту формулу.
        Вот например, когда объясняют интеграл и визуализируют его через площадь фигуры, все становится понятно.
        А тут нет…
    • 0
      e^(π*i) = cos(π) + i*sin(π) = -1 + 0*i = -1
    • 0
      1. Для доказательства нам потребуется формула Эйлера (e^ix=cos(x)+i*sin(x) )

      У нас формула Эйлера была определением операции возведения в мнимую степень.
      То есть, формула «выводилась» из соображений «по аналогии», но строго, по определению, было e^ix=cos(x)+i*sin(x).

      Скорее всего, у вас курс по-другому был построен.
      Мне интересно, как можно определить e^ix другим способом?
      Чтобы можно было при доказательстве ф-лы Эйлера оперировать уже определённым объектом «степень с мнимым показателем».
      • +1
        Мне интересно, как можно определить e^ix другим способом?

        Парочка способов приведена ниже. Все они сводятся к использованию того, что d(exp(z))/dz=exp(z).
  • +9
    e=-1 — как без рисунка написать формулу Эйлера. Если бы Times New, то «пи» выглядело бы пучше, как в книжках, но Хабр не позволяет.

    C формулами и картинками, всё же, понятнее, как здесь, en.wikipedia.org/wiki/Catalan_number.

    А без формул остаётся впечатление загадочности и невыводимости их. И там же — все эти примеры скобок, комбинаций треугольников. Потом, тут mathworld.wolfram.com/CatalanNumber.html неплохо рассказали. Но на русском, действительно, до сих пор не было хорошо иллюстрированной статьи по этим числам.
  • 0
    Доказательство есть через «соответствие 1» и метод отражений.

    Вообще этой последовательностью троллят на олимпиадах: смотришь первые ответы: 1,2,5,14,42,… И сразу пишешь вычисление чисел Каталана. А там только начало правильное :)
  • –1
    Правильные скобочные последовательности очень напоминают задание которое было для поступление толи я Летнюю Яндекс школу толи еще какое то мероприятие которое тут освещалось.

    Поломав минут40 голову над этой «самой просто задачей» я плюнул на нее и побумал, что это сложная задача. Ошибался. Это чрезвычайно сложная задача, если именно решать ее. Как ни покажется странно но мое имхо, что эта задача не столько на алгоритмику и тем более не на программирование, а именно на кругозор. Т.е. ты либо слышал про это либо нет.
    • 0
      Построить рекуррентную формулу для чисел Каталана можно легко просто поняв каким способом из 2*n скобочных структур строятся 2*(n+1) скобочные структуры без повторений.

      При должной сноровке можно даже решить рекуррентность (некоторые методы рассматриваются в «Конкретной математике» Грехем, Кнут, Поташник).

      Впрочем, я не думаю, что в летнюю школу вам бы потребовалось решать рекуррентность.
  • +1
    Спасибо за прекрасную статью. Читается очень легко. Единственное, очень уж броско вначале написали, что самым замечательным математическим фактом является тождество Эйлера. Факт, конечно, замечательный, но математика не настолько скудна, чтобы дать этому фату первое место по замечательности)
    • +1
      Спасибо за спасибо :)

      А под замечательностью тождества Эйлера я имел ввиду не то, что оно очень важно, а то, что оно весьма, на мой взгляд, удивительно и интуитивно непонятно. Из геометрии берем красивую константу, из матана предел некоего ряда, из комплексного анализа, вообще, какую-то мнимую «штуковину», соединяем все это и вдруг…
      Если посмотреть на нумерологию, то там гораздо более искусственные и за уши притянутые совпадения чисел объявляются мистическими.
      • +7
        А мне еще очень нравится тождество Рамануджана:

        • –2
          Мне больше нравится простое разложение в ряд числа pi или числа e. Такие разложения доказывают, что не существует вселенных, в которых e или pi имеют другие значения, что бы не думали об этом фантасты, иначе в этих вселенных 1 + 1 не равнялось бы паре. Сразу становится любопытным вопрос о физических константах. Если окажется, что они тоже выражаются через какие-то хитрые ряды, возникающие на квантовом уровне из единого уравнения всего, то это похоронит все параллельные пространства с отличающимися свойствами пространства, а заодно и существование бога.
          • 0
            мне кажется, что для хорошего фантаста несложно придумать вселенную, где 1+1 не равно двум, а А не тождественно А

            Помню у Дагласа Адамса в Restaurant at the end of the Universe была концепция числа, которое может быть равно чему угодно, кроме самого себя.
          • +1
            Большинство физических констант имеет размерность (то есть выражено в метрах, секундах и других антропометрических единицах). Их числовые выражения в дюймах или саженях будут другими, посему никакого сакрального смысла в этих числовых значениях быть не может.
            • +3
              Есть очень хорошая безразмерная константа — постоянная тонкой структуры: . Вот это число описывает наш мир таким, какой он есть. Число не зависит от того, какие единицы измерения мы будем использовать.
            • 0
              Все же ворпрос остается, безотносительно единиц измерения: либо это некоторые «произвольные» параметры нашего пространства, либо это результат какого-то вычисления, столь же неизбежный, как результат вычисления числа e.

              Например, скорость света в вакууме всегда одна и та же, не важно в каких попугаях вы ее измеряете.

              И одно дело, если есть параллельная вселенная, в которой скорость света в вакууме в два раза меньше, чем у нас. Другое дело, если эта скорость света получается как решение какого-то уравнения — тогда во всех параллельных мирах эта величина будет одинаковой. Решения уравнений не зависят ни от чего.

              В общем-то, вопрос сводится к тому, до какой степени физика описывается математикой.
              • 0
                Например, скорость света в вакууме всегда одна и та же, не важно в каких попугаях вы ее измеряете

                Скорость света, конечно, не зависит ни от чего, но выражается разными числами в разных системах измерений, в отличие от постоянной тонкой структуры. Живи хоть в метрах, хоть в сантиметрах, всегда получится 1/137.
        • 0
          Вначале мне показалось что закономерность в знаменателе это (2n+1)!!!, но потом последний знаменатель спутал все.
          Объясните закономерность, пожалуйста.
          • 0
            Тождество очень тяжело доказывается. Я не знаю как.
          • 0
            Тут левая часть тождества состоит из двух выражений, которые изменяются одновременно. Т.е. одно выражение — пять дробей, второе — пять уровней у дроби. Если мы еще чуть чуть распишем выражение, то вместо первого многоточия у нас будет 1 / (1 * 3 * 5 * 7 * 9 * 11), а вместо правого — 6 / (1 + ...).
    • +1
      В этом выражении вообще нет никакого замечательного факта. Выражением e^ix математики тупо договорились обозначать поворот комплексной плоскости. Да, экспонента — сама по себе прикольная штука, про нее даже анекдоты есть. Да, pi — это отношение длины окружности к диаметру, действительно любопытная штука, если задуматься. Но почему эти два числа, просто взятые вместе становятся чем-то особо замечательным — не понятно.
      • 0
        Выражением e^ix математики тупо договорились обозначать поворот комплексной плоскости.

        Никто не договаривался. Это теорема, а не договоренность.
        • +1
          Договоренность имеет место быть в самом определении возведения числа в комплексную степень. После этого определения доказывать попросту нечего.

          Хотя если определить комплексную степень через что-то непонятное, а потом доказать тождественность этого определения повороту комплексной плоскости, тогда да — теорема. Вопрос в системе аксиом.
          Но это ничуть не добавляет замечательности утверждению, которое имеет простой геометрический смысл на комплексной плоскости.
          • –1
            По-моему, вы все-таки не правы.
            Обычно показательная функция для комлексных чисел определяется точно также, как и для действительных — сначала определяется возведение в натуральную степень, как произведение соответствующего числа сомножителей, а потом выполняется предельный переход. Никакой специальной договоренности, считать поворот возведением в степень не было. За подробностями стоит обратиться к первой главе классического учебника «Введение в комплексный анализ» Шабата.
            • +4
              Это работает, если мы возводим комплексное число в натуральную, целую или рациональную степень. А здесь задача другая — определить, что такое комплексный показатель степени. Насколько я понимаю, есть два подхода.
              1) говорим, что утверждение lim_{x->0}((e^x-1)/x)=1 действует не только для действительных, но и для комплексных x. И что формула e^(a+b)=e^a*e^b тоже продолжает работать. Отсюда доказываем, что умножение на e^(i*x) — в самом деле поворот на угол x, и далее по тексту.
              2) Определяем e^x как решение дифференциального уравнения f'(x)=f(x), f(0)=1. Оно чуть более сильное, чем в первом варианте, и работать с ним удобнее — можно сразу показать, что результатом поворота точки z на угол x окажется z*e^(i*x). Зато формулу e^(a+b)=e^a*e^b придётся доказывать.
              Можно еще определить ln(z) как интеграл по пути от 1 до z от функции 1/x, а e^x — как обратную к ней. Тоже всё получается довольно просто, но придётся доказать, что ln(a*b)=ln(a)+ln(b). Не забывая бороться с неоднозначностью этого логарифма :)
            • 0
              То, что вы пишете про предельный переход — это как раз то, про что я писал во втором абзаце своего предыдущего поста.

              Я не верю в мистическую комплексную связь чисел e и pi.
              e^ix = cos(x) + i sin(x). Видите, числа e здесь нет, это просто обозначение.
              • 0
                То, что «числа e в формуле нет», это правда. Действительно, exp(z) — единственная функция со свойствами показательной функции и комплексным аргументом, которую принято использовать. На вопрос, чему равно i^i, математик нахмурится, и скажет, «наверное, это exp(i*Ln(i))=exp(-pi/2+2*pi*k), где k пробегает все целые числа. Но вопрос плохой». И «числом e» называется значение exp(1). Которое равно какому-то замечательному пределу, сумме какого-то ряда и пр.
                А вот насчет формулы Эйлера… Как сейчас определяется cos(x)? Это либо решение диффура f(x)+f''(x)=0, f(0)=1, f'(0)=0, либо (exp(i*x)+exp(-i*x))/2. Но уж никак не отношение катета к гипотенузе :)
                • 0
                  Кстати, комплексная экспонента exp(a + ib) раскладывается на exp(a) * exp(ib). И я бы сказал, что эти две части ортогональны: в полярной системе координат первая отвечает за изменение радиальной части, а вторая за изменение угла. e = exp(1) относится к радиальной части, а pi — к угловой. Таким образом, эти два числа как бы ортогональны. =)
            • +1
              Возведите, пожалуйста, 2 в степень i вашим способом.
              • 0
                Для любого натурального x выражение (1 + x*(ln 2)/n)^n стремится к 2^x. Вполне естественно, расширить это определение на любые x (действительные и компексные). Ну а выражении (1 + x*(ln 2)/n)^n есть только обычные деления, умножения и возведение в натуральную степень (ln 2 — константа никак с комплексным анализом не связанная). Соответственно любое число в степени i будет пределом выражения (1 + i*c/n)^n.
                • –1
                  Теперь возведите этим способом i в степень i.
                • 0
                  Для любого натурального x выражение (1 + x*(ln 2)/n)^n стремится к 2^x.

                  Любопытно. Для этого вам придётся доказать, что (1+ln(2)/n)^n стремится к 2. И как вы это сделаете, не доказывая общего факта, что (1+x/n)^n стремится к exp(x)?

  • 0
    e^(i*pi)=-1 — теперь буду вставлять в статью для привлечения внимания.
  • +4
    Как раз сегодня столкнулся с презентацией под названием «Pi is wrong» (http://www.youtube.com/watch?v=H69YH5TnNXI), в которой как раз формула Эйлера упоминалась и делалось замечание о том, что она не красива и не логична в таком виде. Куда как более клёво и интуитивно понятно выглядит формула e^(i*τ) = 1 :)
    И да, с использованием τ становится понятен смысл этой формулы :).
    • +2
      т=2*pi баян.

      Вот эта константа реально доставляет!
      www.youtube.com/watch?v=GFLkou8NvJo
      • 0
        Очень классный стёб :)). Действительно доставляет, спасибо :).
    • 0
      6.28...3.14...1.57… e^(i*tau)= 1, e^(i*pi)=-1, e^(i*tav)=i
      • 0
        1.57 ≈ 11÷7, half pi, quarter tau
        τ=2π=4tav
        • 0
           tav? egyptian hieroglyph x001 (U+133CF)
  • –4
    Ещё более интересен следующий «парадокс»

    image
    • +5
      Ничего особо интересного, честно говоря. Логарифм — многозначная «функция», что такого. Здесь происходит примерно то же, что и в более простом «парадоксе»:

      -1 = -1
      1/(-1) = (-1)/1
      sqrt(1/(-1)) = sqrt((-1)/1)
      sqrt(1)/sqrt(-1) = sqrt(-1)/sqrt(1)
      1/i = i/1
      1*1 = i*i
      1 = -1
      
      • 0
        Я бы упростил:

        1*1 = (-1)*(-1)
        1 = -1

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