Определим выражение следующим образом: $$x := выражение$$ $$Пусть\ E - выражение, тогда\ (E) - выражение$$ $$Пусть\ E_1 \ и \ E_2 - выражения, тогда\ E_1 + E_2 \ а \ также \ E_1 - E_2 - выражение$$ Требуется вычислить количество таких выражений длины N
Известно, что количество таких выражений длины 3 ровно 3 $$x+x,\ x-x,\ (x)$$
Длины 5 - 11. Несложно их перечислить
Я пытался вывести рекурренту. Например, перебрать позицию для знака $$i \in [1; n - 2]: \alpha(n) = 2 \cdot (f(i) + f(n - i - 1)), \ \alpha(0) = 0, \ \alpha(1) = 1$$ Но таким образом мы учтем некоторые одинаковые выражения несколько раз Взглянув на последовательность значений функции, а именно 1, 0, 3, 0, 11
Казалось, что $$\alpha(n) = 4 \cdot \alpha(n - 1) + \alpha (n - 2)$$ Но это не так, к сожалению. Я зашел в тупик. Пока что не понимаю, как вычислить эту функцию без полного перебора выражений посимвольно. Быть может, нужно заметить какое-либо свойство. Прошу гостей и пользователей сайта мне помочь.
Заранее спасибо!

задан 10 Янв 22:11

@Kornuel: я уже было начал писать ответ, но обнаружил одну вещь, которую надо прояснить. Обычно в таких задачах выражение однозначно "расшифровывается". Здесь же можно взять x+x и x, и тогда x+x+x будет считаться выражением. Если взять x и x+x, то получим в итоге то же самое. Правильно ли это? Считаются ли такие выражения одинаковыми?

Я бы скорее ожидал, что x -- выражение, и для любых выражений E1, E2 выражениями считаются (E1+E2) и (E1-E2), взятые в скобки. Такой язык был бы вполне "традиционен", а здесь скобки играют какую-то постороннюю и странную роль.

(10 Янв 23:29) falcao

Эти выражения различны.
x+x - выражение => x+x+x также выражение, причем они различны
Я думаю, что скобки сделаны в этой задаче для усложнения, потому что в выражении должна соблюдаться "правильность" постановки скобок.

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

((x))
x+x+x
x+x-x
x-(x)
x-x+x
x-x-x
(x)+x
(x)-x
(x+x)
(x-x)
x+(x)

(10 Янв 23:42) Kornuel

@Kornuel: в такой постановке задачу, конечно, можно решать, но она выглядит крайне противоестественной. Скажем, если взять первое выражение x+x, и второе тоже x+x, то разрешается образовать выражение x+x-x+x, которое "как бы" должно быть разностью двух одинаковых, но на деле это не так. Я бы тогда заменил + и - на y и z, чтобы не возникало нелепостей. Тогда получится xyxzxyx, что не "режет глаз". И даже скобки можно тогда заменить на что-то вроде axb. Тогда получается некоторая формальная грамматика, рост которой, вероятно, можно посчитать.

(11 Янв 1:31) falcao

К сожалению, мои попытки сделать это не увенчались успехом.

(11 Янв 23:27) Kornuel

@Kornuel: а откуда такая странноватая задача? Ведь это не арифметические выражения, а что-то очень искусственное.

(11 Янв 23:43) falcao

Задача с математических сборов. Довольно интересно узнать, как же в итоге она решается

(21 Янв 11:22) Kornuel

@Kornuel: видимо, разумный смысл тут всё-таки есть. Должно решаться через производящие функции. Завтра посмотрю.

Идея в том, что любое выражение есть либо x, либо (E), либо "сумморазность" нескольких выражений, которые сами не представимы в виде сумм или разностей.

(22 Янв 2:37) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
0

Все выражения имеют нечётную длину. Обозначим через $%a_n$% число выражений длины $%2n+1$% для $%n\ge0$%. Найдём производящую функцию $%A(t)=\sum\limits_{n\ge0}a_nt^n$%.

Назовём выражение неприводимым, если оно не имеет вид ни суммы, ни разности. Пусть $%b_n$% -- число неприводимых выражений длины $%2n+1$%, и $%B(t)$% -- производящая функция для них. Всякое неприводимое выражение имеет вид либо $%x$%, либо $%(E)$%, где $%E$% -- выражение. Отсюда $%b_0=1$% и $%b_n=a_{n-1}$% при $%n\ge1$%, то есть $%B(t)=1+tA(t)$%.

Любое другое выражение однозначно представимо в виде $%E_0\pm E_1\pm\cdots\pm E_k$%, где $%k\ge1$%, и $%E_0$%, ... , $%E_k$% неприводимы. Если длина $%E_i$% равна $%2n_i+1$% при $%1\le i\le k$%, а длина всего выражения равна $%2n+1$%, то $%2n+1=(2n_0+1)+\cdots+(2n_k+1)+k$%, откуда $%n_0+\cdots+n_k=n-k$%. Число способов составить такое выражение при данном $%k$% равно $%2^kb_{n_0}\cdots b_{n_k}$%, откуда при $%n\ge1$% имеет место рекуррентное соотношение $$a_n=a_{n-1}+\sum\limits_{k\ge1}2^k\cdot\sum\limits_{n_0+\cdots+n_k=n-k}b_{n_0}\cdots b_{n_k}.$$ Домножая на $%t^n$%, имеем $$a_nt^n=t\cdot a_{n-1}t^{n-1}+\sum\limits_{k\ge1}(2t)^k\cdot\sum\limits_{n_0+\cdots+n_k=n-k}b_{n_0}t^{n_0}\cdots b_{n_k}t^{n_k}.$$ Суммируя по $%n\ge1$%, получаем $$A(t)-1=tA(t)+\sum\limits_{k\ge1}(2t)^kB(t)^{k+1}=tA(t)+\frac{2tB(t)^2}{1-2tB(t)},$$ то есть $$A(t)-1=tA(t)+\frac{2t(1+tA(t))^2}{1-2t-2t^2A(t)}.$$

Решая уравнение относительно $%A(t)$%, имеем квадратное уравнение $%2t^2A(t)^2+(3t-1)A(t)+1=0$%, из которого $$A(t)=\frac{1-3t-\sqrt{1-6t+t^2}}{4t^2}=\frac2{1-3t+\sqrt{1-6t+t^2}}.$$ Это даёт производящий ряд $%A(t)=1+3t+11t^2+45t^3+197t^4+903t^5+\cdots$%. Из общих соображений следует, что коэффициенты растут примерно как $%(3+2\sqrt2)^n$%.

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

ссылка

отвечен 23 Янв 2:33

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1,470
×63
×33
×17

задан
10 Янв 22:11

показан
189 раз

обновлен
23 Янв 2:33

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru