与えられた条件を言い換えると、「 頂点の単純かつ連結なグラフであって、 から に至る一筆書きが存在するものの数」を求める問題となります。 このうち一筆書きに関する条件は、頂点 の次数(繋がっている辺の数)が奇数、その他の頂点の次数が偶数であることと同値です。
一旦、連結という条件を無視すると、 頂点の完全グラフの全域部分グラフであって、指定した 点の次数が奇数であるものを数えることになりますが、この問題(を含む問題)はARCに出題例があります。
https://atcoder.jp/contests/arc115/tasks/arc115_d
以下、この問題は解けるものとして解説を進めますので、必要であれば上記問題の解説を参照してください。 また、以下の解説において上記ARCの問題の解法には触れませんが、計算量等は察しがついてしまうおそれが ではありません。 完全な自力ACにこだわりたい方は念のため、以下を読まないことを推奨します。
上記問題を参照すると、 頂点の単純な無向グラフであって、奇数次の頂点が 個指定されているもの(ただし、連結とは限らない)の数が求まりますので、これを とします。 ここで 通りある「連結とは限らないがその他の条件を満たすグラフ」から、頂点 を含む連結成分の大きさが 以下であるものを取り除くことを考えます。 (奇数次の頂点はこの つのみであるため、これらが同じ連結成分に属することは保証されます。) 頂点の場合の問題の答えを として、 までにおいて、問題の答え が求まっていると仮定し、帰納的に求めましょう。 すなわち、「連結とは限らないがその他の条件を満たすグラフ」の数 から、「頂点 を含む連結成分の大きさが であるもの」の数を、 まで順に引いていきます。
ある について、除くべきグラフの数は、「 以外の 頂点の選び方の数 」「選んだ 頂点内で完結する、連結かつ他の条件も満たすグラフの数 」「残り 頂点において、全ての頂点の次数が偶数であるようなグラフの数 (こちらは、連結である必要はありません)」の積によって求まります。 ここで、全ての頂点が偶数次となるグラフの数は、再び上記ARCの問題(の部分問題)に帰着するため上記の形で表せます。 まとめると、次の式になります。
以上のように、小さい数から順に求めていくことで または、適切に前計算を行えば で答えを求めることができました。