Пользователь
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
карма
55,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
        О, да, у меня были «крестики-нолики» и посложнее: «математический цветник». Зачитаны до дыр :)
    • НЛО прилетело и опубликовало эту надпись здесь
      • 0
        А преподаватель это знает? Возможно, ему известен десяток-другой применений комплексных чисел. Но объяснить, как они связаны с реальностью? А как они связаны? И как связаны с реальностью конечные поля? Неархимедовы множества? И т.д.
        • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            Интересно, что на вопрос «для чего нужны конечные поля», сейчас можно услышать только один ответ — «криптография». Все остальные области применения, если они и были, давно забыты.
            • НЛО прилетело и опубликовало эту надпись здесь
              • 0
                Про конечные поля в электротехнике не слышал. С цифровыми фильтрами понять можно, хотя там все лавры пытается забрать БПФ. А «претензии на отсутствие значимости»… мне казалось, что их больше адресуют бесконечномерным пространствам и функциям на них, неизмеримым множествам, теории «очень больших» множеств и прочим играм с наборами аксиом.
                • НЛО прилетело и опубликовало эту надпись здесь
                  • 0
                    Если вы в конце говорите про теорию струн, то она еще не доказана
                    • НЛО прилетело и опубликовало эту надпись здесь
                • 0
                  В принципе, БПФ можно считать в поле по конечному модулю :)
                  • +1
                    Можно. Но поможет ли это в обработке сигналов?
          • 0
            Вы поставили мой основной вопрос обучения в ВУЗе. ЭТ не была моей основной спецухой, но меня до сих пор интересует какой физический смысл имеет Z-преобразование и комплексное преобразование при расчете цепей.
            • НЛО прилетело и опубликовало эту надпись здесь
              • 0
                Я вспомнил что такое быть студентом.
              • 0
                Огромное спасибо! Как жаль, что не вы были моим преподавателем по физике на 1-2 курсе! Я мог бы быть намного образованнее.
      • 0
        Нам в типичном вузе на типичном втором курсе на типичной дискретке про числа Каталана рассказывали. И про парные скобочки тоже. А ТФКП тоже бывает невероятно занимательно. Почитайте книжку «Простая одержимость», например :-)
        • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            Физический факультет, кафедра физико-технической информатики. Для меня странно звучит фраза «общеобразовательная программа для вуза». В вузе у всех специальность, о каком общем образовании речь? Ну можно говорить об общеобразовательной психологии или физкультуре на технических специальностях. Теория чисел наверняка есть на математических факультетах на соответствующих направлениях.

            Я понимаю, что числа Каталана не у всех были, а если у кого и было, многие успели забыть. Статья, безусловно, полезная, я даже плюсанул её :-)
            • НЛО прилетело и опубликовало эту надпись здесь
    • 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

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