有很多办法

1。

Consider a set with n elements, how many subsets (power set) does it have?

There is one way to calculate it. Each element has two choices, so that the total number of subsets will be 2^n

Another way, the cardinality of any subset must be >=0 and <= n. The number of subsets with cardinality k is C(n, k). So that the total number of subsets will
sum C(n, k)

2.

Consider polynomial (x+y)^n, expanding it
we have (x+y)^n = sum C(n, k) x^k y^{n-k}

set x = 1, y = 1

There are many ways more to prove it..

所有跟帖： 

• or you can simply count it, if your teacher does not -idiot94- ♂ (43 bytes) () 01/29/2009 postreply 06:20:54