комбинаторика: число способов расставить скобки в произведен

[Ирина18]

Помогите решить задачу по комбинаторике:
Дано:
$X_1*X_2*X_3*\cdots *X_n$
Сколькими способами можно расставить скобки, чтобы получить произведение?

Например:
при $n=3$:
$(X_1*X_2)*X_3$
$X_1*(X_2*X_3)$

при $n=4$:
$(X_1*X_2)*(X_3*X_4)$
$(X_1*(X_2*X_3))*X_4$
$X_1*((X_2*X_3)*X_4)$

[cepesh]

Что-то мне напоминает числа Каталана... Могу ошибаться

[Гость]

Если требовать скобки вокруг каждого умножения (т.е. $(x1*x2*x3)$ недопустимо), и притом одни, то вроде нет, не ошибаетесь. См. http://mathworld.wolfram.com/BinaryBracketing.html

[Capella]

Эта задача достаточно не тривиальна (по крайней мере на первый взгляд). При n = 4 описаны не все скобки.. Например не хватает (X1(X2(X3X4)))- Далее, можно ли считать за скобку (((X1X2)X3)X4)? И ещё один вопрос: со скобками должны быть обязательно все члены? Например, если ряд из 10 членов, возможен ли, к примеру, такой вариант: X1X2X3(X4X5)X6X7(X8X9)X10?
В любом случае, если ряд может быть только монотонно возрастающим из всех натуральных чисел, будет сверх сложно определить все скобки при n стремиться к бесконечности..... Даже в самом лёгком варианте надо будет делать сначала обсчёт по всем скобкам только с двумя членами, далее вводить скобку с тремя итак по нарастающей. По моему посчитать от руки невозможно

[Гость]

ψυ& писал(а):

По моему посчитать от руки невозможно

См. http://mathworld.wolfram.com/Bracketing.html.

[Ирина18]

Внешние скобки не важны.
Нужно считать не вручную, а найти формулу (функцию)от n.

[Ирина18]

Как можно решить данную задачу без использования чисел Каталана?
Кто умеет выводить рекуррентные соотношения?
Нужно найти функцию от n

[cepesh]

Ирина18 писал(а):

Как можно решить данную задачу без использования чисел Каталана?
Кто умеет выводить рекуррентные соотношения?
Нужно найти функцию от n

Об этом и многом другом можно узнать в гугле.

[dm]

Ирина18 писал(а):

Как можно решить данную задачу без использования чисел Каталана?
Кто умеет выводить рекуррентные соотношения?
Нужно найти функцию от n

Достаточно подробное рассмотрение задачи про расстановку скобок и числа Каталана есть в книге Грэхем Р., Кнут Д., Паташник О. Конкретная математика, раздел 7.5, пример 4 (с. 391).

[Ирина18]

Реккурентным соотношением чисел Каталана является
С0 = 1,
Сn = С0Сn-1 + С1Сn-2 + С2Сn-3 + ... + Сn-1С0 при n > 0.

Можете объснить, почему? Только понятным языком. Изучила море книг, сайтов и везде написано одно и то же: ВОТ, типа реккурнтное сооношение чисел Каталана. Но из чего это следует?

[dm]

У Кнута этот момент достаточно подробно описан:
при $n>0$ ровно одно умножение "$\cdot$" лежит вне всех скобок - это последнее умножение, связывающее всё в целое. Если эта операция располагается между $x_k$ и $x_{k+1}$, то имеется ровно $C_k$ способов расстановки скобок в произведении $x_0\cdot\ldots\cdot x_k$ и $C_{n-k-1}$ способов в $x_{k+1}\cdot\ldots\cdot x_n$. Осталось просуммировать по $k$.
Вы читали Кнута? Что-то осталось непонятно?

[Ирина18]

Можно ли решить данное рекуррентное сообщение:
Cn = C1*Cn-1 + C2*Cn-2 + ... + Cn-1*C1
способом без использования производящих функций
(метод решения с использованием производящих функций я нашла, только он достаточно сложен с учетом того, что я не проходила производящие функции вообще)

Подскажите, пожалуйста.

[dm]

Просто для сверток естественно переходить к производящим функциям.

[незваный гость]

Ирина18 писал(а):

Можно ли решить данное рекуррентное сообщение:
Cn = C1*Cn-1 + C2*Cn-2 + ... + Cn-1*C1

Да решать-то зачем. Ответ Вам известен. Докажите по индукции, и забудьте.

[Ирина18]

Нужно решить, потому что необходимо выразить Cn через n (т.е. найти функцию от n)