комбинаторика

[navubo]

Дано 2n чисел вида (3 в степени k) (все k различны). Сколькими способами можно записать их в 2 строчки и n столбцов так, чтобы в каждой строчке и в каждом столбце все предыдущие числа делились на последующие.

Помогите пожалуйста с алгоритмом решения.

[AKM]

Я в комбинаторике не особо, но мне видится следующая схемаHack attempt!причём пересталять можно только те, которые нарисованы одним цветом. В таблице, естественно, не числа, а их номера по возрастанию.

А "3 в степени k" на форуме принято писать как $ 3^k $, что имеет вид $ 3^k $.

[Maslov]

AKM в сообщении #253021 писал(а):

Я в комбинаторике не особо, но мне видится следующая схемаHack attempt!причём пересталять можно только те, которые нарисованы одним цветом. В таблице, естественно, не числа, а их номера по возрастанию.

AKM, а как в Вашей схеме получить
$6 5 4$
$3 2 1$
?

[AKM]

Видимо, недодумал-недосмотрел.

[jetyb]

Расположим эти $2n$ чисел в порядке убывания. Если число находится в верхнем ряду, заменим его на "(" , если в нижнем - на ")" . Получившаяся последовательность скобок будет правильной(т.е. в любом префиксе последовательности открывающих скобок не меньше, чем закрывающих). Между записями чисел и правильными расстановками скобок можно установить биекцию.
Осталось посмотреть одно из определений чисел Каталана.

[Maslov]

jetyb в сообщении #253036 писал(а):

Между записями чисел и правильными расстановками скобок можно установить биекцию.
Осталось посмотреть одно из определений чисел Каталана.

Если не трудно, поясните, пожалуйста, для бестолковых, как это будет работать при $n=3$

[jetyb]

((())) : $^{654}_{321}$
(())() : $^{652}_{431}$
(()()) : $^{653}_{421}$
()(()) : $^{643}_{521}$
()()() : $^{642}_{531}$

[Maslov]

jetyb в сообщении #253042 писал(а):

((())) : $^{654}_{321}$
...
()()() : $^{642}_{531}$

Спасибо! Никогда б не додумался