Задача 781
Диаграммы Фейнмана

Пусть $F(n)$ будет количеством связных графов с синими ребрами (направленными) и красными ребрами (ненаправленными), которые содержат:

  • две вершины степени 1 - одну с единственным исходящим синим ребром и другую с единственным входящим синим ребром.
  • $n$ вершин степени 3, каждая из которых имеет входящее синее ребро, отличное исходящее синее ребро и красное ребро.

Например, $F(4)=5$, так как существует 5 графов с такими свойствами:

Также известно, что $F(8)=319$.

Найдите $F(50\,000)$. В качестве ответа приведите остаток от деления полученного результата на $1\,000\,000\,007$.

ПРИМЕЧАНИЕ: Диаграммы Фейнмана - это способ визуализации сил, действующих между элементарными частицами. Вершины представляют взаимодействия. Синие грани на наших диаграммах представляют частицы материи (например, электроны или позитроны), а стрелка представляет движение заряда. Красные грани (обычно волнистые линии) представляют силовые частицы (например, фотоны). Диаграммы Фейнмана используются для предсказания силы взаимодействия частиц.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net