计数问题

第一类斯特林数

? 有\(n\)个不同的球，把它们方到\(m\)个盒子里，每个盒子里的球连成一个环，问有多少种不同的方案。

? \(f[n][m] = f[n - 1][m - 1] + f[n - 1][m] * (n - 1)\) ： 第\(n\)个球单独成一个环 + 第\(n\)个球与别的球挤一个盒子，这个球可以插到\(n - 1\)个空里。

第二类斯特林数

? 有\(m\)个相同的盒子和\(n\)个不同的球，问有多少种不同的方案。

? \(f[m][n] = f[m - 1][n - 1] + f[m][n - 1] * m\) ： 第\(n\)个球单独放一个盒子 + 第\(n\)个球与别的球挤一个盒子，这个球可以放到\(m\)个盒子里。

? 如果这\(m\)个盒子不相同，那么再乘一个\(m!\)就好了。

组合数

? \(C_{n}^{m}\)表示从\(n\)个数里面取\(m\)个数有多少种方案。 直接上式子：

环形染色

? 有\(n\)个球连成的一个环，有\(m\)种颜色，相邻的两个球不能同色，问有多少种不同的方案。

? 留坑。。。。

不相邻染色

? 给你一个长度为\(n\)的格子，里面可以放黑球或白球，两个黑球不能相邻，问有多少种情况。

? 我们用二维数组\(f[i][1]\)表示第\(i\)个格子放白球的情况有多少种，\(f[i][0]\)表示第\(i\)个格子放黑球的情况有多少种。

? \(f[n][1] = f[n - 1][1] +f[n - 1][0]\) ： 如果第\(n\)个格子放白球，那么第\(n - 1\)个格子放黑球或者白球都可以；

? \(f[n][0] = f[n - 1][1]\) ： 如果第\(n\)个格子放黑球，那么第\(n - 1\)个格子必须放白球。

计数问题

原文：https://www.cnblogs.com/czhui666/p/13369370.html