请输入您要查询的字词:

 

单词 PascalsRulebitStringProof
释义

Pascal’s rule (bit string proof)


This proof is based on an alternate, but equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath, definition of the binomial coefficientMathworldPlanetmath: (nr) is the number of bit strings (finite sequencesPlanetmathPlanetmath of 0s and 1s) of length n with exactly r ones.

We want to show that

(nr)=(n-1r-1)+(n-1r)

To do so, we will show that both sides of the equation are counting the same set of bit strings.

The left-hand side counts the set of strings of n bits with r 1s. Suppose we take one of these strings and remove the first bit b. There are two cases: either b=1, or b=0.

If b=1, then the new string is n-1 bits with r-1 ones; there are (n-1r-1) bit strings of this nature.

If b=0, then the new string is n-1 bits with r ones, and there are (n-1r) strings of this nature.

Therefore every string counted on the left is covered by one, but not both, of these two cases. If we add the two cases, we find that

(nr)=(n-1r-1)+(n-1r)
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 1:35:47