考虑枚举第一个点连除去的边的数量ii

剩下的边有2C(2,n1)2^C(2,n-1)种情况

那么第一个点的贡献就是

ans=2Cn12×Cn1i×ik\Large ans = 2^{C_{n-1}^{2}} \times C_{n-1}^{i} \times i^k

由于每个点都是等价的

ans=n×2Cn12×Cn1i×ik\Large ans = n\times2^{C_{n-1}^{2}} \times C_{n-1}^{i} \times i^k

然后用第二类斯特林数的性质

dk=p=0d×S(k,p)×p!\Large d^k = \sum _{p=0}^{d} \times S(k,p) \times p!

将k个不同的小球任意放进d个不同的盒子里,方案数为d^k。考虑到最后可能只有一部分盒子有小球,我们不妨一开始就指定某p个盒子一定要放小球,其余盒子一定不能放,然后将k个小球划分为p个非空集合的方案数便为S(k,p)。由于在第二类stirling数中,集合被认为是一样的,所以最后还要乘上一个(p!)。