Найти количество способов расставить числа в графе...

[likusta]

Условие: вставить от 1 до 10 так, чтобы стрелочка указывала на число, которое больше, чем в том кругу от которого она исходит.
Вопрос: Сколько таких вариантов?

В первом кругу должна быть единица. Мы работаем с 9 числами. Понятно что двойка будет стоять на втором уровне.Десятка на верхнем уровне. Дальше у меня возникаю сложности т.к. каждому кругу соответствует определенный интервал допустимых чисел к тому же их надо расположить по возрастанию. С чего мне начать?

-- Вс фев 14, 2010 17:06:43 --

Извиняюсь, тему хотел в другой раздел поместить. Уважаемые модераторы, пожалуйста перенесите тему.

Тема перенесена

[jetyb]

Опишу алгоритм решения таких задач: пусть из самого нижнего кружка выходит $k$ ветвей с $m_k$ кружков на каждой. Из множества чисел удаляется минимальное, а остальные числа произвольным образом разбиваются на $k$ групп с $m_i$ элементов в $i$-ой. Затем для каждой группы решается та же задача.
Посчитайте, сколько трактовок имеет этот алгоритм применительно к данной задаче.

[maxal]

См. Топологическая сортировка

[likusta]

Спасибо за ответы.

maxal в сообщении #289121 писал(а):

См. Топологическая сортировка

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

[TOTAL]

likusta в сообщении #289143 писал(а):

Нельзя ли разбить все на три части(ветви) и найти все возможные варианты учитывая, что некоторые из чисел были уже использованы и в конце перемножить три числа.

Перемножайте $\left( 2C_9^3\right) \times \left( 2C_5^3\right)$

[Профессор Снэйп]

Задача про то, что каждый частичный порядок можно расширить до линейного.

[PAV]

Чтобы заполнить левую часть графа, нужно произвольным образом выбрать из множества $\{2,3,\ldots,10\}$ три числа. Их можно расположить двумя способами. Из оставшихся минимальное становится нижним в правой части, а далее строятся аналогичные разбиения на части. В принципе, несложная комбинаторика, вполне понятная школьникам.

-- Пн фев 15, 2010 12:08:55 --

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