Problem 781

Feynman Diagrams

Let $F (n)$ be the number of connected graphs with blue edges (directed) and red edges (undirected) containing:

two vertices of degree $1$ , one with a single outgoing blue edge and the other with a single incoming blue edge.
$n$ vertices of degree $3$ , each of which has an incoming blue edge, a different outgoing blue edge and a red edge.

For example, $F (4) = 5$ because there are $5$ graphs with these properties:

You are also given $F (8) = 319$ .

Find $F (50 000)$ . Give your answer modulo $1 000 000 007$ .

NOTE: Feynman diagrams are a way of visualising the forces between elementary particles. Vertices represent interactions. The blue edges in our diagrams represent matter particles (e.g. electrons or positrons) with the arrow representing the flow of charge. The red edges (normally wavy lines) represent the force particles (e.g. photons). Feynman diagrams are used to predict the strength of particle interactions.

费曼图

考虑由蓝色边（有向）和红色边（无向）组成的连通图，记 $F (n)$ 为其中满足如下条件的图的数目：

有两个度为 $1$ 的顶点，其中一个只有一条蓝色出边，另一个只有一条蓝色入边。
有 $n$ 个度为 $3$ 的顶点，每一个均有一条蓝色入边，另一条蓝色出边，和一条红边。

例如， $F (4) = 5$ ，因为有 $5$ 种满足上述条件的图：

已知 $F (8) = 319$ 。

求 $F (50 000)$ ，并将你的答案对 $1 000 000 007$ 取余。

注：费曼图是一种形象化展示基本粒子之间相互作用的方法，其中：顶点代表相互作用；蓝色边代表实物粒子（例如电子和正电子），其方向表示电荷的移动方向；红色边（通常用曲线表示）代表力场粒子（例如光子）。费曼图通常用于预测粒子间相互作用的强度。