Friend of Friend is Friend

解説

SNSをグラフと捉えたとき、各連結成分は必ず完全グラフとなります。

さて、 $n$ 頂点からなる完全グラフの個数は $1$ 個なので、指数型母関数 $f$ は $f(x) = \sum_{n \ge 1}\frac{x^n}{n!} = \exp(x) - 1$ です。

ここで、グラフの数え上げの事実として、 exp / log を用いた以下のものが存在します。

• 指数型母関数 $f, g$ を以下のように定義する。

  • $n![x^n]f(x)$ : $n$ 頂点の連結グラフであって、条件 $*$ を満たすものの個数。

  • $n![x^n]g(x)$ : $n$ 頂点のグラフであって、すべての連結成分が条件 $*$ を満たすものの個数。

• このとき、 $g(x) = \exp(f(x))$ が成り立つ。

よって、各連結成分が完全グラフとなっているグラフの個数を表す指数型母関数は $\exp(\exp(x) - 1)$ と表せます。

答えは $N![x^N]\exp(\exp(x) - 1)$ です。

別解

$N$ 番目のベル数 $B_N$ が答えです。