Metz
Reputation
Top tag
Next privilege 250 Rep.
 Mar 8 awarded Enthusiast Feb 24 awarded Teacher Feb 24 comment Why is the number of possible subsequences $2^n$? I mean, in this case in which you don't consider the order of the elements in each subsequence, the proof Manoj R provides suffice. Otherwise, for each subset of length k you also consider the number of its permutations: so you have C(n,0)*0! + C(n,1)*1! + C(n,2)*2! + ... + C(n,n)*n!. Feb 24 comment Why is the number of possible subsequences $2^n$? @Manish: i think what Qiaochu mean is that in this case to involve binomial theorem is just... too much:) I think the proof you propose in your comment becomes useful (and meaningful) if you consider also the order of the elements in each subsequence. Which is not the case. Feb 24 awarded Editor Feb 24 revised Why is the number of possible subsequences $2^n$? added 131 characters in body Feb 24 answered Why is the number of possible subsequences $2^n$? Jan 30 awarded Scholar Jan 30 accepted $(\{0, 1, … , 2^n-1\}, \oplus)$ groups Jan 30 awarded Student Jan 30 asked $(\{0, 1, … , 2^n-1\}, \oplus)$ groups