利用容斥原理计算含k个不动点的随机排列概率的相关问题咨询
利用容斥原理计算含k个不动点的随机排列概率的相关问题咨询
我最近在研究排列的不动点概率问题,具体背景是这样的:
给定集合$\Omega$是${1,2,...,N}$的所有排列构成的集合,我们采用均匀分布$\mathbb{P}$,也就是说任意一个排列$\sigma$被抽到的概率都是$\mathbb{P}(\sigma) = 1/N!$。这里的不动点指的是满足$\sigma(i)=i$的元素$i \in {1,2,...,N}$。
我现在想求随机抽到一个恰好包含$k$个不动点($0\leq k \leq N$)的排列的概率,而且要求用容斥原理来推导。首先我先说说自己的思路和疑问:
- 我一开始觉得,含$k$个不动点的排列数是组合数$C_N^k = \frac{N!}{k!(N-k)!}$,所以对应的概率就是$\frac{C_N^k}{N!} = \frac{1}{k!(N-k)!}$,但我不确定这个结论是不是正确的?
- 我知道应该用容斥原理的公式:$\mathbb{P}(\cup_{i=1}^n S_i) = \sum_{k=1}^n (-1)^{k-1} \sum_{1\leq i_1 < \dots <i_k\leq n} \mathbb{P} (S_{i_1} \cap \dots \cap S_{i_k})$,这里的$S_i$应该是所有满足$\sigma(i)=i$的排列构成的集合吧?
- 我自己尝试过一个方向:打算把含$k$个不动点的排列集合拆分成若干不一定不交的子集,比如考虑所有包含1作为不动点的排列,直到包含N作为不动点的排列,但不知道接下来该怎么推进。
想请教大家,我的初始结论是不是正确的?如果不对的话,应该怎么用容斥原理来正确推导这个概率呢?有没有具体的解法或者思路建议?谢谢大家!
备注:内容来源于stack exchange,提问作者user996159
相关产品推荐
相关产品推荐

