如何计算从嵌套有限集中抽取元素的组合数？

场景1：允许元素重复的多重集合数量 #

我们需要统计所有满足以下条件的无序多重集合：存在一种方式将 ( n ) 个元素（每个来自对应 ( S_x )）分配到集合中，即对于每个位置 ( x )，选中的元素属于 ( S_x )。

计算方法 #

1. 首先确定合法的元素计数序列：
   设 ( m_i ) 为前 ( i ) 个集合 ( S_1 \sim S_i ) 中的元素在多重集合中出现的总次数，需满足：
   • ( 1 \leq m_1 \leq m_2 \leq \dots \leq m_n = n )
   • 对每个 ( i \in 1..n )，( m_i \geq i )（因为前 ( i ) 个位置的元素都必须来自 ( S_i )，总次数至少为 ( i )）
2. 对每个合法的 ( m ) 序列，计算 ( \Delta_i = m_i - m_{i-1} )（( m_0 = 0 )），表示从 ( C_i ) 中选取的元素总次数；
3. 利用隔板法计算将 ( \Delta_i ) 个重复名额分配给 ( d_i ) 个元素的方式数：( \binom{\Delta_i + d_i - 1}{d_i - 1} )（当 ( \Delta_i = 0 ) 时，结果为1）；
4. 将所有合法序列对应的方式数相乘后求和，得到最终的多重集合数量。

示例验证 #

以题目中的例子：( S_1 = {1,2} )，( S_2 = {1,2,3,4} )（( n=2 )，( d_1=2 )，( d_2=2 )）：

• 合法的 ( m ) 序列有两种：
  1. ( m_1=1, m_2=2 )：( \Delta_1=1, \Delta_2=1 )，方式数为 ( \binom{1+2-1}{2-1} \times \binom{1+2-1}{2-1} = 2 \times 2 = 4 )，对应多重集合 ( {1,3}, {1,4}, {2,3}, {2,4} )；
  2. ( m_1=2, m_2=2 )：( \Delta_1=2, \Delta_2=0 )，方式数为 ( \binom{2+2-1}{2-1} \times \binom{0+2-1}{2-1} = 3 \times 1 = 3 )，对应多重集合 ( {1,1}, {1,2}, {2,2} )；
• 总和为 ( 4+3=7 )，与实际枚举的结果一致。

场景2：不允许元素重复的集合数量 #

我们需要统计所有大小为 ( n ) 的无重复集合，使得存在一种方式将每个元素分配到对应的 ( S_x ) 中（即每个元素属于其分配位置的 ( S_x )）。

计算方法 #

1. 确定合法的元素选取计数：
   设 ( a_i ) 为从 ( C_i ) 中选取的元素数量，需满足：
   • ( a_1 + a_2 + \dots + a_n = n )（总共选 ( n ) 个不同元素）
   • 对每个 ( i \in 1..n )，( a_1 + a_2 + \dots + a_i \geq i )（前 ( i ) 个集合的元素总数至少能覆盖前 ( i ) 个位置的需求）
2. 计算从 ( C_i ) 中选 ( a_i ) 个不同元素的方式数：( \binom{d_i}{a_i} )（当 ( a_i > d_i ) 时，结果为0）；
3. 将所有合法计数组合对应的方式数相乘后求和，得到最终的集合数量。

示例验证 #

同样用题目中的例子：

• 合法的 ( a ) 组合有两种：
  1. ( a_1=1, a_2=1 )：方式数为 ( \binom{2}{1} \times \binom{2}{1} = 2 \times 2 = 4 )，对应集合 ( {1,3}, {1,4}, {2,3}, {2,4} )；
  2. ( a_1=2, a_2=0 )：方式数为 ( \binom{2}{2} \times \binom{2}{0} = 1 \times 1 = 1 )，对应集合 ( {1,2} )；
• 总和为 ( 4+1=5 )，与题目给出的示例结果一致。

内容的提问来源于stack exchange，提问作者Maxpm