Короткий ответ: для n = 15 — самый простой, надёжный и быстрый путь — точный подсчёт динамическим программированием по подмножествам (битмаски). Для больших графов (n ≫ 25) точный подсчёт быстро становится невозможным, тогда применяют приближённые методы: последовательная случайная выборка с важением (sequential importance sampling, SIS), MCMC-методы для выборки равномерных линейных упорядочений и гибриды (точный подсчёт на малых компонентах + случайная выборка). Ниже — детали, оценки сложности и практические советы.

1) Точная схема: DP по подмножествам (битмаски)

Идея. Представим состояние S — множество уже поставленных вершин (битмаска длины n). Пусть dp[S] = число способов получить частичный порядок, где размещены ровно вершины S (т.е. количество линейных упорядочений для оставшихся вершин с учётом уже поставленных S). Начальное dp[0] = 1. Переходы: для состояния S допустимы только те вершины v ∉ S, у которых все предшественники (in-neighbors) уже в S. Для каждой такой v делаем dp[S ∪ {v}] += dp[S].

Псевдокод (сжатый):

Предвычислить pred_mask[v] (битовая маска предков v).dp[0] = 1.Для S от 0 до (1<<n)-1:
avail_mask = { v | ((S >> v) & 1) == 0 и (pred_mask[v] & ~S) == 0 }
для каждого v в avail_mask: dp[S | (1<<v)] += dp[S]Ответ = dp[(1<<n)-1].

Временная сложность: O(n · 2^n) (каждое состояние обрабатывается, из состояния проверяются до n вершин).

Память: O(2^n) числовых записей.

Комментарии:

Для n = 15: 2^15 = 32768 состояний, операций порядка 32768·15 ≈ 5·10^5 — мгновенно в любом языке.Храним числа в целых типах: максимум числа линейных упорядочений ≤ n!, для n=15 это ≈ 1.3·10^12 — укладывается в 64‑битный целый. Для больших n нужно big integers.Оптимизации: битовые операции для быстрого составления avail_mask; префильтрация компонентами (если DAG разбивается на независимые компоненты, ответ = произведение счетов * мультикомбинаторный множитель), использование симметрий/разбиений по «частям» порождает выигрыш.

2) Перебирать все топологические сортировки (backtracking)

Можно рекурсивно строить все упорядочения, выбирая на каждом шаге любую доступную вершину (Kahn-style). Это полезно если число упорядочений невелик.Сложность: O(#разрешённых упорядочений · n) времени и соответственно память/вывод proportional to count — не подходит в худшем случае (например, если DAG почти пустой, число ≈ n!).

3) Приближённые методы — последовательная выборка с важением (SIS)

Идея (простая версия — равновероятный выбор среди доступных):
Повторить T раз:S = ∅, weight w = 1.пока S ≠ V:
строим список доступных вершин A (те, у кого предки ⊆ S).k = |A|.выбираем v из A равновероятно (вероятность 1/k).w *= k (т.е. w = 1 / ∏ p_i — поправочный множитель; при равном выборе p_i = 1/k)S ← S ∪ {v}записать w_i = w.Оценка числа упорядочений L ≈ (1/T) ∑_{i=1..T} w_i. Это несмещённая оценка: E[w] = L.Почему это работает: вероятность сгенерировать конкретное линейное упорядочение σ равна ∏_{step} 1/k_step(σ), а вес возвращает обратную вероятность.Сложность одного пробега: O(n + число проверок доступности). Всего O(T·n).Минусы: дисперсия оценок может быть очень большой (веса могут быть крайне неравномерны), поэтому требуется большое T для малой относительной погрешности; если граф «сильный» частично упорядоченный, равномерный выбор может давать огромную вариативность.Как улучшить (уменьшить дисперсию):
Использовать неравномерную стратегию выбора q_v вместо 1/k, где q_v стремится приближённо пропорциональна числу расширений после выбора v. Идеал: q_v ∝ number_of_extensions(G with v выбран). Но эти значения неизвестны — можно оценивать приближённо: например, использовать эвристики (вес = exp(α·score_v)), score_v может быть степень вершины, оценка числа потомков, размер оставшейся компоненты и т. п.Гибрид: заранее запустить точный DP на всех подграфах до размера m (например m ≤ 20) и использовать эти точные подсчёты как «локальные» q_v для уменьшения дисперсии; то есть при шаге, если оставшихся вершин ≤ m — вычислить точный остаток; либо при выборе v искать dp для g = G \ {S ∪ {v}}.Использовать медиану/median-of-means или бутстрэп для устойчивой оценки доверительных интервалов, т.к. обычный средний и CLT может плохо работать при heavy-tail распределении весов.Работать в логпространстве для предотвращения переполнения: log w = Σ log k_step.

4) MCMC-методы (цепи Маркова) для равномерной выборки линейных упорядочений

Есть цепи, которые делают локальные перестановки (swap соседних несовместимых вершин — т.е. поменять местами две соседние в порядке вершины, если они не противоречат предшествованиям). Такие цепи теоретически имеют правильную равновесную меру (равномерную по всем линейным расширениям).Проблема — неизвестные и, как правило, большие времена перемешивания (mixing time). На практике MCMC может работать, но для строгой оценки погрешности и сходимости нужны дополнительные техники (оценка автокорреляции, диагностические тесты).Подходит если нужны примеры равномерных упорядочений, но не всегда подходит для точной оценки числа упорядочений.

5) Оценка применимости и масштабируемость

n = 15: DP по подмножествам — идеально, легко вычислить в миллисекунды/секунды. Рекомендую именно его.n ≈ 20–25: DP всё ещё возможен в оптимизированной реализации на C/C++/Rust: 2^25 ≈ 33·10^6 состояний, память и время — на грани, но реализуемо (память: ~33M записей; при 8 байтах ≈ 264 MB). В Python скорее медленно, но возможно с оптимизациями/bitset и массивами в C-расширениях.n > 25–30: DP становится мало применим (память/время экспоненциальны). Тогда:
если граф разлагается на независимые компоненты (K компонент), можно считать по компонентам и перемножать, учитывая перестановочные множители (мультиномиальный коэффициент) — это решает множество практических случаев;если граф обладает структурой (малый width / series-parallel / tree-like partial order), можно использовать специализированные алгоритмы/разбиения;иначе применять приближённые методы (SIS, MCMC, гибриды).Трудоёмкость приближённых методов:
SIS: O(T·n) время, где T — число пробегов. Необходимо подобрать T экспериментально, т.к. дисперсия может быть огромной. Часто применяют тысячи — миллионы пробегов.MCMC: сложность зависит от mixing time и желаемой эффективной выборки; нет универсальной гарантии.

6) Практические советы

Для вашего случая (n=15) — реализуйте DP по подмножествам, получаете точный ответ быстро.Реализация: храните dp как массив длиной 1<<n; используйте 64‑бит целые или bigints при необходимости; предвычисляйте pred_mask.Если хотите приближенно и быстрее (например для n>25), начните с SIS с равномерным выбором; оцените дисперсию весов. Если дисперсия большая — пробуйте гибрид (точный DP для оставшихся ≤ m вершин), или улучшайте распределение выбора по эвристикам.При оценке погрешности используйте:
стандартную ошибку mean ≈ sqrt(var(w)/T) и доверительные интервалы,медиану/median-of-means или бутстрэп при heavy-tailed распределении весов.

Короткая реализация формул для веса при равномерном выборе: если на каждом шаге было ki доступных вершин, то вес для этой выборки = ∏{i=1..n} k_i. Среднее таких произведений по многим независимым пробегам даёт несмещённую оценку числа линейных упорядочений.

Подытоживая:

Для n=15: DP по подмножествам — простой и надёжный способ (O(n·2^n) время, O(2^n) память), используйте его.Для больших n используйте приближённые методы (SIS, MCMC), разложение на компоненты и гибриды; будьте готовы к высокой дисперсии и отсутствию строгой гарантии точности без дополнительных усилий.

Если хотите, могу:

привести конкретный код (Python/C++) для DP и/или для SIS;помочь подобрать стратегию для конкретного DAG (можете прислать матрицу смежности/список рёбер).