关于容斥原理(PIE)在双胞胎座位排列问题中应用的疑问
关于容斥原理(PIE)在双胞胎座位排列问题中应用的疑问
我最近碰到AOPS《中级概率与计数》教材里的一个问题,属于容斥原理(PIE)章节的内容。我能跟上给出的解法步骤,但始终搞不懂为什么这个问题能用容斥原理来解决。
简单来说,解法的思路是:先计算恰好1到5对双胞胎坐在一起的情况数,接着用容斥原理算出至少有1对双胞胎坐在一起的排列总数,最后用无任何限制的总排列数减去这个数,得到没有一对双胞胎坐在一起的排列数。具体的计算式是这样的:总排列数 - (第1对坐一起的排列数 + 第2对坐一起的排列数 + ... + 第5对坐一起的排列数) + (第1&2对同时坐一起的排列数 + 第1&3对同时坐一起的排列数 + ... + 第4&5对同时坐一起的排列数) - ... + (-1)^(k+1)*k对同时坐一起的排列数总和 + ... + 5对都坐一起的排列数
不过我一直有个疑问:容斥原理到底为什么适用于这个场景?我印象里容斥原理是和维恩图、集合概念绑定的,n个集合的容斥公式本质是交替加减各阶初等对称和(这里的运算对象是集合的交集,而非数值相乘)。那这个双胞胎座位问题里,对应的各个集合到底是什么呢?
备注:内容来源于stack exchange,提问作者Angad Pal
相关产品推荐
相关产品推荐

