【Some Math】Pascal’s rule

Pascal’s rule 是说:

$$\pmatrix {n-1 \\ k } + \pmatrix{n-1 \\ k-1} = \pmatrix{n \\ k}$$

排列组合公式计算可验证,在此不必赘述。

这个rule可以有一个很直观的理解:在n个元素中,选择k个不同值,相当于在其中「在n个元素中的n-1个元素中,选择k个值。剩下的那个不选」,以及「在n个元素中的n-1个元素中,仅选择k-1个值。剩下的那个元素作为第k个值」这两种情形之和。

binomial公式(伯努利分布,二项分布)同样可以用这种递归的方式去写(事件一共重复N次,每次成功的概率为p,计算成功k次的概率):

binomial(N, k, p) = (1-p) * binomial(N-1, k, p) + p * binomial(N, k-1, p)

Leave a Reply

Your email address will not be published. Required fields are marked *