n个点的基环树数量
某裴姓蒟蒻上午提了一个小问题(rt)。。然后他升华了。。升华之前感受到了神犇的力量。。。
方法一:
g[n][k]表示n个点,k条边的无向图(不一定连通)
f[n][k]表示表示n个点,k条边的无向连通图
咕咕了。。。自己讲不清。。。O(n^4)
方法二:
我们可以枚举环的大小,设为$i$,则可以从$ n$个中随意选$i$个点即$C_n^i$,造出本质不同的环的数量为$(i-1)!$,但是会有翻转同构,所以要$/2$;
当n个点有k个连通块,把他们连成一棵树的方案数是:$ \Pi sz_i \space* n^{k-2}$
证明:把连通块看成点,$sz_i$表示第$i$个连通块的点数
枚举$Prufer$序列,设$p_i$为$Prufer$序列中的第$i$项,$q_i$代表$i$在$Prufer$序列中的出现次数,
则有 $ \Sigma_{Prufer}\space \Pi sz_i^{q_i+1} \space q_i+1$相当于是$i$的度数,而每个点都有可能是连边的点,所以是$sz_i^{q_i+1}$
$\Pi sz_i \space \Sigma_{Prufer}\space \Pi sz_i^{q_i}$
$\Pi sz_i \space \Sigma_{Prufer} \space \Pi sz_{p_i}$
根据$Prufer$序列的性质,我们知道$Prufer$序列长$ k-2$并且每个位置都可以填$[1,k]$
所以根据乘法原理(或是说乘法分配律)可知:
$\Sigma_{Prufer} \space \Pi sz_{p_i}=\Pi_{p=1}^{k-2}\Sigma_{i=1}^k sz_i$
所以有$\Pi sz_i \space \Pi_{p=1}^{k-2}\Sigma_{i=1}^k sz_i$,而$\Sigma_{i=1}^k sz_i=n$
即$\Pi sz_i \space n^{k-2}$
证毕
此时每个点的$sz$都是$1$,除了那个环的$sz$是$i$,共有$n-i+1$个点(连通块)
所以公式为$C_n^i*(i-1)!*i*n^{n-i+1-2}=C_n^i*i!*n^{n-i-1}$
咕了一天qwq2019.05.20
最新文章
- CSharpGL(33)使用uniform块来优化对uniform变量的读写
- java的会话管理:Cookie和Session
- 动画黄金搭档:CADisplayLink&;CAShapeLayer
- std result_of
- python基础——使用dict和set
- BZOJ3775 : 点和直线
- linux的文件属性介绍、目录及路径表示方法
- if 和 swith的选择.
- windows10 预览版 中英文官方下载地址+激活密钥+网盘分享
- HashMap的扩容机制, ConcurrentHashMap和Hashtable主要区别
- 【jquery、XML】jquery通过按钮使打开select
- vivo Xplay 5的Usb调试模式在哪里,打开vivo Xplay 5Usb调试模式的经验
- MFC设置单文档保存格式以及标题
- Buffering of C streams
- html中通过js获取接口JSON格式数据解析以及跨域问题
- Anroid 搭建Maven私服(Android Studio)
- linux zip压缩和解压的各种操控
- 在 Go 语言中使用 Log 包--转自GCTT
- android 写入联系人
- Bzoj1498&;1416: [NOI2006]神奇的口袋
热门文章
- Arc065_E Manhattan Compass
- Java面试题10(如何取到set集合的第一个元素)
- 求解范围中 gcd(a,b)== prime 的有序对数
- 【队列】最大值减去最小值小于等于num的子数组数量
- Maven: 自动远程部署
- #include <;deque>;
- import module, from module import funtion区别
- 百度之星 hdu5701 中位数计数
- Servlet的生命周期以及简单工作原理的讲解
- springMVC绑定json参数之二(2.2.2)