题目分析
来自2013年王迪的论文《浅谈容斥原理》
设(f_{n,S})表示n个节点，入度为0的点集恰好为S的方案数。
设(g_{n,S})表示n个节点，入度为0的点集至少为S的方案数。
对于(g_{n,S})，有递推式
[g_{n,S}=2^{|S|(n-|S|)}g_{n-|S|,emptyset}
]
f与g有如下关系
[g_{n,S}=sum_{Ssubseteq T}f_{n,T}
]
子集反演一下
[f_{n,S}=sum_{Ssubseteq T}(-1)^{|T|-|S|}g_{n,T}
]
我们要求的答案即为
[egin{split}
g_{n,emptyset}&=sum_{|S|=1}^nf_{n,S}\
&=sum_{|S|=1}^nsum_{Ssubseteq T}(-1)^{|T|-|S|}g_{n,T}\
&=sum_{|S|=1}^nsum_{Ssubseteq T}(-1)^{|T|-|S|}2^{|T|(n-|T|)}g_{n-|T|,emptyset}\
&=sum_{i=1}^ninom{n}{i}sum_{j=i}^ninom{n-i}{j-i}(-1)^{j-i}2^{j(n-j)}g_{n-j,emptyset}\
&=sum_{j=1}^n2^{j(n-j)}g_{n-j,emptyset}sum_{i=1}^jinom{n}{i}inom{n-j}{j-i}(-1)^{j-i}\
&=sum_{j=1}^n(-1)^jinom{n}{j}2^{j(n-j)}g_{n-j,emptyset}sum_{i=1}^jinom{j}{i}(-1)^i\
&=sum_{j=1}^n(-1)^jinom{n}{j}2^{j(n-j)}g_{n-j,emptyset}(left[j=0
ight]-1)\
&=sum_{j=1}^n(-1)^{j+1}inom{n}{j}2^{j(n-j)}g_{n-j,emptyset}\
&=n!sum_{j=1}^n2^{j(n-j)}frac{(-1)^{j+1}}{j!}frac{g_{n-j,emptyset}}{(n-j)!}
end{split}
]
很像一个卷积的形式了，但是怎么搞(2^{j(n-j)})呢？
一个套路
[egin{split}
2^{k(n-k)}&=sqrt{2}^{2kn-2k^2}\
&=sqrt{2}^{-n^2+2kn-k^2-k^2+n^2}\
&=sqrt{2}^{n^2-k^2-(n-k)^2}\
&=frac{sqrt{2}^{n^2}}{sqrt{2}^{k^2}sqrt{2}^{(n-k)^2}}
end{split}
]
这样就构造出了卷积形式。
所以
[egin{split}
frac{g_{n,emptyset}}{n!sqrt{2}^{n^2}}&=sum_{j=1}^nfrac{(-1)^{j+1}}{j!sqrt{2}^{j^2}}frac{g_{n-j,emptyset}}{(n-j)!sqrt{2}^{(n-j)^2}}
end{split}
]
构造生成函数
[F(x)=sum_{i=1}frac{g_{i,emptyset}}{i!sqrt{2}^{i^2}}x^i\
G(x)=sum_{i=1}frac{(-1)^{i+1}}{i!sqrt{2}^{i^2}}
]
有
[egin{split}
F&=F*G+1\
&={1over1-G}
end{split}
]
多项式求逆即可。