物理

[组合数学]——算两次

$设A={a_1,a_2,…,a_m}，B={b_1,b_2,…b_n}是两个有限集合$

$对∀a_i∈A，设C_i={(a_i,b)|b∈B}(i=1,2,…,m)，对∀b_j∈B，设D_j={(a,b_j)|a∈A}(j=1,2,…,n)$

$于是|A×B|=\sum_{i=1}^m|C_i|=\sum_{j=1}^n|D_j|$

$这个等式叫做富比尼(Fubini)原理，又叫做算两次原理$

$应用原理：同一对象两种不同角度去进行计数，综合起来以求结果$

$eg$

$设n,k∈N_+，S是平面内n个点的集合，满足：$

$(1)S中任何三点不共线；$

$(2)对S中每一个点P，S中至少有k个点与P的距离相等.$

$求证：k \lt \frac{1}{2}+\sqrt{2n}.$