怎么生物课也遇到计数题啊…
- 今天生物课老师直接说: $n$ 个碱基对的 $DNA$ 种类数目就是 $4^n$ ,如果还要考虑对称的话太麻烦了…
- 于是就想了一下考虑对称同构怎么算.讨论前后翻转,两条链交换,中心对称都算一种的话的情况.
- 考虑 $Burnside$ 引理,显然可以构造出置换群 ${ \text{不变,左右翻转,上下翻转,中心对称}}$ ,中心对称其实就是左右翻转与上下翻转都操作了一次.
- 那么现在只需要计算出每种变换的不动点数目,求其平均数即可.
- 不变 的不动点数目显然是 $4^n$ .
- 左右翻转 的不动点数目显然是 $0$ .因为碱基互补,不可能两条链相同.
- 上下翻转 的不动点数目其实就是回文串的数目. $n$ 为偶数时为 $2^n$ , $n$ 为奇数时为 $2^{n+1}$ .
- 中心对称 的不动点数目,其实就是第 $i$ 个位置恰好与第 $n+i-1$ 个位置互补的数目. $n$ 为偶数时为 $2^n$ . $n$ 为奇数时,中间那个位置要求与自己互补,这是不可能的,数目为 $0$ .
- 对 $4$ 种变换的不动点数目求平均值,得到答案 $4^{n-1}+2^{n-1}$ .
其实 $DNA$ 分子好像只有中心对称这一种变换?因为左右翻转和上下翻转后其实裸露的那两个磷酸分子旁边的东西的是不一样的???但总之无论考虑哪些变换都可以用 $Burnside$ 像上面那样直接搞吧…